2-4 Tree

A 2-4 tree is a kind of tree that has add and remove operations that are guaranteed to keep the tree balanced. The question is how to place the elements on the nodes of the tree so that find is efficient. For the project, we saw a way to do so by placing the elements only at the leaves in sorted order and using the branch nodes only as organization. (A 2-4 tree is very similar to the 2-3 tree from the project.) Instead, a red-black tree will use a different scheme where elements are stored at branch nodes in addition to leaves.

Red-Black Trees

A red-black tree is a binary search tree where in addition each node has a color, either red or black. The colors satisfy the following two properties:

• Black-height: There are the same number of black nodes on every root to leaf path.
• No-Red-Edge: No two red nodes are adjacent. That is, there is no parent and child that are both red.

A red-black tree simulates a 2-4 tree and for that reason the red-black trees are guaranteed to be balanced; the height is always at most \(2 \log n\). This is covered in Section 9.2.1 in the book.

Insert

I briefly started talking about insert. We will continue with insert (and I will post some notes on insert) after the exam.

Exercise

No exercises, study for the exam.