二叉排序树查找 ：什么是红黑树？(2)

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

?????????????????????????????????? ?? ?? ????

????????????????????????????????????????????????

????????假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：

????????????????????????????????????????????????????????????????????????????????????????????????????????

接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？

????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。二叉排序树查找(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图中这棵树，就是一颗典型的红黑树：

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

????????????????????????????????????????????????

什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：

1.向原红黑树插入值为14的新节点：

????????????????????????????????????????????????

由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。

2.向原红黑树插入值为21的新节点：

????????????????????????????????????????????????

由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。

????????????????????????????????????????????????

????????????????????????????????????????????????

变色：

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-87093-2.html