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.

Red Black Trees

Three fix ups mentioned in the lecture:

Convert right-leaning trees to left leaning

Rotate linked red nodes into a normal 4-node (temporarily)

Break up 4-nodes into 3-nodes or 2-nodes

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

Trie allows a pretty quick dictionary-like lookup. What affects the runtime per operation of insertion, lookup or deletion?

Practice Question

(fa07-final-5)

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.