Red Black Tree is a binary search tree. With extra property with each node having color either RED or BLACK.
Note: Height of RB tree is θ(logn).
Insertion:
Insertion in RB tree is little tricky as compared to BST, we have following cases to insert a node in RB tree:
When node x is in right side of parent and uncle is in left side of grand parent of x, second image is solution of problem shown in first image:
Case 2: When uncle has black color (Zig-Zag Rotation)
When x is in right side of its parent and uncle is in right side of x's grandparent.
When x is in left side of its parent and uncle is in left side of x's grandparent.
Java Code for Insertion:
Code: click here
It has following properties:
- Every node is either RED or BLACK
- Root element will have BLACK color.
- Every RED node has BLACK children.
- Every path from root to leaf will have same number of BLACK nodes.
We have few theorems over RB tree:
Note: Height of RB tree is θ(logn).
Insertion:
Insertion in RB tree is little tricky as compared to BST, we have following cases to insert a node in RB tree:
- When tree is null just insert the node and it will be root, color will be BLACK.
- To insert an element first find its position:
- if key <= node.key then move to left
- else move to right
- Once we find the correct place to insert, we insert the node with color RED.
- But if the parent of the node just inserted has color RED then it will violate 3 property.
- So we have to fix this issue. We call it double RED problem, we resolve it using following few cases.
DOUBLE RED PROBLEM:
Few naming conventions used are parent, grandparent and uncle. And these conventions are inspired from real life.
Case 1: When uncle has red color
We will make the changes as shown in the figures:
When node x is in left side of parent and uncle is in right side of grand parent of x, second image is solution:
Note 1: After solving the problem it could happen that at new X double red problem could occur, so we will call our function at new X again.
Note 2: Triangles shown under X are null nodes and when problem propagates they could be trees also. But under Uncle the triangles could be null nodes or trees.
Note 2: Triangles shown under X are null nodes and when problem propagates they could be trees also. But under Uncle the triangles could be null nodes or trees.
Case 2: When uncle has black color (Zig-Zag Rotation)
After Zig-Zag Rotation
When x is in left side of its parent and uncle is in left side of x's grandparent.
After Zig-Zag Rotation
Case 3: When uncle and sibling both have black color (Zig-Zig Rotation)
When x is in left side of its parent and uncle is in right side of x's grandparent.
After Zig-Zig Rotation
When x is in right side of its parent and uncle is in left side of x's grandparent.
After Zig-Zig Rotation
Java Code for Insertion:
There are two classes and one interface:
- RBTreeFunctions - interface
- RBTree - class with functions
- RBTreeTest class - testing(Driver) class
Comments
Post a Comment