Let’s try and de-mystify Red Black trees.
It’s basically a binary-search tree with an additional property, color. Having this property makes it possible to “approximately” balance it. By approximately balance, I mean that going from root to leaf, there’s no path that is twice as long as any other. Let’s first define the structure of RB-tree node as shown on below.
We also use a sentinel node as leaf node to help with the tree fix-up operations. So, all leaf nodes in a RB-Tree are sentinels.
extern RBNode sentinel;
extern RBNode* root;
struct RBNode
{
RBNode(size_t size) : m_size(size) {}
RBNode* m_parent = &sentinel;
RBNode* m_left = &sentinel;
RBNode* m_right = &sentinel;
size_t m_size = { 0 };
bool m_isRed = false;
};
A Red-Black tree must satisfy following properties:
– Every node is red or black.
– The root of the node should be black.
– Every leaf should be black.
– Children of a red node should be black.
– For each node, all paths from node to it’s leaves should contain same number of black nodes.
During the course of Insertion and deletion operations, various properties of out RB-Tree might be violated. We shall use Left and Right rotations to restore those traits.
When left-rotating, X should already contain a right-child(Y). Y’s right node will not change and X’s left node will not change.
void LeftRotate(RBNode* x)
{
// Pre-condition that must be satisfied here is that
// X already has a valid right child(Y).
// Y takes X's place
//Move parents
RBNode* y = x->m_right;
y->m_parent = x->m_parent;
x->m_parent = y;
if(y->m_parent == &sentinel){ root = y; }
else if(y->m_parent->m_right == x){ y->m_parent->m_right = y; }
else { y->m_parent->m_left = y; }
//x becomes y's left node. y's left node becomes x's right node
x->m_right = y->m_left;
if(x->m_right != &sentinel) { x->m_right->m_parent = x; }
y->m_left = x;
}
When right-rotating, X should already contain a left-child(Y). Y’s left node will not change and X’s right node will not change.
void RightRotate(RBNode* x)
{
// Pre-Condition that must be satisfied here
// is that X has a vaild left node(Y).
// Y takes X's place
RBNode* y = x->m_left;
y->m_parent = x->m_parent;
x->m_parent = y;
if(y->m_parent == &sentinel){ root = y; }
else if(y->m_parent->m_right == x) { y->m_parent->m_right = y; }
else { y->m_parent->m_left = y; }
x->m_left = y->m_right;
if(x->m_left != &sentinel) { x->m_left->m_parent = x; }
y->m_right = x;
}
One response to “Red Black Trees: A brief study with code”
Nice