Red-Black Tree - Understanding and Implementation.
Introduction
In this article we will attempt to do the following: Gain an understanding on what a Red-Black Tree is, Get an idea on why we take the effort to reorder and recolor the RB-Tree every time we insert or remove a node, further, we will look into the algorithm for a RB-Tree insertion and removal, along with code implementation for the same in Java.
Prerequisites: Java, Binary-Search Tree, Tree rotations.
What is a Red-Black Tree?
A Red-Black Tree (RB-Tree) is a self balancing Binary-Search Tree(BS-Tree), that follows a certain algorithm while inserting and removing nodes from the tree. This is done to guarantee an O(log n) search time(where n is the number of nodes in the tree), for every element. Further along with the usual variables, the nodes of a RB Tree has a bit(or any representation) that signify it as a red or black node. These colors will add a certain order to the nodes(we will get back to this) and is necessary for the algorithm. The main properties of a RB Tree are as follows:
- The root node is always black.
- Every leaf node is a null node and is Black.
- No red node can have a red parent or child.
- All path from root to leaf should have same number of black nodes.
While inserting or removing nodes from a RB Tree we always make sure to satisfy the above properties.
Understanding search guarantee.
How does a RB-Tree guarantee O(log n) time by following the above properties? First lets take a look at property 4, this property implies there has to be an equal number of black nodes from root to leaf, but we do not worry about the number of Red nodes along any path, but, we impose a separate condition on red node in property 3, which essentially implies no adjacent nodes can be red. this implies the maximum number of red nodes is limited by black nodes along the path, since there has to be at least 1 black node between every two red node.
Keeping these facts in mind, lets assume there are b black nodes along a path(not including the null leaf node), what is the range of red nodes that one can find along the same path? You would be right, if you answered [0 to b]. This implies the maximum difference between the length of any two path will never exceed b, i.e. no path can ever be longer than twice any other path. This imposes a loose balance on the BS-Tree , that is easier to maintain than a strict balance, while also giving similar time performance to a strictly balanced BS-Tree.
A mathematical proof on the guarantee.
Let,
- n - number of nodes
- b - number of black nodes
- r - number of red nodes
- h - height of the RB-Tree
The height of a RB-Tree if it only had black nodes, would be log(b+1) (Height of a complete binary search tree with n nodes is log(n+1)), Now if we add red nodes, we can at max double the height of any path (as we established in the previous section), so the height can be shown to be:
log(b+1) <= h <= 2*log(b+1)
This implies, h = O(log(b))
We also know the search time of any key depends on the height of the tree, so we can conclude the search time of a RB-Tree will take O(log(b)) time.
Further, we know n = b + r, where r ranges from 0 to b (we can say this as an extension of the fact that this is true on a per branch basis)
this implies:
b <= n <= 2b
log(b) <= log(n) <= log(2b)
O(log(b)) = O(log(n))
Thus: h = O(log(n)), and the search time follows this.
Code structure overview.
We are going to structure the code for RB-Tree as follows:
public class RBTree<keyClass extends Comparable<keyClass>, valueClass> {
/**
* The root node of the RedBlack(RB) Tree
*/
RBNode root;
/**
* Standard constructor to initialise an empty tree with root variables.
*/
public RBTree()
{
root = null;
} //All helper function for RBTree //represents node of the RBTree public class RBNode{
private RBColor nodeColor;
private RBNode parentNode;
private RBNode leftNode;
private RBNode rightNode;
private RBDirection directionFromParent;
keyClass key;
valueClass val;
private RBNode(RBNode rbNode, RBColor nodeColor, keyClass key, valueClass val)
{
this.parentNode = rbNode;
this.nodeColor = nodeColor;
this.key = key;
this.val = val;
} //All helper functions for RBNode } } With RBDirection and RBColor being simple enumerations as follows:
public enum RBColor{
RED, BLACK
} public enum RBDirection{
LEFT, RIGHT
} Couple of points to note:
- RBNode is inside the RBTree class mostly to discourage the user from using the nodes individually, but this is mostly a choice up to the programmer, and thus comes down to design choice.
- A more efficient way to represent colors and directions would be as a bit(0 - BLACK, 1 - RED), but this has been replaced with enumerations in favor of readability and easy understanding of code.
- keyClass and valClass are called generics and can be considered as a placeholder for the type of class that is going to be stored in the tree, it can also be used to add conditions to the type of class that is going to be stored, (readers are highly encouraged to read on generics as it is an important concept for any java programmer, though, the article is still fairly understandable without the knowledge).
Insertion
The process of adding a node to a RB-Tree can be broken down to three steps:
- create a new node with color RED.
- regular BS-Tree insert
- recoloring and reordering the Tree.
recolor_and_reorder_for_insert(node):
if(root == node):
node.set_color(BLACK)
else:
parent_node = node.get_parent()
parent_color = parent_node.get_color()
if(parent_color == RED):
uncle_node = get_sibling_node(parent_node)
uncle_color = uncle_node.get_color()
grandfather_node = parent_node.get_parent()
grandfather_color = grandfather_node.get_color()
if(uncle_color == RED):
parent_node.set_color(BLACK)
uncle_node.set_color(BLACK)
if(root != grandfather_node):
grandfather_node.set_color(RED)
recolor_and_rebalance(grandfather_node)
else:
node_color = node.get_color()
//direction_from_parent returns if node is it's parent's right or left node
grandfather_to_parent_direction = parent_node.get_direction_from_parent()
node_to_parent_direction = node.get_direction_from_parent()
if(grandfather_to_parent_direction == LEFT and
node_to_parent_direction == LEFT):
right_rotate(grandfather_node)
parent_node.set_color(grandfather_color)
grandfather_node.set_color(parent_color)
else if(grandfather_to_parent_direction == LEFT and
node_to_parent_direction == RIGHT):
left_rotate(parent_node)
right_node(grandfather_node)
node.set_color(grandfather_color)
grandfather_node.set_color(node_color)
else if(grandfather_to_parent_direction == RIGHT and
node_to_parent_direction == RIGHT):
left_rotate(grandfather_node)
parent_node.set_color(grandfather_color)
grandfather_node.set_color(parent_color)
else if(grandfather_to_parent_direction == RIGHT and
node_to_parent_direction == LEFT):
right_rotate(parent_node)
left_node(grandfather_node)
node.set_color(grandfather_color)
grandfather_node.set_color(node_color)
Please refer to the example below to understand how a general re-balancing procedure work for node addition.
 |
| 1) An example of a RB-Tree with 7 nodes(not including null nodes) stored in it. |
 | ||
| 2) We insert the node "h" with the general rules we follow for a BS-Tree. You will notice the following; parent node(node "o") is RED and uncle node(a null node) is BLACK, further the parent node is LEFT of it's parent(i.e. grandparent node of inserted node, node "r"), and the node "h" is LEFT of the parent node. |
 |
| 3) We right rotate w.r.t the (former) grandfather node(node "r"). |
 |
| 4) Next, we swap the color of the parent node(node "o") and former grandfather node(node "r"). At this point the RB-Tree is done re-balancing the branches and recoloring, and it once again satisfies all the rules of RB-Tree. |
The code implementation of the algorithm looks like this(it is going to be one of the helper function of RB-Tree):
/**
* Reordering and recoloring we need to do after addition of a node(passed to this method)
* @param node
* @throws Exception
*/
private void reorderAndRecolorForInsert(RBNode node) throws Exception
{
// if the node is RED
if(RBColor.RED.equals(node.getNodeColor()))
{
// if it's a root node, color BLACK
if(root.equals(node))
{
node.setColor(RBColor.BLACK);
}
else
{
RBNode parentNode = node.getParentNode();
RBColor parentColor = parentNode.getNodeColor();
// if parent is a RED node
if(RBColor.RED.equals(parentColor))
{
RBNode uncleNode = getSiblingNode(parentNode);
RBColor uncleColor = uncleNode == null? RBColor.BLACK : uncleNode.getNodeColor();
RBNode grandFatherNode = parentNode.getParentNode();
RBColor grandFatherColor = grandFatherNode.getNodeColor();
// if uncle is a RED node
if(RBColor.RED.equals(uncleColor))
{
// set parent node as BLACK
parentNode.setColor(RBColor.BLACK);
// set uncle as BLACK
uncleNode.setColor(RBColor.BLACK);
// if grandfather is not root
if(!grandFatherNode.equals(root))
{
//set grandfather as RED
grandFatherNode.setColor(RBColor.RED);
//recur with grandfather node
reorderAndRecolorForInsert(grandFatherNode);
}
}
//uncle is a BLACK node
else
{
RBDirection directionFromGToP = parentNode.getDirectionFromParent();
RBDirection directionFromParent = node.getDirectionFromParent();
// LEFT LEFT case:
if(RBDirection.LEFT.equals(directionFromGToP) &&
RBDirection.LEFT.equals(directionFromParent))
{
// right rotate w.r.t grandfather
rightRotate(grandFatherNode);
// swap parent and grandparent colour
parentNode.setColor(grandFatherColor);
grandFatherNode.setColor(parentColor);
}
// LEFT RIGHT case:
else if(RBDirection.LEFT.equals(directionFromGToP) &&
RBDirection.RIGHT.equals(directionFromParent))
{
// left rotate w.r.t parent node
leftRotate(parentNode);
// right rotate w.r.t grand father node
rightRotate(grandFatherNode);
//swap node and grandfather colour
RBColor nodeColor = node.getNodeColor();
node.setColor(grandFatherColor);
grandFatherNode.setColor(nodeColor);
}
// RIGHT RIGHT case: (mirror of LEFT LEFT case)
else if(RBDirection.RIGHT.equals(directionFromGToP) &&
RBDirection.RIGHT.equals(directionFromParent))
{
leftRotate(grandFatherNode);
parentNode.setColor(grandFatherColor);
grandFatherNode.setColor(parentColor);
}
// RIGHT LEFT case: (mirror of LEFT RIGHT case)
else
{
rightRotate(parentNode);
leftRotate(grandFatherNode);
RBColor nodeColor = node.getNodeColor();
node.setColor(grandFatherColor);
grandFatherNode.setColor(nodeColor);
}
}
}
}
}
// throw error if the new node is not RED
else
{
throw new Exception("Only red nodes can be inserted.");
}
}
Note:
- The (LEFT, RIGHT), (LEFT, LEFT), (RIGHT, LEFT), (RIGHT, RIGHT) cases all represent the (direction of parent from grandfather, direction of inserted node from the parent)
Deletion
Before we get into node deletion, it would be better to explain two important concepts that will be used:
- Double black node: When a black node is deleted and replaced by a black child, we mark the child as a "double black" node.
- In-order successor: simply put, if, we pop all the nodes of the tree and order it in ascending order(or whatever comparison is used to add a node to the right side of a node), the in-order successor of a node is the node that comes immediately after it, for example: a tree gives a list 2,5,12,87,99,106, the in-order successor of 12 is 87. Though, finding the in-order successor in a tree will be slightly more complicated, a complication we overlooked, when we assumed the tree has been "popped" to give all the elements in an ordered manner. The algorithm for finding in-order successor is as follows:
in_order_successor(node):
if node.has_right_child():
temp_node = node.get_right_node()
while temp_node.has_left_child():
temp_node = temp_node.get_left_node()
return temp_node
else:
if node.is_left_child():
return node.get_parent()
else if node.is_right_child():
temp_node = node.get_parent()|
while temp_node.is_right_child():
temp_node = temp_node.get_parent_node()
if temp_node.is_left_child():
return temp_node.get_parent_node()
else:
return null
else:
return null
Now, let us look into node deletion, when we try to delete a node, we usually try to reduce it to the following two cases:
- Node with no child
- Node with one child
Now, what if the node had two children? We replace the node values(such as key, value pair) with that of it's in-order successor's values(effectively deleting the values to be deleted), without changing the overall tree structure (i.e. the node relations and colors remain the same, and are not copied from the in-order successor), and delete the original in-order successor node, removing the duplicate values.(The more perceptive of the readers would have realized, the BS-Tree rules are not broken when we replace a node with it's in-order successor).
Further, once we remove the node, we check if the removed node is BLACK, if so, we do the following:
- If the node has no children(i.e. 2 null nodes as children, which we usually don't count) we create a dummy null node and mark it as a double black.
- If the node has a RED child, we simply mark the child as BLACK, and attach it to the node's parent.
- If the node has a BLACK child, we mark the child as double black.
By the end of the above checks if there is a double black node, we pass it for reordering and recoloring.
The algorithm for rebalancing and recoloring of double black node is given below:
if not double_black_node == root:
parent_node = double_black_node.get_parent()
sibling_node = double_black_node.get_sibling_node()
if not sibling_node == null:
sibling_color == sibling_node.get_color()
if sibling_color == BLACK:
if sibling_node.has_atleast_one_red_child():
red_child = sibling_node.get_red_child()
if sibling_node.is_left_child() and red_child.is_left_child():
right_rotate(parent_node)
red_child.set_color(BLACK)
if parent_node.get_color() == RED:
parent_node.set_color(BLACK)
sibling_node.set_color(RED)
if sibling_node.is_left_child() and red_child.is_right_child():
left_rotate(sibling_node)
right_rotate(parent_node)
red_child.set_color(parent_node.get_color())
parent_node.set_color(BLACK)
if sibling_node.is_right_child() and red_child.is_right_child():
left_rotate(parent_node)
red_child.set_color(BLACK)
if parent_node.get_color() == RED:
parent_node.set_color(BLACK)
sibling_node.set_color(RED)
else:
right_rotate(sibling_node)
left_rotate(parent_node)
red_child.set_color(parent_node.get_color())
parent_node.set_color(BLACK)
else:
sibling_node.set_color(RED)
if parent_node.get_color() == RED:
parent_node.set_color(BLACK)
else:
//This step is to delete the double_black_node if it's a dummy null node
remove_if_dummy_null_node(double_black_node)
reorder_and_recolor_for_delete(parent_node)
else:
parent_node.set_color(RED)
sibling_node.set_color(BLACK)
if sibling_node.is_right_child():
left_rotate(parent_node)
else:
right_rotate(parent_node)
reorder_and_recolor_for_delete(double_black_node)
else:
remove_if_dummy_null_node(double_black_node)
reorder_and_recolor_for_delete(parent_node)
The final algorithm for node deletion is given below:
root = null
else if node.is_right_child():
parent_node.remove_right_child()
double_black_node = create_null_node()
parent_node.set_right_child(double_black_node)
double_black_node.set_parent(double_black_node)
else if node.is_left_child():
parent_node.remove_left_child()
double_black_node = create_null_node()
parent_node.set_left_child(double_black_node)
double_black_node.set_parent(double_black_node)
else if (not node.has_left_child()) or (not node.has_right_child()):
if node.has_left_child():
temp_node = node.get_left_child()
else:
temp_node = node.get_right_child()
if parent_node == null:
root = temp_node
temp_node.set_parent(null)
temp_node.set_color(BLACK)
else:
if node.is_right_child():
parent_node.set_right_node(temp_node)
else:
parent_node.set_left_node(temp_node)
temp_node.set_parent(parent_node)
if temp_node.get_color() == BLACK and node.get_color() == BLACK:
double_black_node = temp_node
else:
temp_node.set_color(BLACK)
else:
in_order_successor_node = in_order_successor(node)
in_order_successor_node.copy_values_to(node)
delete_node(in_order_successor_node)
if not double_black_node == null:
reorder_and_recolor_for_delete(double_black_node)
The example below will give readers an idea of how node deletion works in a RB-Tree.
 |
| 1)This is the complete graph. we want to remove node "w" from the graph. |
 |
| 2) "w" is a node with no children, so we remove it. |
 |
| 3) We add a dummy null node and mark it as "double black"(represented by the darker shade), lets call it db-node. Now we get the following case: db-node's sibling node(a.k.a "r" node) is a BLACK node with one RED child(a.k.a "t" node), and a LEFT child(of "v" node) and the parent node(a.k.a "v" node) is the right child of it's parent(a.k.a "o" node), |
 |
| 4) So we do a left rotate on the sibling node("r" node). |
 |
| 5) Then a right rotate on parent node("v" node), and color the former red child of sibling("t" node) with the color of the parent node("v" node, and the color once again being RED), and color the parent node("v" node) BLACK. |
The implementation of the above functions are given below:
/**
* Use the function to delete a given node, helper function to "remove function"
* @param node
* @throws Exception
*/
public void deleteNode(RBNode node) throws Exception
{
RBDirection nodeDirection = node.getDirectionFromParent();
RBNode leftNode = node.getLeftNode();
RBNode rightNode = node.getRightNode();
RBNode parentNode = node.getParentNode();
boolean isLeftNodeNull = leftNode == null;
boolean isRightNodeNull = rightNode == null;
RBNode doubleBlackNode = null;
//If both the child nodes are null:
if(isLeftNodeNull && isRightNodeNull)
{
if(parentNode == null)
{
root = null;
}
else if(RBDirection.LEFT.equals(nodeDirection))
{
//node deletion, removing all instances:
parentNode.setLeftNode(null);
//if it was a black node, we would change the black height of the particular branch
//so we create a node representing null node and pass it for reordering.
if(RBColor.BLACK.equals(node.getNodeColor()))
{
//null node creation, we also assign it to the double black node for later reordering/recoloring
doubleBlackNode = new RBNode(parentNode, null, null, null);
//connecting it to the parent node
parentNode.setLeftNode(doubleBlackNode);
}
}
else // if node to be deleted is a RIGHT node, mirror of LEFT
{
parentNode.setRightNode(null);
if(RBColor.BLACK.equals(node.getNodeColor()))
{
doubleBlackNode = new RBNode(parentNode, null, null, null);
parentNode.setRightNode(doubleBlackNode);
}
}
}
// if only one of the side has a child
else if(isLeftNodeNull || isRightNodeNull)
{
// find which side has the child and assign the child to tempNode for further operation
RBNode tempNode = isLeftNodeNull ? rightNode : leftNode;
// assign the child node to the parent node of the node to be deleted (effectively cutting it off from the tree)
if(parentNode == null)
{
root = tempNode;
tempNode.setParentNode(null);
tempNode.setColor(RBColor.BLACK);
}
else
{
if (RBDirection.LEFT.equals(nodeDirection))
{
parentNode.setLeftNode(tempNode);
}
else
{
parentNode.setRightNode(tempNode);
}
tempNode.setParentNode(parentNode);
// if both the node to be deleted and the child node are black nodes, a double black node is formed
// assign it to the doubleBlackNode variable for further reordering and recoloring
if (RBColor.BLACK.equals(tempNode.getNodeColor()) && RBColor.BLACK.equals(node.getNodeColor()))
{
doubleBlackNode = tempNode;
}
else // else, if only one of the nodes is BLACK, just make sure the child node is BLACK
{
tempNode.setColor(RBColor.BLACK);
}
}
}
else // if the node to be deleted has both the children as not null.
{
// find the inorder successor of the node
RBNode inOrderSuccessorNode = inOrderSuccessor(node);
// we replace the values of the node to be deleted with the values of the in order successor
inOrderSuccessorNode.copyTo(node);
// then delete the actual inorder successor node
deleteNode(inOrderSuccessorNode);
}
// if the doubleBlackNode is assigned a value, we still have recolouring and reordering to do.
if(doubleBlackNode != null)
{
reorderAndRecolorForDelete(doubleBlackNode);
}
}
/**
* The helper function to reorder and recolor the RB tree once a node is deleted and double black node exists.
* @param doubleBlacknode
* @throws Exception
*/
private void reorderAndRecolorForDelete(RBNode doubleBlacknode) throws Exception
{
// make sure the node passed is not root node, as root nodes can have
if(root != null && !root.equals(doubleBlacknode))
{
RBNode parentNode = doubleBlacknode.getParentNode();
RBNode siblingNode = getSiblingNode(doubleBlacknode);
if(siblingNode != null) {
RBColor siblingColor = siblingNode.getNodeColor();
// if sibling was BLACK
if (RBColor.BLACK.equals(siblingColor)) {
RBNode siblingRightNode = siblingNode.getRightNode();
RBNode siblingLeftNode = siblingNode.getLeftNode();
RBDirection siblingDirection = siblingNode.getDirectionFromParent();
// if atleast one of the children node is RED(null is considered BLACK)
if ((siblingLeftNode != null && RBColor.RED.equals(siblingLeftNode.getNodeColor())) ||
(siblingRightNode != null && RBColor.RED.equals(siblingRightNode.getNodeColor())))
{
//assign the RED child to the variable:
RBNode redChild = (siblingLeftNode != null && RBColor.RED.equals(siblingLeftNode.getNodeColor())) ?
siblingLeftNode : siblingRightNode;
RBDirection redChildDirection = redChild.getDirectionFromParent();
// LEFT LEFT case:
if (siblingDirection.equals(RBDirection.LEFT) && redChildDirection.equals(RBDirection.LEFT))
{
//rotate right with respect to parent node.
rightRotate(parentNode);
//assign BLACK to child node
redChild.setColor(RBColor.BLACK);
//if parent node was RED
if (RBColor.RED.equals(parentNode.getNodeColor())) {
//set parent node as BLACK
parentNode.setColor(RBColor.BLACK);
//set sibling node as RED
siblingNode.setColor(RBColor.RED);
}
}
// LEFT RIGHT case:
else if (siblingDirection.equals(RBDirection.LEFT) && redChildDirection.equals(RBDirection.RIGHT))
{
//left rotate with respect to the sibling node
leftRotate(siblingNode);
//right rotate with respect to the parent node
rightRotate(parentNode);
//the red child should be assigned the colour of the (sibling's) parent node
redChild.setColor(parentNode.getNodeColor());
//assign BLACK to parent node
parentNode.setColor(RBColor.BLACK);
}
// RIGHT RIGHT case: (mirror of LEFT LEFT case)
else if (siblingDirection.equals(RBDirection.RIGHT) && redChildDirection.equals(RBDirection.RIGHT))
{
leftRotate(parentNode);
redChild.setColor(RBColor.BLACK);
if (RBColor.RED.equals(parentNode.getNodeColor())) {
parentNode.setColor(RBColor.BLACK);
siblingNode.setColor(RBColor.RED);
}
}
// RIGHT LEFT case: (mirror of RIGHT LEFT case)
else
{
rightRotate(siblingNode);
leftRotate(parentNode);
redChild.setColor(parentNode.getNodeColor());
parentNode.setColor(RBColor.BLACK);
}
}
// no red children
else
{
// assign RED to the sibling node
siblingNode.setColor(RBColor.RED);
// if parent node is RED
if (RBColor.RED.equals(parentNode.getNodeColor()))
{
// set parent as BLACK
parentNode.setColor(RBColor.BLACK);
}
else
{
// remove dummy null nodes from the tree
if(doubleBlacknode.getNodeColor() == null)
{
disconnectNode(doubleBlacknode);
}
//recur with the parent node
reorderAndRecolorForDelete(parentNode);
}
}
}
// if sibling was RED
else
{
// set parent node as RED
parentNode.setColor(RBColor.RED);
// set sibling node as BLACK
siblingNode.setColor(RBColor.BLACK);
// if sibling was parent's RIGHT child
if(RBDirection.RIGHT.equals(siblingNode.getDirectionFromParent()))
{
// rotate left w.r.t parent node
leftRotate(parentNode);
}
else // sibling was LEFT child
{
// rotate RIGHT w.r.t parent node
rightRotate(parentNode);
}
//recur with the double black node from start
reorderAndRecolorForDelete(doubleBlacknode);
}
}
else // if no sibling nodes exists:
{
// delete the double black node if it was a dummy node created to represent a null node
if(doubleBlacknode.getNodeColor() == null)
{
disconnectNode(doubleBlacknode);
}
// recur the function call for its parent
reorderAndRecolorForDelete(parentNode);
}
}
//if passed node is a dummy representation of a null node, delete it
if(doubleBlacknode.getNodeColor() == null)
{
disconnectNode(doubleBlacknode);
}
} /**
* Used to disconnect a node from its parent.(helper function)
* @param node
*/
private void disconnectNode(RBNode node)
{
RBNode parentNode = node.getParentNode();
if(parentNode != null)
{
if(RBDirection.LEFT.equals(node.getDirectionFromParent()))
{
parentNode.setLeftNode(null);
}
else
{
parentNode.setRightNode(null);
}
node.setParentNode(null);
}
}
/**
* returns inorder succesor of a node (null if no succesor).
* @param node
* @return
*/
public RBNode inOrderSuccessor(RBNode node)
{
RBNode rightNode = node.getRightNode();
// if right node exists
if(rightNode != null)
{
RBNode tempNode = rightNode;
// go left of the node until the end and save the node
while(tempNode.getLeftNode() != null)
{
tempNode = tempNode.getLeftNode();
}
// return the left most node
return tempNode;
}
// if no right node exists
else
{
// then its parent is the in order successor, if its a LEFT node
if(RBDirection.LEFT.equals(node.getDirectionFromParent()))
{
return node.getParentNode();
}
// if its a RIGHT node
else
{
RBNode tempNode = node.getParentNode();
// go up the parent node until the node is no longer a RIGHT node
while(RBDirection.RIGHT.equals(tempNode.getDirectionFromParent()))
{
tempNode = tempNode.getParentNode();
// if the parent node doesnt exist(it means, it is the greatest element in the tree)
if(tempNode == null)
{
return null;
}
}
// if the following node is a LEFT node, its parent is the in order successor
return tempNode.getParentNode();
}
}
}
Note:
- We have chosen to not represent any of the null nodes as actual part of the tree, so, when needed to represent a double black null node, We create a dummy null node, which we later delete once it's use is over, since we don't want our tree to actually have any null nodes. This is where disconnect_node method plays it's roll by disconnecting the dummy null node from our tree. We make sure to set the color of the dummy null node as "null", allowing us to quickly detect a dummy null node.
Conclusion
So, there you have the working of a RB-Tree, for the full code(including some test files) please visit my Git-hub page, further, all the RB-Tree images were obtained from here. RB-Tree is just one of the many types of data structures used in various places for efficient storing of ordered data, My next project will make use of RB-Tree and intends to show one of it's use case while also explaining a different concept, hope to see you there!
Comments
Post a Comment