Just like AVL tree, red black tree is another way to to make binary search tree balanced. If you don't familiar with AVL tree, please check my previous article first.
In AVL tree, we calculate each node's height, and use it to decide if rebalance operations are needed and also to decide which rebalance operations to take. In red black tree, we don't need to calculate the height, but we label each node as red or black, and use this label to decide if rebalance operations are needed and which rebalance operations to take. Now let's dig into the details.
First, let see the node structure.
class RedBlackNode {
data: number;
left: RedBlackNode | null;
right: RedBlackNode | null;
parent: RedBlackNode | null;
isRed: boolean;
isLeft: boolean;
constructor(data: number) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.isRed = true; // new node are red
this.isLeft = true; // this will be updated when inserting
}
};
As you can see, 3 attributes are added. Attribute parent is used to store current node's parent. Attribute isRed is used to lable the node. Attribute isLeft indicates if current node is left child or right child.
Then comes the insert operation, this is pretty standard.
insert(data: number) {
const node = new RedBlackNode(data);
if (this.root === null) {
this.root = node;
} else {
this._insert(this.root, node);
}
this._rebalance(node);
}
private _insert(parent: RedBlackNode, node: RedBlackNode) {
if (node.data < parent.data) {
if (parent.left === null) {
node.isLeft = true;
node.parent = parent;
parent.left = node;
} else {
this._insert(parent.left, node);
}
} else {
if (parent.right === null) {
node.isLeft = false;
node.parent = parent;
parent.right = node;
} else {
this._insert(parent.right, node);
}
}
}
Two things needed to be noted here. First is that when we insert a node, we need to set the ifLeft and parent attributes properly. Second, when the node is inserted into the tree, we call the _rebalance function to rebalance the tree.
Now comes the rebalance part. On which conditions should we do the rebalance operations? Actually, there are only 3 steps:
- if current node is the root node, then make node as black
- if current node is red, and its parent is also red, then do rebalance operations
- do first 2 steps recursively
So in code, process is like this.
private _rebalance(node: RedBlackNode) {
if (node.parent === null) {
node.isRed = false;
return;
}
if (node.isRed && node.parent.isRed && node.parent.parent !== null) {
// ....
}
this._rebalance(node.parent);
}
The rebalance operations include 2 parts in red black tree: rotation and color flipping. Rotation part is almost the same to AVL tree, except for handling the new attributes(parent, isLeft, isRed). Color flopping is an operation to change node's label(red or black).
We need to know current node's aunt's label, then we can decide which operations to take. For example, if current node is d, then its aunt is b.
/**
* a
* b c
* d
*
* d is node, b is aunt
*/
Then let's see this code flow.
let aunt: RedBlackNode | null = null;
if (node.parent.isLeft) {
aunt = node.parent.parent.right;
} else {
aunt = node.parent.parent.left;
}
// operations according to aunt
if (aunt === null || !aunt.isRed) {
this._rotate(node);
} else {
// color flip
// parent => black
// grandparent => red
// aunt => black
if (aunt !== null) {
aunt.isRed = false;
}
node.parent.parent.isRed = true;
node.parent.isRed = true;
}
Next is the rotation part. We know that in AVL tree, there are 4 types of rotations, same things for red black tree. But apart from that, there 1 more thing needed to be noted: after rotation, a color flipping operation is needed.
private _rotate(c: RedBlackNode): void {
const b = c.parent;
if (b === null) return;
const a = b.parent;
if (a === null) return;
if (c.isLeft) {
if (b.isLeft) {
/**
* a
* b
* c
*
* c is the node
*
* after rotation, tree becomes
*
* b
* c a
*
* make c and a red, b black
*/
this._rightRotate(a);
this._flipColor(b, c, a);
} else {
/**
* a
* b
* c
*
* c is the node
*
* right rotate by b
*
* a
* c
* b
*
* left rotate by a
*
* c
* a b
*
* make a and b red, c black
*
*/
this._rightRotate(b);
this._leftRotate(a);
this._flipColor(c, a, b);
}
} else {
if (!b.isLeft) {
/**
* a
* b
* c
*
* c is the node
*
* after rotation, tree becomes
*
* b
* a c
*
* make a and c red, b black
*/
this._leftRotate(a);
this._flipColor(b, a, c);
} else {
/**
* a
* b
* c
*
* c is the node
*
* left rotate by b
*
* a
* c
* b
*
* right rotate by a
*
* c
* b a
*
* make b and a red, c black
*/
this._leftRotate(b);
this._rightRotate(a);
this._flipColor(c, b, a);
}
}
}
Now comes the last part, the left and right rotation. Main idea is the same as AVL tree, but remember to handling the extra attrubites properly.
/**
* a
* b
* c x
*
* =>
*
* b
* c a
* x
*/
private _rightRotate(a: RedBlackNode) {
if (a.left === null) return;
// handle x
const b = a.left;
const x = b.right;
a.left = x;
if (x !== null) {
x.isLeft = true;
x.parent = a;
}
// handle b
const parent = a.parent;
b.parent = parent;
if (parent === null) {
this.root = b;
} else {
if (a.isLeft) {
parent.left = b;
b.isLeft = true;
} else {
parent.right = b;
b.isLeft = false;
}
}
// handle a
a.isLeft = false;
a.parent = b;
b.right = a;
}
/**
* a
* b
* x c
*
* =>
*
* b
* a c
* x
*
*/
private _leftRotate(a: RedBlackNode) {
if (a.right === null) return;
// handle x
const b = a.right;
const x = b.left;
a.right = x;
if (x !== null) {
x.isLeft = false;
x.parent = a;
}
// handle b
const parent = a.parent;
b.parent = parent;
if (parent === null) {
this.root = b;
} else {
if (a.isLeft) {
parent.left = b;
b.isLeft = true;
} else {
parent.right = b;
b.isLeft = false;
}
}
// handle a
a.isLeft = true;
a.parent = b;
b.left = a;
}
OK, that is the whole process. Let see all the code.
class RedBlackNode {
data: number;
left: RedBlackNode | null;
right: RedBlackNode | null;
parent: RedBlackNode | null;
isRed: boolean;
isLeft: boolean;
constructor(data: number) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.isRed = true; // new node are red
this.isLeft = true; // this will be updated when inserting
}
};
class RedBlackTree {
private root: RedBlackNode | null = null;
insert(data: number) {
const node = new RedBlackNode(data);
if (this.root === null) {
this.root = node;
} else {
this._insert(this.root, node);
}
this._rebalance(node);
}
private _insert(parent: RedBlackNode, node: RedBlackNode) {
if (node.data < parent.data) {
if (parent.left === null) {
node.isLeft = true;
node.parent = parent;
parent.left = node;
} else {
this._insert(parent.left, node);
}
} else {
if (parent.right === null) {
node.isLeft = false;
node.parent = parent;
parent.right = node;
} else {
this._insert(parent.right, node);
}
}
}
private _rebalance(node: RedBlackNode) {
if (node.parent === null) {
node.isRed = false;
return;
}
if (node.isRed && node.parent.isRed && node.parent.parent !== null) {
/**
* a
* b c
* d
*
* d is node, b is aunt
*/
let aunt: RedBlackNode | null = null;
if (node.parent.isLeft) {
aunt = node.parent.parent.right;
} else {
aunt = node.parent.parent.left;
}
if (aunt === null || !aunt.isRed) {
this._rotate(node);
} else {
// color flip
// parent => black
// grandparent => red
// aunt => black
if (aunt !== null) {
aunt.isRed = false;
}
node.parent.parent.isRed = true;
node.parent.isRed = false;
}
}
this._rebalance(node.parent);
}
private _rotate(c: RedBlackNode): void {
const b = c.parent;
if (b === null) return;
const a = b.parent;
if (a === null) return;
if (c.isLeft) {
if (b.isLeft) {
/**
* a
* b
* c
*
* c is the node
*
* after rotation, tree becomes
*
* b
* c a
*
* make c and a red, b black
*/
this._rightRotate(a);
this._flipColor(b, c, a);
} else {
/**
* a
* b
* c
*
* c is the node
*
* right rotate by b
*
* a
* c
* b
*
* left rotate by a
*
* c
* a b
*
* make a and b red, c black
*
*/
this._rightRotate(b);
this._leftRotate(a);
this._flipColor(c, a, b);
}
} else {
if (!b.isLeft) {
/**
* a
* b
* c
*
* c is the node
*
* after rotation, tree becomes
*
* b
* a c
*
* make a and c red, b black
*/
this._leftRotate(a);
this._flipColor(b, a, c);
} else {
/**
* a
* b
* c
*
* c is the node
*
* left rotate by b
*
* a
* c
* b
*
* right rotate by a
*
* c
* b a
*
* make b and a red, c black
*/
this._leftRotate(b);
this._rightRotate(a);
this._flipColor(c, b, a);
}
}
}
private _flipColor(root: RedBlackNode, left: RedBlackNode, right: RedBlackNode): void {
root.isRed = false;
left.isRed = true;
right.isRed = true;
}
/**
* a
* b
* c x
*
* =>
*
* b
* c a
* x
*/
private _rightRotate(a: RedBlackNode) {
if (a.left === null) return;
// handle x
const b = a.left;
const x = b.right;
a.left = x;
if (x !== null) {
x.isLeft = true;
x.parent = a;
}
// handle b
const parent = a.parent;
b.parent = parent;
if (parent === null) {
this.root = b;
} else {
if (a.isLeft) {
parent.left = b;
b.isLeft = true;
} else {
parent.right = b;
b.isLeft = false;
}
}
// handle a
a.isLeft = false;
a.parent = b;
b.right = a;
}
/**
* a
* b
* x c
*
* =>
*
* b
* a c
* x
*
*/
private _leftRotate(a: RedBlackNode) {
if (a.right === null) return;
// handle x
const b = a.right;
const x = b.left;
a.right = x;
if (x !== null) {
x.isLeft = false;
x.parent = a;
}
// handle b
const parent = a.parent;
b.parent = parent;
if (parent === null) {
this.root = b;
} else {
if (a.isLeft) {
parent.left = b;
b.isLeft = true;
} else {
parent.right = b;
b.isLeft = false;
}
}
// handle a
a.isLeft = true;
a.parent = b;
b.left = a;
}
print() {
const q: (RedBlackNode | null)[] = [];
q.push(this.root);
while (true) {
const len = q.length;
for (let i = 0; i < len; i++) {
const v = q[i];
if (v !== null) {
q.push(v.left, v.right);
} else {
q.push(null, null);
}
}
const level = q.splice(0, len);
console.log(level.map(v => v === null ? "x" : `${v.isRed ? 'r' : 'b'}(${v.data})`).join(" "));
if (q.every(v => v === null)) break;
}
}
}
Then make some tests.
const t = new RedBlackTree();
t.insert(1);
t.insert(2);
t.insert(3);
t.insert(4);
t.insert(5);
t.insert(6);
t.insert(7);
t.insert(8);
t.insert(9);
t.print();
/**
b(4)
r(2) r(6)
b(1) b(3) b(5) b(8)
x x x x x x r(7) r(9)
*/