Define tree; properties and applications

Definition

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

Properties

For a tree T with n vertices:

1. There is exactly one simple path between any two vertices.
2. T has exactly n − 1 edges.
3. Removing any edge disconnects T; adding any edge between two vertices creates exactly one cycle.
4. A tree with n ≥ 2 vertices has at least two leaves (vertices of degree 1).
5. A graph is a tree iff it is connected with n − 1 edges, or acyclic with n − 1 edges.
6. A rooted tree has a root, and the terms parent, child, sibling, ancestor, descendant, leaf and internal vertex are defined by direction away from the root. In a full m-ary tree with i internal vertices, n = mi + 1 and leaves l = (m − 1)i + 1.

        r            n = 6 vertices, 5 edges
       / \           leaves: c, d, e
      a   b          internal: r, a, b
     / \   \
    c   d   e

Applications

• Binary search trees, heaps (searching, sorting, priority queues).
• Expression trees and parse trees in compilers.
• Decision trees (classification, lower bound for sorting).
• Huffman coding for data compression (prefix codes).
• Hierarchical structures: file systems, organization charts, XML/HTML DOM.
• Spanning trees for network design (minimum spanning tree) and routing.
• Game trees and backtracking search.