Chapter 10
Trees

 Modified: 

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter10/extra_examples.html - Extra examples with solutions.

10.1 Introduction to Trees

Definition 1

Tree is a connected graph with no simple circuits.

Example

G1, G2 are trees

G3 has circuit d,a,b,c,d

G4 is not connected

Definition

Forest is unconnected trees.

Theorem 1

Tree as undirected graph iff simple path between any two vertices.

Definition 2

Rooted tree has one vertex designated as root and every edge is directed away from the root.

T is undirected graph as a tree, any vertex could be root.

Question

Draw tree T with root b.

Definitions by Example

Parent a of g, f, b.
Child g, f, b of a.
Leaf if no children, d,e,f,i,k,l,m
Ancestors a, b,c of d.
Siblings g, f, b.
Descendants b, c, d of a.
All are descendants of the root
Internal vertices have children.
a,b,c,g,h,j
Subtree g.
 

Definition 3

m-ary tree if every internal Vertex has no more than m children.

Full m-ary tree if every internal Vertex has exactly m children.

Binary tree is m-ary tree with m=2.

T1 is full binary

T2 is full 3-ary

T3 is full 5-ary

T4 is 3-ary

Definition

Left child in (a) of parent a is b

in (c) of parent i is k.

Trees as Models

 

Seven connected processors

Recurrence relations

Edges are labeled with the values of each recurrence term.

a0 = 3

a1 = 4

an = an-1 + an-2

 

 

Properties of Trees

Theorem 2

n vertices tree has n-1 edges.

Example

Below tree has 7 vertices and 6 edges.

Theorem 3

Full m-ary tree with i internal vertices contains n=mi+1 vertices.

Example

Above 2-ary tree

3 internal vertices

n=2*3+1 = 7 total vertices.

Theorem 4

Full m-ary tree with:

(i) n vertices has i=(n-1)/m internal vertices and l=[(m-1)n+1]/m leafs.

(ii) i internal vertices has n=mi+1 vertices and l=(m-1)i+1 leafs.

(iii) l leafs has n=(ml-1)/(m-1) vertices and i=(l-1)/(m-1) internal vertices.

Example

Full 3-ary tree: (iii) l leafs has n=(ml-1)/(m-1) vertices and i=(l-1)/(m-1) internal vertices.

9 leafs

n = (3*9-1)/(3-1) = 13 total vertices

i = (9-1)/(3-1) = 4 internal vertices

Example 9

Chain letter sent to 4 others represented by 4-ary tree with leaf Vertexs those not sending letter.

How many people have seen letter, including first person, if no duplicates and letter ends after 100 people received but did not send (leaf Vertex)?

How many people sent the letter?

Internal Vertexs those who sent letter.

(iii) l leafs has n=(ml-1)/(m-1) vertices and i=(l-1)/(m-1) internal vertices.

l=100    Leaf Vertexs.

By (iii) n=(4*100-1)/(4-1) = 399/3 = 133 vertices, the number who have seen the letter.

By (iii) i=(100-1)/(4-1) = 99/3 = 33 internal vertices, the number who sent out the letter.

 

Definition

Balanced m-ary tree if all leaf Vertexs are at levels h or h-1.

Example

T1 is balanced, leafs at level 3 and 4.

T2 is not balanced, leafs at levels 2, 3, 4.

T3 is balanced, all leafs at level 3.

 


 

Definition

Height is maximum number of edges from tree root to lowest leaf.

Depth is number of edges a vertex is from the root.

 

Theorem 5

mh maximum leafs in m-ary tree of height h.

Example

Following 2-ary tree of height 2 has 4 leafs.

mh = 22 = 4

Example

Full 4-ary tree of height 5 has 1024 leafs.

mh = 45 = 1024

 

Example

3-ary
Height

Maximum
leafs mh
0 30 = 1
1 31 = 3
2 32 = 9
3 33 = 27

Corollary 1

h ³ élogm lù for m-ary tree of height h and l leafs.

h = élogm lù for full and balanced m-ary tree of height h and l leafs.

Example

Below full, balanced 2-ary tree of height 2 has 4 leafs.

h = élog2 4ù = élog2 22ù = é2ù = 2

Example

4-ary tree of height 5 has 1024 leafs maximum.

h ³ élog4 1024ù = élog4 45ù = é5ù = 5

 

10.2 Applications of Trees

Binary Search Trees

Definition

Binary search tree totally orders vertices.

Example

The following binary tree is totally ordered where all:

  1. left children are alphabetically less than the parent,
  2. right children are alphabetically greater than the parent.

 

Definition

Binary search tree constructed by adding vertices to maintain a total ordering.

Example

Child vertices:

  1. > parent, add to right
  2. < parent, add to left
  3. = parent, don't add

Example

Add computer science to the right-bottom figure.

 

Example

Add oceanography to the figure using Algorithm 1.

Algorithm 1 Locating and Adding Items to a Binary Search Tree

procedure insertion( T : binary search tree, x : item)

v := root of T

while v ¹ null and label(v) ¹ null

if x < label( v ) then

if left child of v ¹ null

then v := left child of v

else  add new vertex as left child of v

         v := null

else

if right child of v ¹ null

then v := right child of v

else  add new vertex as right child of v

         v := null

if root of T = null then add a vertex v to 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 the new vertex
 

Decision Trees

Example

8 coins, 1 counterfeit of different weight than other 7 coins.

Same number of coins on balance scale weight either:

left < right, left = right, left > right

3-ary decision.

Best case possible is 2 weightings below:

Weight 1,2,3 and 4,5,6: left = right

Weight 7 and 8: either left < right or left > right

8 possible outcomes, 8 leafs

coin in leaf 1,2, 4, 5, 7, 8 is counterfeit.

By Corollary 1:

 h ³ élog3 8ù @ é1.89ù = 2

so the decision tree height is at least 2, agreeing with the above figure.

 

Corollary 1

h ³ élogm lù for m-ary tree of height h and l leafs.

h = élogm lù for full and balanced m-ary tree of height h and l leafs.

 

Example

Sorting a, b, c.

P(3,3) = 3! = 6 ways to arrange 3 values

a<b<c a<c<b b<a<c b<c<a c<a<b c<b<a

6 leaf Vertexs

Decision tree for sorting compares 2 values at a time (binary-comparison sort).

2-ary tree.

left > right left < right

Sorting n has n! outcomes (leafs).

Number of comparisons (tree height), by Corollary 1:

h ³ élog2 n!ù

élog2 3!ù = élog2 6ù @ é2.33ù = 3

so the height is at least 3, agreeing with the below figure.

élog2 n!ù is Q(n log2 n)

Graph illustrates that log n! is O(n log n)

Means that a binary-comparison sort is Q(n log2 n)

Example - Sorting

 

10.3 Tree Traversal

Universal Address Systems

Traverse tree in lexicographic (dictionary or alphabetical) order:

0<1<1.1<1.2<1.3<2<3<3.1<3.1.1<3.1.2.1<3.1.2.2<3.1.1.3<3.1.2.4<3.1.2<3.1.3<3.2<4<4.1<5<5.1<5.1.1<5.2<5.3

 

Traversal Algorithms

Example

Trees are naturally recursive, each subtree is a tree.

Tree algorithms are recursive, when visiting subtrees.

The following lists first, then visits only left subtrees.

Order listed is: a, b, e, j

Algorithm 0.1 Preorder Left Subtree Traversal

procedure preLeft( T: ordered rooted tree )

if T = null then return

r := root of T

list r

T( c ) := left subtree with c as root

preLeft( T( c ) )

The following first visits only left subtrees, then lists.

Order listed is: j,e,b,a

Algorithm 0.2 Postorder Left Subtree Traversal

procedure postLeft( T: ordered rooted tree )

if T = null then return

r := root of T

T( c ) := left subtree with c as root

postLeft( T( c ) )

list r

Definition 1

Preorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.
  1. Visit r.
  2. Visit T1 in preorder.
  3. Visit T2 in preorder.

  n.  Visit Tn in preorder.

 

Example

Preorder traversal of T visits vertices in the order of:

a,b,e,j,k,n,o,p,f,c,d,g,l,m,h,i

Algorithm 1 Preorder Traversal

procedure preorder( T: ordered rooted tree )

r := root of T

list r

for each child c of r from left to right

T( c ) := subtree with c as root

preorder( T( c ) )

Definition 1

Preorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.
  1.     Visit r.
  2.     Visit T1 in preorder.
  3.     Visit T2 in preorder.

  n+1.  Visit Tn in preorder.

Definition 2

Inorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.
  1.     Visit T1 inorder.
  2.     Visit r.
  3.     Visit T2 inorder.

  n+1. Visit Tn inorder.

Inorder traversal of T visits vertices in the order of:

j,e,n,k,o,p,b,f,a,c,l,g,m,h,d,h,i

Algorithm 2 Inorder Traversal

procedure inorder( T: ordered rooted tree )

r := root of T

if r is leaf then list r

else

l := first child of r from left to right

T( l ) := subtree with l as its root

inorder( T( l ))

list r

for each child c of r except for l from left to right

T( c ) := subtree with c as root

inorder( T( c ) )

Definition 3

Postorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.
  1.     Visit T1 postorder.
  2.     Visit T2 postorder.

  n.      Visit Tn postorder.

  n+1. Visit r.

Algorithm 3 Postorder Traversal

procedure postorder( T: ordered rooted tree )

r := root of T

for each child c of r from left to right

T( c ) := subtree with c as root

postorder( T( c ) )

list r

Postorder traversal of T visits vertices in the order of:

j,n,o,p,k,e,f,b,c,l,m,g,h,i,d,a

Example

Lexiographic ordering of "newyork" in a binary-search tree.

               n
             /   \
           e      w
            \     /  \
             k  o     y
                  \     
                   r    

     void Preorder() {              
          System.out.print( key );                      // nekwory
          if( left != null) left.Preorder( );
          if( right != null) right.Preorder( );
     }
     void Inorder() {              
          if( left != null) left.Inorder( );
          System.out.print( key );                      // eknorwy
          if( right != null) right.Inorder( );
     }
     void Postorder() {             
          if( left != null) left.Postorder( );
          if( right != null) right.Postorder( );
          System.out.print( key );                      // keroywn
     }

Java Preorder/Inorder/Postorder construction and traversal of binary tree

 class Vertex {
     Vertex p, left, right;
     char key;
 
     Vertex (char key, Vertex p, Vertex left, Vertex right) {
                  this.key=key;    this.p = p;
                  this.left = left;   this.right = right;
     }
           
     void Preorder() {               // Traverse preorder
          System.out.println( key );
          if( left != null) left.Preorder( );
          if( right != null) right.Preorder( );
     }
 
     void Inorder() {               // Traverse inorder
          if( left != null) left.Inorder( );
          System.out.println( key );
          if( right != null) right.Inorder( );
     }

     void Postorder() {               // Traverse postorder
          if( left != null) left.Postorder( );
          if( right != null) right.Postorder( );
          System.out.println( key );
     }

     void Insert(char key) {    // Insert new Vertex
           if( key <= this.key)
                  if( left != null ) left.Insert( key );
                  else left = new Vertex(key, this, null, null);
           else
                  if( right != null ) right.Insert( key );
                  else right = new Vertex(key, this, null, null);
      }
}
 
public class VertexFun {
     public static void main(String a[]) {
           Vertex root = new Vertex( 'n', null, null, null);
           root.Insert( 'e' );
           root.Insert( 'w' );
           root.Insert( 'y' );
           root.Insert( 'o' );
           root.Insert( 'r' );
           root.Insert( 'k' );
 
           root.Inorder();
     }
}

 

Infix, Prefix, Postfix Notation

Binary tree representing ((x+y) ^2) + ((x-4)/3)
                                          

Preorder: + ^ + x y 2 / - x 4 3

Inorder: x + y ^ 2 + x - 4 / 3

Postorder: x y + 2 ^ x 4 - 3 / +

 

RPN - Reverse Polish Notation

RPN can be evaluated by a simple stack machine.

The following stack algorithm evaluates an expression in RPN.

Evaluate the RPN: 1 2 3 * - 4 +

Try the Java applet to enter expressions in the form specified in the expression grammar, parse, generate RPN, then evaluate the RPN. Source code for the applet is available.

 

10.4 Spanning Trees

Definition 1

Spanning tree of simple graph G is subgraph of G containing every vertex of G.

Example 1

Simple graph not necessarily a tree, below has circuits.

Spanning tree construction from the simple graph

 

Theorem 1

Connected simple graph iff it has a spanning tree.

Proof

Show G connected

  1. Assume simple graph G has spanning tree T.
  2. T contains every vertex of G.
  3. T is a subgraph of G, therefore is a path between every two vertices of T.
  4. Since T is a spanning tree of G and a subgraph of G, G is connected.

Show spanning tree

  1. Assume G is connected.
  2. If G is not a tree, contains simple circuit.
    1. Remove an edge from circuit.
      • Result still contains all vertices of G.
      • Still connected.
    2. Go to 2.
  3. G is a connected tree, no simple circuits remain.

Example

Several spanning trees

Example 2

IP Multicasting

 

Depth-First Search

 

Algorithm 1 Depth-First Search

procedure DFS( G : connected graph, vertices: v1, v2,...vn)
T := tree consisting of v1
visit( v1 )

procedure visit( v : vertex of G)

for each vertex w adjacent to v and not yet in T

add vertex w and edge (v, w) to T

visit( w )

Example
  1. Add v1 = f arbitrarily as root of T.
  2. {d,e,g,h} adjacent to f, pick g.
  3. T=(V,E)
    • V={f,g}
    • E={(f,g)}
  4. {f,h} adjacent to g, f already in T, pick h.
  5. T=(V,E)
    • V={f,g,h}
    • E={(f,g), (g,h)}

    Continue adding {h,k,j}

  6. No vertex adjacent to j, not yet in T
  7. Backtrack to k
  8. No vertex adjacent to k, not yet in T
  9. Backtrack to h
  10. Vertex i adjacent to h, not yet in T, pick i.

    T=(V,E)

    • V={f,g,h,k,j,i}
    • E={(f,g),(g,h),(h,k),(k,j),(h,i)}
       
  11. No vertex adjacent to i, not yet in T
  12. Backtrack to h
  13. No vertex adjacent to h not yet in T
  14. Backtrack to f
  15. Vertex c,d adjacent to f, not yet in T, pick d.

    T=(V,E)

    • V={f,g,h,k,j,i,d}
    • E={(f,g),(g,h),(h,k),(k,j),(h,i),(f,d)}

:

 

Breadth-First Search

 

Algorithm 2 Breadth-First Search

procedure BFS( G : graph, vertices: v1,v2,...vn)
T := tree consisting of v1
L := empty list
put v1 in the list L of unprocessed vertices

while L is not empty

remove the first vertex, v, from L

for each neighbor w of v

if w not in L and not in T then

add w to the end of list L

add w and edge (v, w) to T

Example
  1. Add v1 = e arbitrarily as root of T.
  2. L = { e }
  3. v = e
  4. {b,d,i,f} neighbors of e
    • L = { b }
    • T=(V,E)
      • V={e,b}
      • E={(e,b)}
    • L = {b, d}
    • T=(V,E)
      • V={e,b,d}
      • E={(e,b), (b,d)}
    • L = {b, d, i}
    • T=(V,E)
      • V={e,b,d,i}
      • E={(e,b), (e,d), (e,i)}
    • L = {b, d, i, f}
    • T=(V,E)
      • V={e,b,d,i}
      • E={(e,b), (e,d), (e,i), (e,f)}
  5. v = b first of L = {b,d,i,f}
  6. {a,c,e} neighbors of b
    • L = {d,i,f,a}
    • T=(V,E)
      • V={e,b,d,i,a}
      • E={(e,b),(e,d),(e,i),(e,f),(b,a)}
    • L = {d,i,f,a,c}
    • T=(V,E)
      • V={e,b,d,i,a,c}
      • E={(e,b),(e,d),(e,i),(e,f),(b,a),(b,c)}