1. Overview of red-black trees
Red-black Tree (RED-black Tree) is a self-balanced binary search Tree. Formerly also called a Symmetric Binary B-tree.
Red-black trees must meet the following five properties: 1. Each node is red or black; 2. 2. The root of the tree is always black. 3. Each leaf node (outer node, null node) is black;
Note: The leaf node here is different from the leaf node in the previous article series and refers to the additional null node. See the NULL node in Figure 1
4. The children of every red node are black;
In other words, the parent of a red node is black; There cannot be 2 consecutive red nodes on all paths from root to leaf.
5. All paths from any node to the leaf node contain the same number of black nodes.
Here is a red-black tree:
Note: Null nodes are not drawn in all the following figures.
Parent: sibling: uncle: grand: grandparent: grand: grandparent: grand: grand: grandparent: grand: grand: grand: grand: grand: grand: grand: grand: grand: grand: grand: grand: grand
2. Red black tree and 4th order B tree
2.1 Comparison between red-black tree and fourth-order B-tree
Red-black trees can be better understood in terms of fourth-order B-trees.
Level 4 B-tree brief portal
Let’s start with the figure above and compare a red-black tree to a fourth-order B tree
The black node without red child node is an independent B-tree node.
When comparing red-black trees and fourth-order B-trees, in the process of mutual transformation, we agreed:
- A node with only one element is marked black;
- If there are two elements, the node is marked in black first and then in red. When transformed into a red-black tree, it can be split into two nodes, and the node marked red as the child node of the node marked black.
- If you have three elements, the middle element is black, and the left and right elements are red. When transformed into a red-black tree, it is split into three nodes, and the left and right red nodes are used as children of the black node.
Therefore, the 4th order B tree in the lower right corner of the figure above can be converted to the red-black tree in the upper right corner (adjust the display style to the red-black tree in the upper left corner) according to the convention described above. The red-black tree in the upper right corner can also be converted into a fourth-order B-tree.
2.2 Red-black tree is equivalent to fourth-order B-tree
- In red-black trees, the black node and its red children are fused together to form a B-tree node.
- The number of black nodes in a red-black tree is equal to the total number of nodes in a fourth-order B-tree.
In red-black tree vs fourth-order B-tree, there are several cases in which nodes in red-black tree are merged to obtain fourth-order B-tree: 1) The black node and its two red child nodes are merged to form a fourth-order B-tree node. This is: red black red. 2) The black node and its only right red child node are merged into a fourth-order B-tree node. This is: black and red. 3) The black node and its only left red child node are merged into a fourth-order B-tree node. This is: red and black. 4) The black node has no red child node and becomes a fourth-order B-tree node by itself. This is black.
Here are four scenarios:
3. Add red black tree
Based on the equivalence between red-black tree and fourth-order B-tree, fourth-order B-tree can be compared when red-black tree adds elements to facilitate the analysis of its processing logic.
We know that in a B tree, new elements must be added to the leaf node, which corresponds to each node in the red-black tree.
In the red-black tree, we set the newly added nodes to red by default, then process the related nodes as needed and eventually restore the red-black tree.
If the default value is set to red, properties 1, 2, 3 and 5 of the red-black tree above are directly satisfied (property 4 should not necessarily be satisfied), so that the properties of the red-black tree can be satisfied as soon as possible. You just need to do something to satisfy property 4.
Since the new element must be added to the leaf node, there are 12 ways to add an element to a red-black tree, as shown in the figure below:
Among the 12 cases, the parent node of the ⑤⑩⑪ restful restful restful restful restful restful sleep is black, which directly satisfies property 4.
In the remaining 8 cases, property 4 is not satisfied, because the added node is red, and the parent node of the added node is also red, that is, two consecutive red nodes.
Next, the processing of the various add scenarios is analyzed.
Red-black tree adding elements can be divided into the following scenarios:
3.1 A red-black tree is an empty tree
Use the insert node as the root node and color the node black.
3.2 Adding a Node The parent node of a Node is black
Accordingly, the following figure shows the ⑤⑩⑪ of all children. Add it directly.
3.3 The parent node of a Node to be added is red and the uncle of the node to be added is not red (the uncle is black or does not exist)
Corresponding to ⑥⑦⑧⑨ in the “All Cases Added” figure above. However, there are differences in the processing procedures of these four cases. The following is the corresponding analysis of these four cases:
3.3.1 Adding a node is the left child of the parent node and the parent node is the left child of the grandfather node, that is, LL for the grandfather node
That is, the parent node of the added node is red, the uncle node of the added node is not red (the uncle node is black or does not exist), and the added node is the left child node of the parent node, and the father node is the left child node of the grandfather node.
Solution: 1) father section point dyed black, grandfather section point dyed red; 2) Dextral rotation of the grandfather node (LL-dextral).
Example: The following figure for analysis
According to the above analysis: By analogy with fourth-order B-tree, when 60 is added, in terms of fourth-order B-tree, elements 60, 72 and 76 are merged into a node. After the analysis of equivalence between the previous fourth-order B-tree and red-black tree, it can be known that if 60 wants to be added successfully and elements 60, 72 and 76 want to be merged into a contact, 72 must turn black, 76 must turn red, that is, red (60) black (72) red (76); At the same time, when red-black tree is converted into fourth-order B-tree: The black node merges with its red child node to form a B-tree node. In other words, the black node 72 needs to be the parent of the two red nodes 60 and 76. Therefore, when 72 turns black, the parent node 76 needs to point to 72, which is equivalent to a dextral operation for the grandfather node 76.
The whole process can be summarized as follows: the parent node 72 is dyed black, and the grandfather node 76 is dyed red; The grandfather node is then right-handed. The resulting graph for the bottom half of the figure above.
3.3.2 Adding a node that is the left child of the parent node and the parent node is the right child of the grandfather node, that is, RR for the grandfather node:
That is, the parent node of the added node is red, the uncle node of the added node is not red (the uncle node is black or does not exist), and the added node is the left child node of the parent node, and the father node is the right child node of the grandfather node.
This is the opposite of the case in 3.3.1 above, so the idea is the same, but the rotation is the opposite. Solution: 1) father section point dyed black, grandfather section point dyed red; 2) Left-rotate the grandfather node (RR-left-rotate).
As shown in the following figure, adding node 52 is equivalent to RR for the grandfather node 46, so dye the parent node 50 black and the grandfather node 46 red. The grandfather node is then left rotated to obtain the lower half of the resulting graph
3.3.3 Adding that the node is the right child node of the parent node and the parent node is the left child node of the grandfather node, namely LR for the grandfather node:
That is, the parent node of the added node is red, the uncle node of the added node is not red (the uncle node is black or does not exist), the added node is the right child node of the parent node, and the father node is the left child node of the grandfather node.
Analysis: at this time, only the left rotation of the parent node can be converted into the above LL type, so: solution: 1) The left rotation of the parent node, converted into LL type; 2) Perform subsequent operations according to LL type.
Here’s an example:
In the figure above, add node 74 is the right node of parent node 72, and 72 is the left node of grandfather node 76, i.e., for grandfather node 76, it is equivalent to LR, as shown in the upper left view. At this point, 72 becomes the left child node of 74 and 74 becomes the left child node of 76. After rotation, the parent node 72 has been converted into LL type, as shown in the lower left corner of the view. According to the above scenario 2.1. LL type, dye the parent node 74 black and the grandfather node 76 red, and then rotate 76 right to get the final result, as shown in the lower right corner view.
In fact, you can color it first and then rotate it again, and you can also restore it to a red-black tree: I) add nodes and dye them black, grandparent nodes and dye them red; Ii) Left-rotate the parent node and right-rotate the grandfather node.
3.3.4 Adding a node is the left child node of the parent node and the parent node is the right child node of the grandfather node, that is, RL for the grandfather node:
That is, the parent node of the added node is red, the uncle node of the added node is not red (the uncle node is black or does not exist), and the added node is the left child node of the parent node, and the father node is the right child node of the grandfather node.
Analysis: At this time, just rotate the parent node to the right to convert it to the RR type above, similar to the above scene 3.3.3, except in the opposite direction, so its rotation should be reversed and then adjusted. So:
Solution: 1) Rotate the parent node right and convert it into RR; 2) Perform subsequent operations according to RR.
It can also be colored and then rotated to restore the tree to a red-black tree: I) add nodes and dye them black, grandparent nodes and dye them red; Ii) Right rotation for the parent node and left rotation for the grandfather node.
3.4 The parent node of a Node to be added is red, and the uncle node of a node to be added is red
Corresponding to ①, ②, ③ and ④ in all the above cases, the following figure is used to analyze the situation ① :
Add node 10, its parent node 17 is red, and its uncle node 33 is also red. Contrast in terms of order 4 B tree, 10, 17, 25, 33 merged into a tree node B, appear on the overflow (node 4 elements more than 4 order B tree log on a single node element 3 limit), so according to the operation of the overflow in the B tree, nodes within the element about merger and node splitting up, at this time choose 25 overflow (17 because don’t choose, 25 itself is the child node of 38, which is convenient to handle), and it is split into two child nodes. The left nodes 10 and 17 want to become a B-tree node (always pay attention to the analogy of red-black tree), then 17 and 10 can be merged into a node only when they are black, because the red-black tree can be merged into a B-tree node as follows: The black node merges with its red child node. And 33 on the right has to be black. At this point we complete the logic of splitting. Continue to analyze the upward merging of 25. At this time, it can be regarded as 38 and 55 adding a new 25. At this time, we can regard 25 as the newly added node, so as to return to the judgment processing process of the newly added node. Here, the parent node of 25 is red, and the uncle node of 25 is not red (there is no uncle node, and the default nil node in the red-black tree is black). Meanwhile, 25 is the left node of the parent node 38, and the parent node 38 is the left node of the grandfather node 55, which conforms to the above scenario 2.1. So the parent node 38 is colored black, the grandfather node 55 is colored red, and then the parent node 55 is rotated right. Redest restores red-black tree balance.
The process is illustrated with the annotation information.
Therefore, the whole process can be summarized as follows: 1) dye the parent node and uncle node into black; 2) Merge grandparent nodes upward: treat grandparent nodes as newly added nodes.
1) The red-black tree may not be restored, so continue the recursive processing. If you work all the way to the root node, you only need to color the root node black
The processing process of ②③④ is the same as that of ①, except that the rotation involved may be different, so it will not be described here.
4. Remove
In a B-tree, the last elements that are actually deleted are in the leaf nodes. When we find an element in the B tree to delete, we find the successor element, replace its value with the successor element, and then delete the successor node.
Like adding nodes, the deletion of red-black trees is also divided into two categories: red nodes and black nodes.
4.1 The deleted node is a red node
Direct deletion also meets the property of red-black tree four, so it can be directly deleted
Note: After the direct deletion, you also need to dye the deleted section red
4.2 The node to be deleted is black
The deleted node is black and can be divided into three types: 1) black node has no child node (i.e. leaf node) 2) black node has one red child node 3) black node has two red child nodes. 3) It is impossible for the black node and two red child nodes to be deleted directly, because the replacement value of the successor node will be found and then the successor node will be deleted, so this situation is not considered.
And 2) how to determine that the black node has a red child node? Whether the child node used to replace the node is red. We know that in the binary search tree, when the node with degree 1 is deleted, the position of the node is replaced by the child node of the deleted node.
4.2.1 Delete a black node with only one red child node
There are two cases of deleting the black node with only one red child node: Figure 1 below) The red child node is the right child node and the red node 50 is the right node of the black node 46. 2) The red child node is the left child node. The red node 72 is the right node of the black node 76.
The operation of the above two cases is basically the same, so choose one to analyze. We select the case where the red child node is the right child node for analysis: The whole process is shown in the figure below:
So: deleting the black node with only one red child node can restore the red-black tree balance by dyeing the replacement child node black.
4.2.2 The deleted node is a black leaf node, and its sibling node is also black
In the figure below, 88 in the left half view and 88 in the right half view are black themselves, and the younger node 76 is also black.
Similarly, when we delete 88 in the left and right views, the B-tree will overflow, and we need to “borrow” elements from the sibling node to fill (the sibling node elements merge up, and the parent node elements fill down). You can post that when you delete 88 on the left, its sibling 76 has elements to borrow (for b-trees, 76 and 78 are merged into a single B-tree node). On the right, 88, whose sibling 76 is a single element node, has no elements to borrow. Different processing is required for sibling nodes with or without elements to borrow. Therefore, the scene where the deleted node is a black leaf node and its sibling node is also black needs to be subdivided.
4.2.2.1 The node to be deleted is a black leaf node, and its sibling node is also black, and the sibling node has at least one red child node
Sibling nodes have at least one red child node. There are three cases, namely red right child node, red left child node, and two red child nodes, as shown in the figure below:
The three cases drawn here are divided according to the red child node. The positions of deleted nodes and sibling nodes can also be opposite to the situation in the figure, that is, 88 is the left child node, 76 is the right child node, which is exactly opposite to the figure (affecting the subsequent rotation direction).
We take the red right child node (the leftmost view in the figure above) as an example for analysis: 1) Delete node 88, and the B tree overflows; 2) Borrow elements from sibling nodes, merge element 78 up, and fill parent node 80 down. At this point, if 78 is taken as the reference, 80 just conforms to LR (78 is the right node of parent node 76 and 76 is the left node of grandfather node). Therefore, left-rotation is performed for 76 and right-rotation is performed for 80 to solve the problem of underflow. 3) Color the rotated central node with the color of the parent node of the original deleted node, while the new left and right child nodes after the rotation are black (76 and 80 must be black if they want to be an independent B-tree node).
The whole process and results are shown below:
The other two deletions are similar and will not be described here.
4.2.2.2 The deleted node is a black leaf node, and its sibling node is also black, and the sibling node does not have a red child node
Of course, if the parent node of the deleted node is black, it will be treated slightly differently:
4.2.3 The deleted node is a black leaf node, and its sibling node is red
From the point of view of B tree, if the sibling node is red, there must be no element to borrow.
The black nodes of a red-black tree and their red children are combined to form a fourth-order B-tree.
Borrowing elements directly from the children of the red node is cumbersome. We can find a way to make the children of the red sibling (which must be black) become siblings. This translates to a situation where the deleted node is a black leaf node and its siblings are also black. 1) Dye the brother node point black, and the father node point red; 2) Rotate the parent node accordingly; 3) When the deleted node is a black leaf node and its sibling node is also black, the red-black tree balance is finally restored according to the corresponding operations.
Example: See the following figure
5. Add delete code
5.1 Red-black tree Nodes
public static class RBTreeNode<E> { boolean color = RED; // Add node default red E element; RBTreeNode<E> left; RBTreeNode<E> right; // RBTreeNode<E> parent; Public RBTreeNode(E element, RBTreeNode<E> parent) {this.element = element; this.parent = parent; } public boolean hasTwoChildren() { return left ! = null && right ! = null; } public Boolean isLeftChild() {return (parent! = null && this == parent.left); } public Boolean isRightChild() {return (parent! = null && this == parent.right); Public RBTreeNode<E> sibling() {if (isLeftChild()) {return parent.right; } if (isRightChild()) { return parent.left; } return null; }}Copy the code5.2 Add and delete all complete codes
/**
* 红黑树
* @param <E> 泛型
*/
public class RBTree<E> {
// 标记节点颜色
private static final boolean RED = false;
private static final boolean BLACK = true;
private int size; // 树元素大小
private RBTreeNode<E> root; // 根节点
private Comparator<E> comparator; // 比较器，可由外部控制比较器规则
// 外部不传入比较器规则，则使用默认的存入节点的对象实现的比较规则
public RBTree() {
this(null);
}
// 外部传入比较器规则，则使用传入的比较规则
public RBTree(Comparator<E> comparator) {
this.comparator = comparator;
}
/**
* 添加元素
*/
public void add(E element) {
elementNotNullCheck(element);
// 添加根节点
if (root == null) {
root = new RBTreeNode<>(element, null);
size++;
return;
}
// 添加的不是第一个节点
// 1.找到父节点
RBTreeNode<E> parent = root;
RBTreeNode<E> node = root;
int cmp = 0;
while (node != null) {
// 保存父节点，如果此时不保存的话，在 while 循环发现 node == null 的时候，跳出循环
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.element = element;
return;
}
}
// 2.看看插入到父节点的哪个位置
RBTreeNode<E> newNode = new RBTreeNode<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
/**
* 添加节点后恢复红黑树平衡
* @param node 新添加的节点
*/
private void fixAfterAdd(RBTreeNode<E> node) {
RBTreeNode <E> parent = node.parent;
// 添加的是根节点
if (parent == null) {
black(node); //根节点着黑色
return;
}
// 插入节点的父节点是黑色，直接返回（因为插入的节点默认是红色）
if (isBlack(parent)) {
return;
}
/* 插入节点的父节点是红色 */
// 获取节点的叔父节点（父节点的兄弟节点）
RBTreeNode<E> uncle = parent.sibling();
// 获取节点的祖父节点（父节点的父节点）
RBTreeNode<E> grand = parent.parent;
// 叔父节点是红色
if (isRed(uncle)) {
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点，继续向上恢复红黑树
red(grand);
fixAfterAdd(grand);
return;
}
// 能来到这里，说明叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
red(grand);
rotateRight(grand);
} else { // LR
red(grand);
black(node);
rotateLeft(parent);
rotateRight(grand);
}
} else { // R
if (node.isLeftChild()) { // RL
black(node);
red(grand);
rotateRight(parent);
rotateLeft(grand);
} else { // RR
black(parent);
red(grand);
rotateLeft(grand);
}
}
}
/**
* 删除元素
*/
public void remove(E element) {
// 通过元素值查找节点
RBTreeNode<E> node = node(element);
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继结点
RBTreeNode<E> s = successor(node);
// 用后继结点的值覆盖读为2的节点的值
node.element = s.element;
// 删除后继结点，这里只需要将node指向s，后面代码统一删除 node 即可
node = s;
}
// 删除 node 节点（此时 node 节点的度必然是 0 或者 1，因为node的度未2的情况，上面已经特殊处理了）
RBTreeNode<E> replaceNode = node.left != null ? node.left : node.right;
if (replaceNode != null) { // node 是度为1的节点，使用子节点替代replaceNode替换node的位置
// 更改 parent
replaceNode.parent = node.parent;
if (node.parent == null) { // 删除的是根节点
root = replaceNode;
}
// 更改parent的left、right指向
if (node == node.parent.left) {
node.parent.left = replaceNode;
} else if (node == node.parent.right) {
node.parent.right = replaceNode;
}
// 删除节点之后的处理
fixAfterRemove(replaceNode);
} else if(node.parent == null) { // node是叶子节点且根节点
root = null;
// 删除节点之后的处理
fixAfterRemove(replaceNode);
} else { // node 是叶子节点但不是根节点
if (node == node.parent.right) {
node.parent.right = null;
} else {
node.parent.left = null;
}
// 删除节点之后的处理
fixAfterRemove(node);
}
}
/**
* 删除元素后，恢复红黑树平衡
* @param node 被删除的节点 或者 用以取代被删除节点的子节点（当被删除节点的度为1）
*/
private void fixAfterRemove(RBTreeNode<E> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
RBTreeNode<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
RBTreeNode<E> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
fixAfterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
fixAfterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
/**
* 左旋转 - RR 型
*/
private void rotateLeft(RBTreeNode<E> node) {
RBTreeNode<E> subNode = node.right;
RBTreeNode<E> subSubNode = subNode.left;
node.right = subSubNode;
subNode.left = node;
// 让subNode成为最小失衡子树的根节点
subNode.parent = node.parent;
if (node.isLeftChild()) {
node.parent.left = subNode;
} else if (node.isRightChild()) {
node.parent.right = subNode;
} else {
root = subNode;
}
// 更新 subSubNode 的 父节点
if (subSubNode != null) {
subSubNode.parent = node;
}
// 更新 node 的父节点
node.parent = subNode;
}
/**
* 右旋转 - LL 型
*/
private void rotateRight(RBTreeNode<E> node) {
RBTreeNode<E> subNode = node.left;
RBTreeNode<E> subSubNode = subNode.right;
node.left = subSubNode;
subNode.right = node;
// 让subNode成为最小失衡子树的根节点
subNode.parent = node.parent;
if (node.isLeftChild()) {
node.parent.left = subNode;
} else if (node.isRightChild()) {
node.parent.right = subNode;
} else {
root = subNode;
}
// 更新 subSubNode 的 父节点
if (subSubNode != null) {
subSubNode.parent = node;
}
// 更新 node 的父节点
node.parent = subNode;
}
/**
* 通过值找到节点
*/
private RBTreeNode<E> node(E element) {
RBTreeNode<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
// 相等（即找到）直接返回
if (cmp == 0) return node;
// 查询元素比节点值大，则继续查找节点的右子树
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
// while 循环结束，未查到对应节点
return null;
}
/**
* 获取一个节点的后继结点
*/
private RBTreeNode<E> successor(RBTreeNode<E> node) {
if (node == null) return null;
// 右子树不为空，前驱结点在右子树中（right.left.left...）
if (node.right != null) {
RBTreeNode<E> p = node.right;
while (p.left != null) {
p = p.left;
}
return p;
}
// 右子树为空，从父节点、祖父节点..中寻找前驱结点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
/**
* 节点着色
* @param node 着色节点
* @param color 需要着的颜色
* @return 返回着好色的节点
*/
private RBTreeNode<E> color(RBTreeNode<E> node, boolean color) {
if (node == null) return node;
node.color = color;
return node;
}
/**
* 节点着红色
* @param node 着红色的节点
* @return
*/
private RBTreeNode<E> red(RBTreeNode<E> node) {
return color(node, RED);
}
/**
* 节点着黑色
* @param node 着黑色的节点
* @return
*/
private RBTreeNode<E> black(RBTreeNode<E> node) {
return color(node, BLACK);
}
/**
* 获取节点的颜色
*/
private boolean colorOf(RBTreeNode<E> node) {
return node == null ? BLACK : ((RBTreeNode<E>)node).color;
}
/**
* 节点是否为红色
*/
private boolean isRed(RBTreeNode<E> node) {
return colorOf(node) == RED;
}
/**
* 节点是否为黑色
*/
private boolean isBlack(RBTreeNode<E> node) {
return colorOf(node) == BLACK;
}
/**
* 元素空（null）检查
* @param element 元素
*/
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
/**
* 节点值比较
* @param e1
* @param e2
* @return 返回值等于0，代表e1 == e2；返回值大于0，代表e1 > e2；返回值小于0，代表e1 < e2；
*/
private int compare(E e1, E e2) {
// 外部传入了可比较器则使用传入的可比较器
if (this.comparator != null) {
return comparator.compare(e1, e2);
}
// 外部未可比较器则使用e1对应类实现的Comparable的比较器，因为二叉搜索树的节点必须存放可比较的对象元素
return ((Comparable<E>)e1).compareTo(e2);
}
}
Copy the code6. Balance and complexity of red-black trees
At the beginning of this article, we listed five properties of red-black trees, so why do those five properties guarantee the equilibrium of red-black trees? The five properties guarantee that a red-black tree is equivalent to a fourth-order B tree. Compared to an AVL tree, a red-black tree has a looser equilibrium criterion: a weak equilibrium, a black-height equilibrium, when no path is twice as large as the other paths. In addition, the maximum height of a red-black tree is 2 log base 2 (n + 1), which is still order log base n.
Complexity Search for red-black trees: O(logn)
Added: O(logn), O(1) rotation operations
Delete: O(logn), O(1) rotation operations
Comparison of AVL trees and red-black trees
- AVL tree
1) Balance labeling is strict: the height difference between each left and right self-reported is no more than 1;
2) The maximum height is 1.44 ∗ log2 N + 2 − 1.328 (100W nodes, maximum height of AVL tree is 28);
3) Search, add, and delete are O(logn) complexity, where add requires O(1) rotation adjustment, and delete requires O(logn) rotation adjustment at most.
- Red and black tree
1) The balance standard is relatively loose: no path is twice larger than other paths;
- The maximum height is 2 ∗ log2(n + 1) (100W nodes, the maximum height of red-black tree is 40);
3) Search, add, delete are O(logn) complexity, add, delete only need O(1) rotation adjustment.
AVL tree and red black tree selection
- Search times are much greater than insert and delete, select AVL tree; Search, insert, delete almost the same number of times, choose red black tree;
- Compared with AVL trees, red black trees sacrifice part of the balance in exchange for a small amount of rotation during insert/delete operations, and the overall performance is better than AVL trees.
- The average statistical performance of red-black tree is better than that of AVL tree.