Chapter 8: Tree

8.1 Trees

8.1.1 Terminology.

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

A rooted tree is a tree in which a particular vertex is designated as the root and every edge is directed away from the root.

The level of a vertex v is the length of the simple path from the root to v. The height of a rooted tree is the maximum level of its vertices.

Let T be a tree with root v0. Suppose that x, y and z are vertices

in T and that (v0, v1, . . . , vn) is a simple path in T. Then:

1. vn−1 is the parent of vn.

2. v0, v1, . . . , vn−1 are ancestors of vn.

3. vn is a child of vn−1.

4. If x is an ancestor of y, y is a descendant of x.

5. If x and y are children of z, x and y are siblings.

6. If x has no children, it is called a terminal vertex or leaf.

7. If x is not a terminal vertex, it is an internal or branch vertex.

8. The subtree of T rooted at x is the graph (V,E), where V is x together with its escendants and E = edges of simple paths from x to some vertex in E.

8.2. Binary Trees

8.2.1. Binary Trees.

A binary tree is a rooted tree in which each vertex has at most two children, designated as left child and right child. If a vertex has one child, that child is designated as either a left child or a right child, but not both. A full binary tree is a binary tree in which each vertex has exactly two children or none.

1. If T is a full binary tree with i internal vertices, then T has i+1 terminal vertices and 2i + 1 total vertices.

2. If a binary tree of height h has t terminal vertices, then t <= 2^h.

More generally we can define a m-ary tree as a rooted tree in which every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. A binary tree is just a particular case of m-ary ordered tree (with m = 2).

8.2.2. Binary Search Trees

Assume S is a set in which elements (which we will call "data") are ordered; e.g., the elements of S can be numbers in their natural order, or strings of alphabetic characters in

lexicographic order. A binary search tree associated to S is a binary tree T in which data from S are associate with the vertices of T so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

8.3. Decision Trees, Tree Isomorphisms

8.3.1. Decision Trees.

A decision tree is a tree in which each vertex represents a question and each descending edge from that vertex represents a possible answer to that question.

8.4. Tree Transversal

8.4.1. Transversal Algorithms.

A rooted tree T = (V,E) with root r. If T has only one vertex r, then r by itself constitutes the preorder, postorder and inorder transversal of T. Otherwise, let T1, . . . , Tk the subtrees of T from left to right (fig. 8.15). Then:

1. Preorder Transversal : Pre(T) = r, Pre(T1), . . . , Pre(Tk).

2. Postorder Transversal: Post(T) = Post(T1), . . . ,Post(Tk), r.

3. Inorder Transversal. If T is a binary tree with root r, left subtree TL and right subtree TR, then: In(T) = In(TL), r, In(TR).

8.5. Spanning Trees

8.5.1. Spanning Trees.

A tree T is a spanning tree of a graph G if T is a subgraph of G that contains all the vertices of G.

8.5.2. Breadth-First Search Algorithm

1. Add v1 to T, insert it in the queue and mark it as "visited".

2. If the queue is empty, then we are done. Otherwise let v be the vertex in the front of the queue.

3. For each vertex v0 of G that has not been visited yet and is adjacent to v (there might be none) taken in order of increasing subscripts, add vertex v0 and edge (v, v0) to T, insert v0 in the queue and mark it as "visited".

4. Delete v from the queue.

5. Go to step 2.

A pseudocode version of the algorithm is as follows:

1: procedure bfs(V,E)

2: S := (v1) {ordered list of vertices of a fix level}

3: V' := {v1} {v1 is the root of the spanning tree}

4: E' := {} {no edges in the spanning tree yet}

5: while true

6: begin

7: for each x in S, in order,

8: for each y in V - V'

9: if (x,y) is an edge then

10: add edge (x,y) to E' and vertex y to V'

11: if no edges were added then

12: return T

13: S := children of S

14: end

15: end bfs

8.5.3. Depth-First Search Algorithm.

1. Add v1 to T, insert it in the stack and mark it as "visited".

2. If the stack is empty, then we are done. Otherwise let v be the vertex on the top of the stack.

3. If there is no vertex v0 that is adjacent to v and has not been visited yet, then delete v and go to step 2 (backtrack). Otherwise, let v0 be the first non-visited vertex that is adjacent to v.

4. Add vertex v0 and edge (v, v0) to T, insert v0 in the stack and mark it as "visited".

5. Go to step 2.

A pseudocode version of the algorithm is as follows:

1: procedure dfs(V,E)

2: V' := {v1} {v1 is the root of the spanning tree}

3: E' := {} {no edges in the spanning tree yet}

4: w := v1

5: while true

6: begin

7: while there is an edge (w,v) that when added

8: to T does not create a cycle in T

9: begin

10: Choose first v such that (w,v)

11: does not create a cycle in T

12: add (w,v) to E'

13: add v to V'

14: w := v

15: end

16: if w = v1 then

17: return T

18: w := parent of w in T {backtrack}

19: end

20: end

8.5.4. Minimal Spanning Trees.

Given a connected weighted tree G, its minimal spanning tree is a spanning tree of G such that the sum of the weights of its edges is minimum.

Prim's Algorithm. It starts with a single vertex and at each iteration adds to the current tree a minimum weight edge that does not complete a cycle. The following is a pseudocode version of Prim's algorithm. If (x, y) is an edge in G = (V,E) then w(x, y) is its weight, otherwise w(x, y) = 1. The starting vertex is s.

1: procedure prim(V,w,s)

2: V' := {s} {vertex set starts with s}

3: E' = {} {edge set initially empty}

4: for i := 1 to n-1 {put n edges in spanning tree}

5: begin

6: find x in V' and y in V - V' with minimum w(x,y)

7: add y to V'

8: add (x,y) to E'

9: end

10: return E'

11: end prim

Kruskal's Algorithm. Another algorithm to find a minimal spanning tree in a connected weighted tree G = (V,E) is Kruskal's Algorithm. It starts with all n vertices of G and no edges. At each iteration we add an edge having minimum weight that does not complete a cycle. We stop after adding n − 1 edges.

1: procedure kruskal(E,w,n)

2: V' := V

3: E' := {}

4: while |E'| < n-1

5: begin

6: among all edges not completing a cycle in T

7: choose e of minimum weight and add it to E

8: end

9: T' = (V',E')

10: return T'

11: end kruskal