Short note: Trees and applications

A tree is a connected undirected graph with no cycles (simple circuits).

Properties (n vertices):

• Exactly one simple path joins any two vertices.
• It has n − 1 edges.
• Removing any edge disconnects it; adding any edge creates exactly one cycle.
• A tree with n ≥ 2 has at least two leaves (vertices of degree 1).

A rooted tree has one vertex chosen as the root; edges are directed away from it, giving parent, child, ancestor, descendant, leaf and internal vertex. A binary tree has at most 2 children per vertex. For a full m-ary tree with i internal vertices: n = mi + 1 and leaves l = (m − 1)i + 1.

          A            root A, children B, C
         / \           B has children D, E; leaves: D, E, C
        B   C          n = 5, edges = 4
       / \
      D   E

Applications:

• Binary search trees for fast searching and sorting.
• Expression trees in compilers and parse trees for syntax.
• Decision trees for classification and analysis of comparison sorts.
• Huffman coding trees for data compression.
• File system directories, organization charts and family trees.
• Spanning trees and minimum spanning trees for networks.
• Game trees and backtracking.