Time: Tue 11/14/17 3 pm
What are the best/worst run time for inserting an element into, finding an item in, or removing an item from a binary search tree? What about the run time for a self balancing tree?
2-3-4 tree (2-4 tree), an order-4 B-tree, is an isometry of red-black tree. However, it can be a more manageable option to get started, before transitioning to red-black tree.
Try insert the following numbers into a 2-3-4 tree: [1, 12, 8, 2, 25, 6, 14, 28, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45] (from: CMSC 132: Object-Oriented Programming II).
Deleting from a tree can be more elaborative.
Three fix ups mentioned in the lecture:
Color the root of the tree back to black; as a result of other fix ups, the root may be colored red.
Try experimenting with the numbers from above. Try converting a 2-3-4 tree to/from a leaf leaning red black tree (LLRB).
Trie allows a pretty quick dictionary-like lookup. What affects the runtime per operation of insertion, lookup or deletion?
If a 2-4 tree has a height of h (that is, if the lowest nodes that contain keys are at a distance of h edges from the root), what is the maximum possible height of a corresponding red-black tree? Give your reasoning.