Trees & Applications of Trees

1Trees

History and uses:

• Arthur Cayley (1857) used trees to count chemical compounds.
• Computer science: efficient algorithms for locating items in a list.
• Games such as checkers and chess: finding winning strategies.
• Modelling sequences of decisions, e.g. the complexity of sorting algorithms.
• Family trees (genealogical charts): vertices are people, edges are parent–child links.

Forests

A graph with no simple circuits that is not necessarily connected is a forest. Each connected component is a tree. (Figure 3: one graph, three components, three trees.)

2Rooted trees & terminology

• Any vertex can be chosen as the root, and different roots give different rooted trees (Figure 4: the same tree T rooted at a and at c).
• We draw the root at the top and omit the arrows: the choice of root determines their directions.

3Ordered rooted trees & binary trees

In some applications every non-root vertex is labelled left or right even if it is an only child.

4Binary search trees (BST)

Goal: search a list efficiently when the items are totally ordered.

Building one (insertion)

1. The first item becomes the root.
2. For each new item, start at the root:
   • Smaller → go left; larger → go right.
   • Repeat until the needed child doesn't exist.
3. Insert the item there as a new left or right child.

                 mathematics
               /             \
        geography            physics
        /       \           /       \
  chemistry   geology  meteorology  zoology
                                    /
                              psychology

Algorithm 1 — locating and adding an item

procedure insertion(T: binary search tree, x: item)
v := root of T              {a vertex not present in T has the value null}
while v ≠ null and label(v) ≠ x
begin
    if x < label(v) then
        if left child of v ≠ null then v := left child of v
        else add new vertex as a left child of v and set v := null
    else
        if right child of v ≠ null then v := right child of v
        else add new vertex as a right child of v and set v := null
end
if root of T = null then add a vertex v to the tree and label it with x
else if v is null or label(v) ≠ x then label new vertex with x and let v be this new vertex
{v = location of x}

5Quick revision sheet