CS 61B

Time: Tue 11/14/17 3 pm

Self Balancing Trees

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:

  1. Convert right-leaning trees to left leaning
  2. Rotate linked red nodes into a normal 4-node (temporarily)
  3. 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 allows a pretty quick dictionary-like lookup. What affects the runtime per operation of insertion, lookup or deletion?

Practice Question


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.