Reading

7.4. Balanced Trees
Explanation of 2-3 trees and red-black trees from Sedgewick & Wayne.
- Note: S&W colors the links between nodes instead of the nodes themselves. The color of a link in S&W corresponds in our presentation to the color of the target node of the link.
7.6. Red-Black Trees (code only)
Optional handout: 2-3 tree deletion

Note: The red-black trees in our course are those of Sedgewick & Wayne. These allow a red node only as a left child of a black node. There are other variants of red-black trees out there where red nodes can also be right children. These have a different (weaker) invariant and thus use different operations to fix the invariant when inserting a node.

Summary of the invariant of red-black trees

Every red node is the left child of a black node.
Every branch (path from the root through the tree) has the same number of black nodes.

Summary of how to insert in a red-black tree

Insert the new key using the BST insertion procedure and color it red.
This may create a problem with Part A of the invariant. Use color flips and rotations to fix this problem. Fixing a problem may create a new such problem one level higher up in the tree. Continue fixing these problems until no problem remains or the root itself becomes red. In that case, color the root black.

Color flip. Given a black node with two red children, color the node red and its children black.

Right rotation. Given a node x with right child y, replace x by y and make x the left child of y. Exchange the colors of x and y. Put the remaining subtrees of x and y in the correct places according to the ordering.

Left rotation. The opposite of a right rotation. Given a node y with left child x, replace y by x and make y the right child of x. Exchange the colors of x and y. Put the remaining subtrees of x and y in the correct places according to the ordering.

Kinds of problems:

A red node is a right child. Solution:
- If it has a red sibling, use a color flip.
- Otherwise, use a left rotation to instead turn the parent into a red left child.
A red node x is a left child of a red node y. Solution: y must be the left child of a black node z (why?). Use a right rotation to make z a right child of y. (Now you can continue with a color flip.)

Videos and slides

E. 2-3 trees
F. Red-black trees

Note: Check out the tree visualizations (e.g. Gnarley trees) to see self-balancing search trees in action.

Mentimeter

Results