A Red-Black tree is one of the more popular self-balancing binary search tree, with it commonly being used by built-in libraries – like in C++ where it is normally used to implement std::set and std::map.
After needing to implement a Red-Black tree, I found that, while there are many posts on Red-Black Trees, many of the posts did not sufficiently explain how to handle the many different cases in insertion and deletion. As well, there wasn’t a single website one could look at, and some left me more confused than when I had visited. I am hoping this series of posts, with a description for insertion and deletion, will fill this gap.
You can view my complete implementation of a Red-Black Tree on GitHub.
Requirements for Red-Black Tree
Red-Black trees must first meet the requirements for a regular binary search tree, mainly each node has up to two children (normally called left and right) and for each node, its key must be greater than all keys in the left subtree, and not greater than any key in the right subtree.
In addition, each node is marked as being either red or black, with the additional following limitations:
- All leaves (non-existent/null children) are counted as being black.
- If a node is red, then its children are black.
- Every path from a given node to any of the descendant leaves contains the same number of black nodes.
- The root is black. (Not necessarily required, but makes things easier)
By enforcing 2 and 3, the length of the longest path from root to leaf will never be longer than twice the length of the shortest path from root to leaf. This causes the tree to be roughly height balanced, and ensures that the worst case for lookup is still O(log N).
In this example, nodes 1 and 8 would have two leaves, while node 4 would just have a leaf as its right child.
There are also some very helpful visualization programs for Red Black Trees.
Where N is the number of elements already inserted into the tree.
- Parent: Direct parent of node.
- Child: The left or right child of the node.
- Grandparent: The parent of the nodes parent. Guaranteed to exist if node’s parent is red, otherwise may not exist.
- Sibling: Other child of parent, can be null.
- Uncle: Sibling of parent, may not exist.
One very important operation for Red Black trees is rotation, which is used in both insertion and deletion to help balance the tree. There are left and right rotations, which are symmetric to each other.
Let the node being rotated be N, the left child of N be L, and the right child of N be R.
In a right rotate, N will become the right child of L. L keeps its left subtree (A in the example) but the right subtree (B in the example) is moved to be the left subtree of N.
The exact opposite will occur in a left rotate, with N becoming the left subtree of R, and the left child of R becoming the right child of N.
Be careful that you do not lose any references to any of the children and that you properly update all parent references (including the original parent of N).
I also have example C++ code for rotation.