A red-black tree is a binary search tree that has an extra bit of information for each node: its color, which can be red or black. Each node of the tree contains the fields color, key, left, right and parent. If the parent or any of the left or right children does not exist, the respective field is set to null.
A binary search tree is red-black tree if it meets the following properties:
- Each node is either red or black.
- The root is always black.
- If a node is red then both is children must be black.
- Every path from a node to a leaf contains the same number of black nodes.
We will refer to the number of these properties later in our examples, so it is good to know them.
Here is an example of a red-black tree:
The number of black nodes on any path from a node down to a leaf node will be called the black height of the node. The notion of black height is well defined on the basis of property 4, according to which all paths from a node to a leaf have the same number of black nodes. We define the black height of a red-black tree as the black height of its root.
This means that whenever a new node is inserted into the tree it will not become significantly unbalanced, because the properties need to be maintained, which is the major advantage of using this type of data structure. Let’s now look at some operations that can be performed on red-black trees:
- When we execute insertions and deletions on a red-black tree with n nodes, it could happen that some of the properties of this data structure are not respected. In order to restore these properties, the colors of some of the nodes in the tree and the pointer structure need to be changed.
The structure of the pointers is changed by rotation. There are two types of rotation: left and right rotation. In order to be able to perform a right rotation on a node x, the left child of the node must not be null. The tree is then rotated to the right, so in our example 8 becomes the right child of 4. If the left child of the initial root already had a right child (in our case it did – 5), we make its right child the left child of the initial root (the left child of 8 in our example). Finally, all the nodes that are located on a different level in the rotated tree change their color (in our example, all of them, except 5). The process of left rotation is symmetrical to the left rotation. The following image describes these two techniques:
- Inserting a node in a red-black tree with n nodes can be done in timeO (log n). We will firstly used the procedure of inserting into a binary search tree to insert a node x in the tree. Next, we will color x with red. To guarantee the preservation of the red-black properties, we recover the resulting tree by node re-coloring and by performing rotations. After insertion only the third property can be broken, which states that a red colored node cannot have a child colored in red. Specifically,property 3 is violated if the parent of x is red. There are a couple of cases to consider:
a). If the parent of the newly inserted node is red, then this must mean that its parent is black, because the tree was a red-black tree before. In this case we color both the inserted node and its parent with black, then color the grandparent of the newly inserted node with red, in order to preserve the fourth property. For example, if we were to insert ‘1’ in the tree shown in the picture above in the right, we would firstly insert it to the left of ‘2’. We would then color both 1 and 1 in black and 4 in red.
b). If the parent of the newly inserted node is black, then we can keep the red color of the node, because it does not break the fourth property.
For example, if we were to insert 9 in the red-black tree above, we would firstly follow the insertion procedure that applies to regular binary search trees and obtain the following tree, which violates properties 3 and 4:
All we need to do now is change the color of 9, which will restore all the properties of a red-black tree:
- Deletion in red-black trees is not much more complicated than insertion.
- If the node we want to remove is red then we would still end up with a red-black tree after its deletion. This means we can use exactly the same algorithm as with regular binary search trees.
- If the node we want to remove is black its descendants must be given another black ancestor in order not to break the fourth property. If both descendants are red then we can color the one that will replace the black node removed in black. If not, we will need to restructure the tree.
For example, suppose we want to delete the root of our red-black tree above. Following the steps described in the section corresponding to regular binary search trees, we delete the root’s key and replace it with the largest value in the left sub-tree (in this case 5), as follows:
This tree does not violate any of the four properties, so this time we do not need to change colors.
The key thing to remember about red-black trees is that they enable the implementation of all dictionary operations in O(log n). The four properties discussed make this data structure more balanced than regular binary search trees.
RED-BLACK Trees Data Structure in Java
RED-BLACK Trees Data Structure in PHP
RED-BLACK Trees Data Structure in C++
RED-BLACK Trees Data Structure in Python
RED-BLACK Trees Data Structure in Ruby