Draw the binary search tree that results from inserting the following sequence of key values, in the order given, into an empty tree:
D, A, F, E, C, K, B, M, G
Draw the best two binary search trees that result from deleting the node labelled 'x' (i.e., the node at which the element with the key value 'x' is stored) from the tree shown below. (Only node labels [keys] are shown in the diagram.)
Imagine some binary tree diagram here.
What is the height-balance property of AVL trees?
What is splaying? When is it performed on a splay tree?
For each of the following tree diagrams, indicate whether or not the tree represents a legal configuration of a binary search tree implemented as a red-black tree by writing "legal" or "illegal" under each tree. Shaded nodes represent red nodes and open nodes represent black nodes.
A nice diagram of various binary trees goes here.
Redraw the last of the red-black tree diagrams above as the equivalent (2,4) tree.
What is the depth property of a (2,4) tree? What is the comparable property of a red-black tree?
What data structure has operations defined on it that perform a "zig", a "zig-zig", or a "zig-zag"?
