Understanding Red-Black Trees by Ethr
Links
These pages helped me understand how to transform a Binary Search Tree into a red-black tree.
Code
Explaination
Rules
1. A node is either red or black.
2. The root is black.
3. All leaves are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
Setup consideration
Make sure that your implentation of nodes/leaves has a flag for the colour, either red or black.
Insertion
All nodes are inserted as red (except for the root node which is a special case and inserted as black). After insertion, you have to check the rules making rotations and/or colour changes to correct the tree sometimes moving up the tree until you reach the root.
The trick is sto break rule 4 then fix it again.
Rotations
Rotations are essential in any balancing algorithm. Knowing when to use them is another thing.
Right: To rotate right, push node X down and to the right. Node X's left child replaces X, and the left child's right child becomes X's left child.
Left: To rotate left, push node X down and to the left. Node X's right child replaces X, and the right child's left child becomes X's right child.
Remember to set the parent of the side node to x's former parent and if x was the root to set that correctly otherwise set the parent node's 'left' or 'right' variables to point to x's former side node.
Balancing
Algorithm:
- Take a reference to the node added and call it 'x'
- Until x's parent is black performing balancing (x however can change to point at different nodes.
The direction of rotations and moves depends on the location of the parent of the node added to the its parent.
I'm going to describe what to do if the node is on the left. To do this on the right, simply exchange sides.
Look at the grandparents right child, if its red:
- parent goes to black
- gp r c goes to black
- grandparent goes to red
- x = grandparent, go to next iteration of balancing (move up the tree)
else:
- if new node added is on the right of its parent:
-- x = parent (move up the tree)
-- rotate left on x
- endif
- x's parent goes to black
- x's grandparent goes to red
- rotate right on the grandparent
- go to next iteration of balancing
After balancing set the root to black.
These pages helped me understand how to transform a Binary Search Tree into a red-black tree.
Code
Explaination
Rules
1. A node is either red or black.
2. The root is black.
3. All leaves are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
Setup consideration
Make sure that your implentation of nodes/leaves has a flag for the colour, either red or black.
Insertion
All nodes are inserted as red (except for the root node which is a special case and inserted as black). After insertion, you have to check the rules making rotations and/or colour changes to correct the tree sometimes moving up the tree until you reach the root.
The trick is sto break rule 4 then fix it again.
Rotations
Rotations are essential in any balancing algorithm. Knowing when to use them is another thing.
Right: To rotate right, push node X down and to the right. Node X's left child replaces X, and the left child's right child becomes X's left child.
Left: To rotate left, push node X down and to the left. Node X's right child replaces X, and the right child's left child becomes X's right child.
Remember to set the parent of the side node to x's former parent and if x was the root to set that correctly otherwise set the parent node's 'left' or 'right' variables to point to x's former side node.
Balancing
Algorithm:
- Take a reference to the node added and call it 'x'
- Until x's parent is black performing balancing (x however can change to point at different nodes.
The direction of rotations and moves depends on the location of the parent of the node added to the its parent.
I'm going to describe what to do if the node is on the left. To do this on the right, simply exchange sides.
Look at the grandparents right child, if its red:
- parent goes to black
- gp r c goes to black
- grandparent goes to red
- x = grandparent, go to next iteration of balancing (move up the tree)
else:
- if new node added is on the right of its parent:
-- x = parent (move up the tree)
-- rotate left on x
- endif
- x's parent goes to black
- x's grandparent goes to red
- rotate right on the grandparent
- go to next iteration of balancing
After balancing set the root to black.