Balanced Tree Review Exercises

1. Show the tree that results from inserting the following keys into
   1. an AVL tree

   2. a red-black tree (circle black nodes, not red nodes)

   3. a 2-3 tree

   In each case, show the tree after each insertion.

   Keys:  10  5  3  9  8  1  3  7  4  2
   

2. Explain the relationship between red-black trees and 2-3-4 trees.

3. Show the red-black tree corresponding to the following 2-3-4 tree.

                         10  20  30
                       /   |    |   \
                      /    |    |    \
                     /     |    |     \
                  5 6     15   25 26   35 40 45
   

4. Show the 2-3-4 tree corresponding to the following red-black tree (color designated by B or R).

                               50B
                             /     \
                            /       \
                          20R        80B
                         /   \      /   \
                       10B   30B  70R   100R                 
   

5. In big-O, what is the time required to insert into an N-element
   1. AVL tree?

   2. red-black tree?

   3. 2-3 tree?

   Would the answer for (c) be different if it were an N-node 2-3 tree instead of a 2-3 tree holding N elements?