NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Balanced Trees


1. Draw the 2-3-4 tree that results when you perform top-down insertion of the keys D E M O C R A T I C in that order into an initially empty tree.
















2. Draw the red-black tree that results when you perform top-down insertion of the following keys in that order into an initial empty tree.

D E M O C R A T I C
Hint: feel free to use the Java tree tool from the course web page to check your work, but note that you would be expected to solve a problem like this on exam without any help.
















3. Insert the following keys in that order in an empty tree using the standard BST insertion method.

R E P U B L I C A N
Starting from this BST, insert J using splay insertion.