Simple Red-Black Trees
What is a red black tree?
A red-black tree is a type of binary search tree. It is self balancing like the AVL tree, although it uses different properties to maintain the state of being balanced. Balanced binary search trees are much more efficient at search than unbalanced binary search trees, so the complexity needed to maintain balance is often worth it. With a single search a balanced binary search trees time complexity is O(log (n)), meaning it scales well with a large input because you don't have to search each and every node in the tree. Meanwhile that is the case with an unbalance binary search tree with a time complexity of O(n). The main reason they’re called red-black trees because each node in the tree is labeled as red or black.
Of course, the nodes aren’t actually colored. Each node simply has a flag to indicate whether it is considered red or black. Instead of the colors, I find it more useful to consider each node to be a toll booth. As you travel from the root to one of the null references (an exit), you have to pay $1 at each black toll booth, but the red toll booths are free. The “equal exit cost” rule says that the cost of the trip is the same, no matter which exit you choose.
Properties
Coloring a node just isn’t enough to make a red-black tree it must maintain these properties:
- Every node is colored with either red or black.
- The root must be black
- The red nodes can never appear in a row within a tree,
- Both children of a red node must be black nodes, the parent or the red node must be a black node
- Every path from a node to a descendant leaf has the same number of black nodes.
Operations(Inserting, Deleting)
In a red-black tree there are two operations that can change the structure of the tree, which are insert and deleting a node. For inserting a node, first we have to search through the tree and insert it as a red node at the right spot. This also might violate the properties that the tree must maintain as the parent of the red node we’re inserting might be a red node. So to handle insertion and deletion there are cases we must account for.
Inserting
When inserting a node int a tree we must maintain the trees properties. We have to search through the tree to find the spot to insert it at. Then we color the node red. After the node is inserted in the correct place we check if the trees properties; restore them if any properties we’re violated.
Restoration
If we do need to restore tree’s properties there are two main steps:
- Recoloring, changing a node from red to black or vice versa
- Rotations, alters the subtree of a tree by rearranging subtrees. The goal of the rotations is to reduce the height of the tree.
Rotations
When altering a subtree there are two options when it comes to rotations: Left and Right. As it depicts in the diagram below the in the left rotation the right child of the root node becomes the new head and the left side shifts down. Whereas in a right rotation the left child becomes the new head and the right side shifts down.
Deletion
The amazing part of deletion is that it follows the same rule set as insertion. It relies on the same cases that insert relies on.
In Conclusion
Red-black trees are binary search trees that store one additional piece of information in each node (the node’s color) and satisfy three properties. These properties deal with the way nodes can be colored (the root property and the red property) and the number of black nodes along paths from the root node to a null child pointer (the black property). Although it is not intuitively obvious, the algorithms for restoring these properties after a node has been added or removed result in a tree that stays balanced.
While the lookup method is identical for binary search trees and red-black trees, the insert and delete methods are more complicated for red-black trees. The insert method initially performs the same insert algorithm as is done in binary search trees and then must perform steps to restore the red-black tree properties through restructuring and recoloring.
