18.2 Creating LLRB Trees
Software Engineers? More like Tree Engineers
Software Engineers? More like Tree Engineers
We said in the previous section that we really like 2-3 trees because they always remain balanced, but they are very hard to implement. On the other hand, BSTs can be unbalanced, but we like how simple and intuitive they are. Is there a way to combine the best of two worlds? Why not create a tree that is implemented using a BST, but is structurally identical to a 2-3 tree and thus stays balanced?
(Note that in this chapter we will be honing in on 2-3 Trees specifically, not 2-3-4 trees)
We are going to create this tree by looking at a 2-3 tree and asking ourselves what kind of modifications we can make in order to convert it into a BST.
For a 2-3 tree that only has 2-nodes (nodes with 2 children), we already have a BST, so we don't need to make any modifications!
However, what happens when we get a 3-node?
One thing we could do is create a "glue" node that doesn't hold any information and only serves to show that its 2 children are actually a part of one node.
However, this is not an elegant solution because we are taking up more space and the code will be ugly. So, instead of using glue nodes we will use glue links instead!
To transform dummy glue nodes to glue links, we choose arbitrarily to make the left element a child of the right one. This results in a left-leaning tree.
We show that a link is a glue link by making it red. Normal links are black. Because of this, we call these structures left-leaning red-black trees (LLRB). We will be using left-leaning trees in this course.
Left-Leaning Red-Black trees have a 1-1 correspondence with 2-3 trees. Every 2-3 tree has a unique LLRB red-black tree associated with it.
As for 2-3-4 trees, they maintain correspondence with standard Red-Black trees.
Below is a summary of the properties/invariants of LLRB Trees:
1-1 correspondence with 2-3 trees.
No node has 2 red links.
There are no red right-links.
Every path from root to leaf has the same number of black links (because 2-3 trees have the same number of links to every leaf).
Height is no more than 2x height + 1 of the corresponding 2-3 tree.
The height of a red-black tree is proportional to the log of the number of entries.
