红黑树
红黑树主要规则
- 根节点永远是黑色.
- 新插入的红点默认永远是红色.
- 空节点为黑色节点计算.
- 任何一个节点只能是红色或者黑色.
- 任何一条从根节点到叶子节点的路径内，不能包含两个相邻的红色节点.
- 任何一条从根节点到叶子节点的路径内，包含相同的黑色节点（空节点为黑色节点计数）.
网上大部分公认为5条规律,但其实更为官方的说明是4条. 但我认为6条更为清楚，其中大家忽略的是一条，所有新插入节点颜色为红色，会让你在只了解5条的情况下。不知道如何下手写代码。
In addition to the requirements imposed on a binary search tree the following must be satisfied by a red–black tree:[17]
Each node is either red or black.
All leaves (NIL in the figure 1) are considered black.
If a node is red, then both its children are black.
Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
Some authors, e.g. Cormen & al.,[17] claim "the root is black" as fifth property; but not Mehlhorn & Sanders.[18] or Sedgewick & Wayne[16]:432–447 Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the recursive algorithms and proofs.
以上信息来自维基百科.维基百科认为4条规则
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal_of_a_black_non-root_leaf#Properties
在我们开始编码之前，我想先说明几点。
以上的6条规则，不需要强记，但对真实编码有帮助的是最后两条。直接看规则，会让人感觉无从下手。所以每个学习者，都需要根据几个切入点去理解规律的使用。
-
任何一条从根节点到叶子节点的路径内,不能包含两个相邻的红色节点. 此规律用于解决插入数据的冲突检测. 插入操作仅需要检测此条规则既可. 检测到冲突到，根据父节点的兄弟节点来决定是重新染色，还是旋转节点。
- 如果父节点兄弟节点为红色，进行染色操作。
- 如果父节点兄弟节点为黑色，进行旋转操作。
以上仅需要简单了解，会在后续流程中，详细说明。
-
任何一条从根节点到叶子节点的路径内，包含相同的黑色节点（空节点为黑色节点计数）.
新删除节点，如果破坏了这条规则，则需要修复树的黑色节点平衡性，也基于此规则去重新平衡红黑色。
其他任何规则都是辅助规则，如根节点永远是黑色，在某些操作后，可能会破坏掉根节点是黑色这条特性，将新的根节点重新置为黑色即可。
插入新节点
我们以一个示例来更好的理解插入，以及红黑树自平衡过程
准备数据
[1,3,5,7,6,8,9,10]
开始插入数据
-
插入元素：|1|
- 播放操作: 新元素始终为红色，因为根节点为空，根节点被赋值 ，根据规则1：根节点永远是黑色. 将根节点置为黑色。
[xx] 包含的为黑色节点，|xx|包含的为红色节点 [01] / \ [xx] [xx]- 冲突检测: 无
-
插入元素：|3|
- 插入操作: 新元素始终为红色，因为根节点不为空，且元素大于根节点:[01]，放置右侧。
[xx] 包含的为黑色节点，|xx|包含的为红色节点 [01] / \ [xx] |03|- 检测检测: 发现没有相邻的两个红色节点，结束操作。
-
插入元素：|5|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于[01,03],放于元素|03|的右侧。
[xx] 包含的为黑色节点，|xx|包含的为红色节点 [01] / \ [xx] |03| / \ / \ [xx][xx][xx]|05|-
平衡检测：检测是否有冲突，检测到相信两个红色节点:[05,03],根据插入的平衡修复规则.
- 如果父节点兄弟节点为红色，进行染色操作。
- 如果父节点兄弟节点为黑色，进行旋转操作。
父节点兄弟节点为：[xx] 为黑色节点，执行旋转操作，这里提及一点，如果文章不说明，对哪个节点进行旋转，编码将中止，并且需要学习者再搜索其他文章。这是很多博客的问题。所以很难找到一篇博客根据描述，直接写出代码。本文将尝试将细节描述清楚，读者可以根据这些描述，直接进行编码。
所有冲突检测的关键节点为，检测到冲突的节点，这里为红色节点|05|。但操作实际为父节点的父节点(Grand-parent):[01]. 以下简称为G节点，对节点G:[01]，根据不同的节点分布，进行旋转。这里一定有四种不同的旋转分类。
* left-left case 执行 rightRotate(Grand-parent) * left-right case 执行 leftRotate(parent) 然后执行 right(Grand-parent) * right-right rotation 执行 leftRotate(Grand-parent) * right-left rotattion 执行 rightRotate(parent) 然后执行 leftRotate(Grand-parent)具体的旋转这里不进行过多描述，避免本章内容过多。这里明显是right-right类型，所以我们执行leftRotate(Grand-parent).
|03| / \ [01]|05|旋转后，有一个固定的对新的根节点重新染色的过程。通过任何旋转操作完后平衡性保障后，都需要确保，新的父级节点为黑色，左侧俩个孩子为红色。
[03] / \ |01||05|以上解决了所有冲突，此处需要明确，并不是检测一次，而是解决完当前节点后，仍然需要递归向上，检测所有节点是否存在相邻红色节点。并解决所有相邻红色节点冲突。
-
插入元素：|7|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于{03,05},放于元素|05|的右侧。
[03] / \ |01| |05| / \ / \ [xx][xx][xx]|07|- 冲突检测： 检测到新插入节点与父级节点:[07,05] 为两个相邻的红色节点，其父级节兄弟节点：|01| 为红色，根据规则2，父级兄弟节点为红色，执行染色操作。根据上面提过的隐藏的操作条件，所以规则操作节点都是G节点，对G进行重新染色操作。
确保染色后，父节点为红色，两个子节点为黑色，但需要确认操作的节点是不是树的根节点，如果是的话，会与另一条规则：根节点始终为黑色，起冲突，所以我们将根节点：[03]置为黑色。
[03] / \ [01] [05] / \ / \ [xx][xx][xx]|07|以上，解决了所有冲突。
-
插入元素：|6|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于[03,05],放于元素[05]的左侧。
[03] / \ [01] [05] / \ / \ [xx][xx]|06||07|- 冲突检测，没有相邻的两个红色节点。
-
插入元素：|8|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于[03,05,07],放于元素|07|的右侧。
[03] / \ [01] [06] / \ / \ [xx] [xx] |05| |07| / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx]|08|- 冲突检测，检测到两个相邻的红色节点：[08,07], 其父亲兄弟节点为红色节点：|05|，执行重新染色操作。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] [07] / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx]|08|染色后，父节点始终为红色，两个子节点为黑色。再往上检测，没有发现任何冲突，结束操作。
-
插入元素：|9|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于{03,05,07,08},放于元素|08|的右侧。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] [07] / \ / \ / \ / \ [xx] [xx] [xx] [xx] [xx] [xx] [xx] |08| / \ / \ / \ / \ / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx]|09|- 冲突检测，检测到两个相邻的红色节点：[09,08], 其父亲兄弟节点为黑色节点：[xx]，执行节点旋转操作。
根据以上提过的操作节点为G节点:[07], 且应对旋转模型：right-right. 对G节点执行左旋操作。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] |08| / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][07]|09|根据上面提及的规则，旋转后确保父节点为红色，两个子节点始终为黑色。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] [08] / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx]|07||09|冲突解决完毕，向上继续检测没有其他问题，结束操作。
-
插入元素：|10|
- 插入操作：新元素始终为红色，因为根节点不为空，且元素大于[03,06,08,09],放于元素|09|的右侧。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] [08] / \ / \ / \ / \ [xx] [xx] [xx] [xx] [xx] [xx] |07| |09| / \ / \ / \ / \ / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx]|10|- 冲突检测，检测到两个相邻的红色节点：[10,09], 其父亲兄弟节点为红色节点：|07|，对节点G:[08]进行染色操作。
染色后父节点为红色，两个子节点为黑色。
[03] / \ [01] |06| / \ / \ [xx] [xx] [05] |08| / \ / \ / \ / \ [xx] [xx] [xx] [xx] [xx] [xx] [07] [09] / \ / \ / \ / \ / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx][xx]|10|向上继续检测，检测到两个相邻的红色节点:[08,06], 其父亲兄弟节点为黑色节点[01],根据规则，对节点G:[03]进行左旋操作.
|06| / \ [03] |08| / \ / \ [01] [05] [07] [09] / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx]|10|旋转后确保新的根节点为黑色，两个子节点为红色。这里，根节点更新为新的节点:06,且根节点需要始终为黑色，将根节点|06|置为黑色。
[06] / \ |03| |08| / \ / \ [01] [05] [07] [09] / \ / \ / \ / \ [xx][xx][xx][xx][xx][xx][xx]|10|Okay, 解决了所有冲突。
以上是使用测试数据：[1,3,5,7,6,8,9,10] 插入的全部过程。根据这些过程，了解如何解决红黑色的冲突。以及应用红黑树的几个常用规则。
操作检测
我们需要使用严格的自检测机制来确保所有操作的正确性，节点关系的正确性。
重新审视这几条规则，如果没有自检测机制，那么可能在真实编码中，任何一个节点，忘记染色，节点路径出现异常，都会导致大量的时间浪费。
- 根节点永远是黑色.
- 新插入的红点默认永远是红色.
- 空节点为黑色节点计算.
- 任何一个节点只能是红色或者黑色.
- 任何一条从根节点到叶子节点的路径内，不能包含两个相邻的红色节点.
- 任何一条从根节点到叶子节点的路径内，包含相同的黑色节点（空节点为黑色节点计数）.
以此，我们需要有强大的异常检测机制，去辅助大家编写逻辑正确的代码。
- 根节点永远是黑色
- 任何一条从根节点到叶子节点的路径内，不能包含两个相邻的红色节点.
- 任何一条从根节点到叶子节点的路径内，包含相同的黑色节点（空节点为黑色节点计数）.
为此，我为以上三条规则编写了自检测逻辑，并附加了一条子父节点关系的检测逻辑。
@ForTest
private boolean validate(Node<E> node){
if(null == root){
return true;
}
//My own rule, The relationship between children and parent after rotation was always correct.
//Which is really important to help me check my code after any operations.
if(!validateNodeRelationShip(node)){
throw new AssertionError("The relationship between each node are ruined!");
}
//Check the rule: The path from root-leaf have the same number of the black nodes.
if(!validateBlackNode(node,0,0)){
throw new AssertionError("The path from root-leaf have the different number of the black nodes.");
}
//Check the rule: the root node should always be black.
if(!validateRootNode(node)){
throw new AssertionError("The root node was not black.");
}
//Check the rule: There are no consecutive red nodes.
if(!validateConsecutiveRedNode(node)){
throw new AssertionError("There have two consecutive red node.");
}
return true;
}
/**
* Check if the relationship between the children and the parent is corrected
* After insertion, we should always know wherever the rotation ruins the relationship or not.
* @param node
* @return
*/
@ForTest
private boolean validateNodeRelationShip(Node<E> node){
if(null == node){
return true;
}
if(null != node.left && node.left.parent != node ||
null != node.right && node.right.parent != node){
return false;
}
return validateNodeRelationShip(node.left) && validateNodeRelationShip(node.right);
}
/**
* Validate the rule:
* The root node was always black.
* @param node
* @return
*/
private boolean validateRootNode(Node<E> node){
return node.color == BLACK;
}
/**
* Validate black node
* The rule:The path from root-leaf have the same number of the black nodes.
* @param node
*/
private boolean validateBlackNode(Node<E> node,int preBlackSize,int blackSize) {
if(null == node){
//Check if another path has the same black nodes as this path.
return preBlackSize == blackSize;
}
if(node.color == BLACK){
blackSize++;
}
if(0 == preBlackSize && (null == node.left || null == node.right)){
preBlackSize = blackSize;
}
return validateBlackNode(node.left,preBlackSize,blackSize) && validateBlackNode(node.right,preBlackSize,blackSize);
}
/**
* Validate the rule:
* No path can have two consecutive red nodes, But the path can have two consecutive black nodes.
* @param node
* @return
*/
private boolean validateConsecutiveRedNode(Node<E> node){
if(null == node){
return true;
}
if(node.color == RED && (null != node.left && node.left.color == RED||null != node.right && node.right.color == RED)){
return false;
}
return validateConsecutiveRedNode(node.left) && validateConsecutiveRedNode(node.right);
}
以上，将测试代码放于添加逻辑后
@Override
public boolean add(@NonNull E e) {
if(null == root){
root = new Node<>(e);
root.color = BLACK;
} else {
Node<E> newNode = addInternal(root, e);
fixViolationAfterInsertion(newNode,e);
//After inserting the new element. We check if all the rules are corrected.
validate();
}
size++;
return true;
}
测试插入逻辑是否正确
@Test
public void testInsert(){
final Random random = new Random();
//test 10 times, make sure all the operation is correct.
for(int i=0;i<10;i++) {
RedBlackTree<Integer> tree = new RedBlackTree<>();
Deque<Integer> deque = new ArrayDeque<>();
for (int i1 = 0; i1 < 1000; i1++) {
int value = random.nextInt(100000);
while (deque.contains(value)) {
value = random.nextInt(100000);
}
deque.push(value);
tree.add(value);
}
assert 1000 == tree.size();
}
}
以上，红色树插入相关。
另请查阅：红黑树删除相关
网友评论