preface
In this article I will introduce you to the most famous self-balanced binary search tree, the red-black tree.
Red black tree by Rudolph. Bell, a professor of information technology at the Technical University of Munich. In 1978, at Robert. Sedgwick published a paper formally naming this data structure a red-black tree and providing a complete complexity proof.
Red black trees are cumbersome, but they are very efficient in practice, because they are self-balanced (what red black trees achieve is actually a pseudo-equilibrium, which we will discuss later), so they don’t degenerate into linked lists like binary search trees do in extreme cases. You can find, insert, and delete elements at O(logN)O(logN)O(logN) O(logN). Because of its excellent performance, it is widely used in the design of some underlying data structures — for example, TreeMap and TreeSet in the Java language are red-black trees.
Let’s explore what a red-black tree is actually a data structure.
Red black tree and 2-3 tree
Before introducing the famous red-black tree, let’s take a look at data structures like 2-3 trees. Understanding 2-3 trees in advance will help us to learn about red-black trees, because red-black trees are similar to the principles of 2-3 trees, and 2-3 trees are easier to understand than complex red-black trees.
What is a 2-3 tree? First, a 2-3 tree is an absolutely balanced multi-fork tree.
We all know the concept of a balanced binary tree — a balanced binary tree is a binary search tree. It is either an empty tree, or the absolute value of the difference between the height of the left subtree and the height of the right subtree (alias: balance factor) is no more than 1, and both the left and right subtrees of a balanced binary tree are balanced binary trees.
As shown below, the tree is a balanced binary tree:
The so-called absolute balance is more strict than the balance in a balanced binary tree. Absolute balance is defined as: for any node in the tree, the height of the left and right subtrees is the same.
As shown in the figure above, the diagram represents a 2-3 tree. This tree satisfies the definition of absolute equilibrium.
In addition, the 2-3 tree is not a standard binary tree, but a multi-fork tree. In the 2-3 tree above, we can see that some nodes hold one element and some nodes hold two elements. A node with one element is called a 2-node, and a node with two elements is called a 3-node. There are only two types of nodes in a 2-3 tree, which is how the 2-3 tree gets its name.
Next, I’m going to show you how to insert elements into a 2-3 tree, and let’s take a look at the magic operation that 2-3 trees do to keep the whole tree perfectly balanced.
First, we insert a node “42” into an empty 2-3 tree, and then we insert a node “37” :
Inserting nodes into a 2-3 tree is the same as a binary search tree, but it follows another principle: new nodes are never inserted into an empty location.
If the tree is a binary search tree, node “37” will be inserted to the left of node “42”, but this breaks the absolute balance of the 2-3 trees. So, node “37” does not insert into an empty location, but merges with node “42” to become a new 3-node:
Next, we insert element “12” into the 2-3 tree:
According to our principle that “new nodes are never inserted into an empty location”, node “12” will merge with the current 3-node to become a “4-node” :
This 4-node is then split into three 2-nodes to maintain absolute equilibrium and follow the definition of a 2-3 tree:
We continue to insert the element “18” into the current 2-3 tree:
Insert element “6” into the current 2-3 tree:
Insert element “11” into the current 2-3 tree:
Insert element “5” into the current 2-3 tree:
Through the above simulations, you can already get a preliminary understanding of the characteristics of 2-3 trees and how they maintain absolute balance when adding elements to 2-3 trees.
We said before that red black trees and 2-3 trees are essentially the same thing, and if you understand 2-3 trees, then the red black trees that I’m going to talk about are not hard to understand. There are two types of nodes in a 2-3 tree: 2-node and 3-node. 2-node stores one element, and 3-node stores two elements. Red-black tree is a “2-3 tree in binary tree form”, which uses a single black node to represent a 2-node, and the two “red-black” nodes to represent a three-node point:
In this way, all Red nodes in a red-black Tree must be Left child nodes, so we also call this red-black Tree “left-leaning red-black Tree”.
For example, a 2-3 tree like this:
That’s why we say that a red-black tree is equivalent to a 2-3 tree, and any 2-3 tree can be converted to a red-black tree in this way.
Red black tree implementation
Basic properties of red-black trees
Red-black trees have the following five basic properties:
1. Each node is either red or black.
There’s nothing to say about that, because it’s called a red-black tree, and the nodes are either red or black.
2. The root node must be black.
We can think of a 2-3 tree by analogy. The nodes of a 2-3 tree are either 2-node or 3-node. No matter which kind of node is used as the root node of a red-black tree, the color of the root node must be black.
3. Every leaf node (the last empty node) must be black.
If the red-black tree is empty, then the root node is also empty, which corresponds to the second point, because the root node must be black.
4. If a node is red, its children are black.
You can also use the analogy of a 2-3 tree. In a red-black tree, the left and right nodes of the red node are either 2-nodes or 3-nodes. No matter which kind of node, the nodes connected to the red node must be black nodes.
5. From any node to the leaf node, the same number of black nodes pass through.
After converting the above 2-3 tree to a red-black tree, it looks like this:
From this figure, we can clearly see that from any node to the leaf node, the number of black nodes passing through is the same.
This is what we say — a red-black tree is a binary tree that maintains “black balance” (black nodes are absolutely balanced), and a red-black tree is not a balanced binary tree in the strictest sense, but because of the black-balanced property of a red-black tree, it can be considered to maintain an approximate balance.
From this we can also analyze the time complexity of adding, finding, and removing elements to a red-black tree. In the worst case, red nodes alternate with black nodes on the path from the root node to the leaf node, and its complexity is O(2logN)O(2logN)O(2logN) O(2logN). Ignoring the coefficient of the constant term, we can get that the time complexity of adding, deleting, modifying and searching in red-black tree is O(logN)O(logN)O(logN).
Code implementation for adding elements to a red-black tree
Let’s look at how to add elements to a red-black tree.
It is not difficult to define and implement nodes in red-black trees. Because the red-black tree itself is a binary search tree, the node can store element values and have Pointers to left and right children inside, just as the nodes in the binary search tree implement. If the nodes in a red-black tree are either red or black, we use an additional Boolean variable to represent the node’s color:
public class Node<E> {
public E e;
public Node left;
public Node right;
public boolean color;
public Node(E e) {
this.e = e;
left = null;
right = null;
color = true; // true for red, false for black}}Copy the codeAs you can see, we initialize a node with a red color. The principle of adding nodes to a 2-3 tree is that new nodes are never inserted into an empty space. When we add nodes, we should first fuse the nodes to be added with other nodes. If the color of the initial node is red, it means that the newly added node is fused with other nodes.
Before going through the logic of adding a node to a red-black tree, let’s review the logic of inserting a node into a binary search tree:
If the root node of the current binary search tree is empty, the newly inserted node becomes the root node.
If the root node of the current binary search tree is not empty, the root is used as the node for the current comparison: the newly inserted node is compared with the current node; If the value is smaller than the current node, “go left”, if the value is larger than the current node, “go right”, and then let the node at the next level continue as the current comparison node until it reaches the insertion position.
The following figure shows the process of adding node “28” to the current binary search tree:
Java code:
/ * * *@paramE adds a new element */ to the binary search tree
public void add(E e) {
root = add(e, root);
}
/ * * *@paramE searches the binary tree for the newly inserted node *@paramNode Node of the current comparison *@returnReturns the root node of the binary search tree */
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
return node;
}
Copy the codeWe want the root node of a red-black tree to always be black, so we manually set the root node to black after each insertion:
public void add(E e) {
root = add(e, root);
root.color = BLACK; // false
}
Copy the codeBased on the logic of inserting a node into the binary search tree, we can insert a new node into the red-black tree in the following cases:
- The currently inserted node is fused with the 2-node
- The currently inserted node is fused with the 3-node
If we insert into a 2-node, we have the following two situations:
In the first case, the inserted node has a smaller element value than the current 2-node.
If this is the case, we can simply merge the new node with the 2-node into a 3-node:
In the second case, the inserted node has a greater element value than the current 2-node.
Insert element “42” in the position of the child to the right of “37” :
At this point, the definition of left-leaning red-black tree is not satisfied, we need to perform a “left rotation” operation with node “37” (left rotation is counterclockwise, right rotation is clockwise) and reset the color:
In order to lose generality, I added the corresponding subtrees to the child nodes of node “37” and node “42” respectively. Through the logic of the pseudo-code in the figure above, we can see that the tree after “left rotation” retains the characteristics of both red-black tree and binary search tree.
The Java code for the left rotation operation is as follows:
/ left rotation: * * * * * * / node x \ / \ * T1 x = = = = = = = = = > node T3 * / \ \ * T2, T3 T1 / T2 * * /
private Node leftRotate(Node node){
Node x = node.right;
/ / left rotation
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
Copy the codeAfter discussing all the cases where the newly inserted node is fused with the 2-node, let’s look at the case where the newly inserted node is fused with the 3-node.
If we insert into a 3-node, we have the following situations:
In the first case, the new node is larger than the black node on the 3-node:
After node 66 is inserted:
This step is equivalent to the fusion of our newly inserted node and 3-node into a 4-node, corresponding to the 2-3 tree, our operation is as follows:
Next, we need to turn the current 4-node into 3 2-nodes and let the “42” continue to fuse upwards:
Therefore, correspondingly, in red-black tree, we should change nodes “37” and “66” into black 2-nodes, and set node “42” as the red node that continues to fuse with the previous node:
This step is called flipColors, and as the name implies, it flips the colors of all three nodes. The code is as follows:
// flipColors
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
Copy the codeIn the second case, the new node is smaller than the value of the red node on the 3-node:
After node 12 is inserted:
At this point, we need to perform a right rotation on node “42” :
FlipColors again:
The Java code for the right rotation is as follows:
Turn: / * * * right * * * / node x \ / \ * x T2 = = = = = = = = = = = > node * / \ \ * y y T1 T1, T2 * * /
private Node rightRotate(Node node) {
Node x = node.left;
/ / right turn
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
Copy the codeIn the third case, the new node has a larger value than the red node on the 3-node, but a smaller value than the black node:
After node 40 is inserted:
At this point, we first do a left rotation on node “37”, then a right rotation on node “42”, and then a flipColors operation:
In general, adding elements to a red-black tree has the following logic:
The complete Java code for adding a node to a red-black tree is as follows:
public class RBTree<E extends Comparable<E>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private int size;
public RBTree(a) {
root = null;
size = 0;
}
public int size(a) {
return size;
}
public boolean isEmpty(a) {
return size == 0;
}
/** * Determine the node color **@param node
* @return* /
public boolean isRed(Node node) {
if (node == null)
return false;
return node.color;
}
/ * * *@returnReturns the root node of the red-black tree */
public Node getRoot(a) {
return root;
}
/ left rotation: * * * * * * / node x \ / \ * T1 x = = = = = = = = = = = > node T3 * / \ \ * T2, T3 T1 / T2 * * /
private Node leftRotate(Node node){
Node x = node.right;
/ / left rotation
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
Turn: / * * * right * * * / node x \ / \ * x T2 = = = = = = = = = = = > node * / \ \ * y y T1 T1, T2 * * /
private Node rightRotate(Node node) {
Node x = node.left;
/ / right turn
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// Color flip
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
/ * * *@paramE adds a new element */ to the red-black tree
public void add(E e) {
root = add(e, root);
root.color = BLACK;
}
/ * * *@paramE to the newly inserted node * in the red-black tree@paramNode Node of the current comparison *@returnReturns the root node of the red-black tree */
private Node add(E e, Node node) {
if (node == null) {
size++;
return new Node(e); // The red node is inserted by default
}
if (e.compareTo((E) node.e) < 0) {
node.left = add(e, node.left);
} else if (e.compareTo((E) node.e) > 0) {
node.right = add(e, node.right);
}
if(isRed(node.right) && ! isRed(node.left)) node = leftRotate(node);if(isRed(node.left) && isRed(node.left.left))
rightRotate(node);
if(isRed(node.left) && isRed(node.right))
flipColors(node);
returnnode; }}Copy the codeSo this is the end of inserting a node into a red-black tree.
The above content is my summary of red-black tree learning. The operation of removing a node from a red-black tree is not covered in this article.
conclusion
Today I’m going to focus on red-black tree data structures.
We first introduced 2-3 trees before introducing red-black trees. If you understand 2-3 trees, it’s not really that hard to understand red-black trees.
Then we introduce the five basic characteristics of red-black trees:
- Each node is either red or black
- The root node must be black in color
- Every leaf node (the last empty node) must be black
- If a node is red, its children are black
- From any node to the leaf node, the same number of black nodes pass through
And the five basic characteristics of red-black tree are analyzed from the principle of 2-3 tree.
Finally, we showed you how to add a node to a red-black tree and its code implementation.
Well, so far, this article is here ~ welcome to pay attention to my public number, here I hope you can harvest more knowledge, we see you in the next issue!