Red-Black Tree
A red-black tree is a kind of binary search tree that solves the "balancing" problem. It contains a bit of extra logic to ensure that as nodes are inserted and deleted, the tree remains relatively balanced.
Click to play video
How It Works
Each node in an RB Tree stores an extra bit, called the "color": either red or black. The "color" ensures that the tree remains approximately balanced during insertions and deletions. When the tree is modified, the new tree is rearranged and repainted to restore the coloring properties that constrain how unbalanced the tree can become in the worst case.
The "red" and "black" nomenclature is arbitrary - you could call them "red vs blue" trees (shout-out rooster teeth), or not even call it "color" at all. The important part is just that we now have two "types" of nodes and that will affect the algorithm for balancing it.
List of Very Simple Rules
- Each node is either red or black.
- The root is black.
- All Nil leaf nodes are black.
- If a node is red, then both its children are black.
- All paths from a single node go through the same number of black nodes to reach any of its descendant Nil (black) nodes.
Assignment
As it turns out, we've been inserting user records into our tree with incrementing numerical IDs (pre sorted data)! The app's user lookups are starting to get really slow. Let's start implementing a Red-Black tree to speed things up.
In a normal BST, the child nodes don't need to know about, or carry a reference to their parent. The same is not true for Red-Black trees.
The RBNode class is already implemented for you, as well as the __init__ constructor method of the RBTree class. There's also a data member, self.nil created for you in the constructor. self.nil contains the value we'll use to designate all the nil (empty) leaf nodes, which are used for rebalancing purposes but contain no "actual" value.
Complete the insert method. It should take a value as input and add the value as a new node in the tree if the value doesn't already exist.
We're done for now! We've really just made another (more complicated) regular binary tree, seeing as it's not a fully-fledged red-black tree yet... but these upgrades will allow us to implement the rest of the logic in the next few lessons.
So far we've added:
- a
parentpointer from child to parent (so children know who their parents are) - the mechanisms for coloring the nodes, but have defaulted them all to
redfor now
Tip
I'd highly recommend using pencil/paper or some kind of drawing tool to visualize the tree as you go through the assignments in this chapter.