Trees - Red-Black
When we looked at binary search trees in the previous lesson, we neglected
worst case scenarios. This is a valid binary search tree, however traversing
the tree causes time complexity grows to
Is there a way we can re-balance this tree such that it returns back
to
A red-black tree is a self balancing binary search tree that balances after each insertion or deletion.
Why is it termed red-black? This term and some rules help us distinquish between a red-black tree and a binary search tree that happens to be balanced. Here are the rules:
- nodes are colored either red or black
- The root node is black
- There are no parent-child red nodes (however this is not the case for black)
- Every leaf (including null nodes) are black
- Every path from root to leaf has the same number of black nodes
A few correlaries. A black node may have a red node as a child. A node may be recolored. When we insert a node, we should first color it red. We will next go through a step-by-step process of how coloring will work when we insert a few nodes. When we insert a node, we have two tools we may use to rebalance the tree: re-colouring or rotating.
Start with a single root node. It must be colored black.
Insert two nodes, one on either side of the root. We color each red.
Insert a node that is smallest yet. We color it red. We have now violated a rule of a red-black tree. We should try and re-color the parent node.
We can't stop here, otherwise we would violate the rule of same number of black nodes from root to leaf. So we recolor the same depth node to black as well.
This looks good. All we had to do to conform to a red-black tree is to re-colour our nodes, the structure of the tree is fine.
We insert a node that is again smallest yet. There is no re-coloring we may perform that conforms to the rules of a red-black tree, thus we must rotate it.
There are multiple rotations possible: left-rotate, right-rotate, left-right-rotate, and right-left-rotate. We elect to do a right-rotate on the intermediate node 2.
With right-rotate, given a node x (3) that is parent to a node y (2) which is a left subtree of x, we rotate y such that it becomes parent to x while x becomes right subtree to y.
We have one step left after rotating. We need to re-colour our nodes. The only configuration we can do to conform to our rules, is to re-colour Node(2) to black, to match the node at its same depth, and Node(3) to red, to match the other node at its same depth.
There are other rotations possible. With left-rotate, we do a reflection of right-rotate. With left-right-rotate, we do left-rotate first, then right-rotate. This will typically be of a lower subtree first, then a higher subtree. With right-left-rotate, we do right-rotate first, then left-rotate, essentially a reflection of left-right-rotate.