Red Black Trees
Last updated
Last updated
We will create a new tree structure similar to B-trees, since B-trees are really difficult to implement.
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
rotateRight(G): Let x be the left child of G. Make G the new right child of x.
Below is a graphical description of what happens in a left rotation on the node G.
We could also rotate a non-root node.
We could use a red link to convert a 3-node to BST tree. We choose arbitrarily to make the left element a child of the right one. The structure is called left-leaning red-black trees (LLRB).
Left-Leaning Red-Black trees have a 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 same number of black links.
Height is no more than 2x height of corresponding 2-3 tree.
While inserting, use a red link.
If there is a right leaning "3-node", rotate left the appropriate node to fix.
If there are two consecutive left links, rotate right the appropriate node to fix.
If there are any nodes with two red children, color flip the node to emulate the split operation.
Because a LLRB tree has a 1-1 correspondence with a 2-3 tree and will always remain within 2x the height of its 2-3 tree, the runtimes of the operations will take log N time.
