红黑树--优化的二叉搜索树

vlambda
2021-03-21

红黑树--优化的二叉搜索树

在分享红黑树之前，先看一下下面的这棵二叉搜索树

这是一棵平衡的二叉搜索树，现在要在其中插入下列一组数据：

19，18，17，16，15，14，13，12

根据上一篇分享的二叉搜索树的插入过程，将这些数字按顺序插入后，上面的二叉搜索树，最终变成了下面这个样子

红黑树--优化的二叉搜索树

现在这个仍然是一个二叉搜索树，但是原本平衡的结构，现在变成了一条腿的瘸子了，其结构已经接近成了线性的，这样的话其查找、插入等操作效率就大打折扣了。因为二叉搜索树只有保持近似平衡，才能保证其O(lg n)的时间复杂度。

红黑树正是为了解决这个问题而生。

红黑树的性质

为了解决上面的问题，红黑树为每个结点添加了一个属性color，规定：

1、红黑树的每个结点，要么是红，要么是黑

2、红黑树的根结必须是黑色

3、红黑树所有的叶子结点都是黑色

4、红黑树中如果有一个结点是红色的，那么它的两个孩子结点必须是黑色

5、从红黑树中任意一个结点（不包含该结点）到叶子结点的简单路径上，黑色结点的数量是相同的

这里需要说一下叶子结点是什么？

红黑树定义结点时需要定义5个属性，color(颜色)、key(结点保存的值)、p(结点的父结点)、left(结点的左孩子结点)、right(结点的右孩子结点)，如果一个结点没有子结点，那就规定p、left、right，这几个指针都指向一个NIL，这个NIL称为叶子结点，它除了color为黑色外，其它的属性值随意。

下面这个图是一个标准的红黑树的示意，可以对照着红黑树的性质看一下它是否满足上面的五条性质。

1、所在点或红或黑(满足)

2、根结点12是黑色(满足)

3、所有没有子结点的结点都指向NIL叶子结点，并且NIL为黑色(满足)

4、所有红色结点的子结点都是黑色(满足)

5、经查，第五条性质也(满足)

所以它是一个红黑树。

红黑树--优化的二叉搜索树

关于这张图做叶子结点示意时我们这样画，但是一般情况下，我们不用画出NIL叶子结点，如下图即可：

红黑树--优化的二叉搜索树

红黑树的操作

由于红黑树本质上是一棵二叉搜索树，所以对上篇分享

（如果没有看，可以点此链接查看）中提到的：遍历、查找、找前驱/后继、获取最小/大值、这些操作在红黑树上同样适用。

而插入和删除操作，在这里就不适用了。因为这两操作可能会对红黑树的性质造成破坏。

现在进行插入两个数字，看看是如何破坏红黑树性质的，现在插入：1

红黑树--优化的二叉搜索树

对比五个性质，现在这棵树仍然保持了红黑树的性质，没有问题。

现在再插入：10

红黑树--优化的二叉搜索树

现在就出问题了，结点9是红色，按照性质4，红色结点的孩子结点必须是黑色，红黑树的性质被破坏。经过筛查，插入10这个操作，仅仅对性质4产生了影响，其它4个性质仍然保持。

从上面的两个插入操作，插入1、插入10，可以看出，

插入的新结点是黑色结点的孩子的话，不会对红黑树的性质产生影响，

插入的新结点是红色结点的孩子的话，会对性质4产生影响，破坏红黑树的性质

除了上面在红色结点下面插入会破坏红黑树的性质外，还有一种情况会破坏性质，那就是在空树上插入，因插入的新结点是红色，它做了树根，这样就破坏了性质2

如何解决插入新结点带来的破坏红黑树的性质问题呢，那就需要对新插入的结点进行一番调整

维护红黑树性质的操作

为了维护被破坏的性质，有两种操作可以使用：

一种是变色，这个很好理解，就是让原先是黑色的结点变成红色，红色的结变成黑色。

另一种是旋转，旋转分为左旋和右旋

左旋：对任意一个右孩子不为空的结点x，与它的右孩子y，进行逆时针旋转操作

看下左旋的示意图吧，初始的树内结构如下图：

红黑树--优化的二叉搜索树

现在选定结点3为x，结点7为x的右孩子，也就是y进行左旋操作，

红黑树--优化的二叉搜索树

操作后如下图：

红黑树--优化的二叉搜索树

从结果中可以看出，y变成了x的父结点，x变成了y的左孩子，原先y的左孩子6变成了x的右孩子。

左旋操作的结果就是将结点的右孩子变成结点的父结点，结点变成右孩子的左孩子，结点的右孩子的左孩子变成结点的右孩子(有点绕，对着图看应该很好理解)。

右旋操作与左旋正好反，选定一个左孩子不为空的结点，和其左孩子，然后对其顺时针旋转：

红黑树--优化的二叉搜索树

右旋后，恢复了最开始的样子：

红黑树--优化的二叉搜索树

右旋操作的结果：将结点的左孩子变成了结点的父结点，结点变成了其左孩子的右孩子，结点的左孩子的右孩子变成了结点的左孩子

从上面的左旋和右旋示意当中可以看出，两种旋转后，整棵树还是一棵二叉搜索树。

插入操作时三种情况利用相应变色和旋转维护红黑树性质

现在假设插入新结点5，x指针指向5这个结点，可以看出5 的插入破坏了红黑树的性质4，需要对新插入的结点进行调整。

红黑树--优化的二叉搜索树

第一种情况：如果新结点的父结点是红色，其叔父结点（祖父的右孩子）也是红色，则需要执行操作，改变父结点与叔父结点为黑色，祖父结点为红色，同时x指针指向其祖父结点

在上图中x的父结点6是红色，叔父结点9也是红色，祖父结点7是黑色，所以执行操作，让6和9变黑，7变红，同时让x指针指向7。

红黑树--优化的二叉搜索树

现在x指针指向的7是新的需要调整的结点。

第二种情况：如果要调整的结点的父结点是红色，其叔父结点是黑色，并且x是其父结点的右孩子，则执行，先将x指针指向其父结点，然后对其父结点执行左旋操作

上图中要调整的结点是x指向的结点7，其父结点是3，叔父结点是14，同时x是3的右孩子，所以可执行第二种情况，先将x指向3，然后对3执行左旋。

红黑树--优化的二叉搜索树

第三种情况：如果要调整的结点的父结点是红色，其叔父结点是黑色，并且x是其父结点的左孩子，则执行，将其父结点改变为黑色，其祖父结点改变为红色，然后对其祖父执行右旋操作

对于上图，先将父结点7改为黑色，祖父结点12改为红色

红黑树--优化的二叉搜索树

然后对祖父结点12执行右旋操作

红黑树--优化的二叉搜索树

现在再观察，x指向的结点的父结点7是黑色，而我们调整时其父结点为红色时才会执行调整。所以到此整个调整就结束了，可以看到新插入结点5后，被破坏的红黑树的性质，经过调整，现在又恢复了红黑树性质。

与上面三种情况相对称的还有三种，

第一种情况：如果新结点的父结点是红色，其叔父结点（祖父的左孩子）也是红色，则需要执行操作，改变父结点与叔父结点为黑色，祖父结点为红色，同时x指针指向其祖父结点

第二种情况：如果要调整的结点的父结点是红色，其叔父结点是黑色，并且x是其父结点的左孩子，则执行，先将x指针指向其父结点，然后对其父结点执行右旋操作

下面图示过程：不再解释了哈。

红黑树--优化的二叉搜索树

import java.util.Arrays;
public class RbTree { public static String RED = "red"; public static String BLACK = "black";
 public RbNode root;
 public static class RbNode { public String color; public int aValue; public RbNode p; public RbNode left; public RbNode right; }
 // 实现中序遍历 public void accessTree(RbNode n) { if (n != null) { accessTree(n.left);// 先访问左孩子 System.out.print(n.aValue); // 输出根结点的值 System.out.print(","); accessTree(n.right);// 最后访问右孩子 } }
 public void leftRotate(RbTree tree, RbNode nodeRotate) { RbNode y = nodeRotate.right;// 旋转结点的右孩子 y, nodeRotate.right = y.left;// 旋转结点的右孩子设置为其右孩子的左孩子 if (y.left != null) {// 旋转结点的右孩子的左孩子不为null y.left.p = nodeRotate;// 旋转结点的右孩子的左孩子的父结点设置为旋转结点 } y.p = nodeRotate.p;// 旋转结点的右孩子的左孩子的父结点设置为旋转结点父结点
 if (nodeRotate.p == null) { tree.root = y; } else if (nodeRotate == nodeRotate.p.left) { nodeRotate.p.left = y; } else { nodeRotate.p.right = y; }
 y.left = nodeRotate; nodeRotate.p = y; }
 public void rightRotate(RbTree tree, RbNode nodeRotate) { RbNode y = nodeRotate.left; nodeRotate.left = y.right; if (y.right != null) { y.right.p = nodeRotate; } y.p = nodeRotate.p;
 if (nodeRotate.p == null) { tree.root = y; } else if (nodeRotate == nodeRotate.p.left) { nodeRotate.p.left = y; } else { nodeRotate.p.right = y; }
 y.right = nodeRotate; nodeRotate.p = y; }
 public void treeInsert(RbTree tree, RbNode nodeInsert) { RbNode pos = null;// 记录找到插入位置 RbNode y = tree.root; while (y != null) { pos = y; if (nodeInsert.aValue < y.aValue) { y = y.left; } else { y = y.right; } } // 下面代码设置x和它的父结点的各个属性 nodeInsert.p = pos; if (pos == null) {// 如果pos为null说明树中原来没有结点，则新插入结点调置为树根 tree.root = nodeInsert; } else if (nodeInsert.aValue < pos.aValue) { pos.left = nodeInsert; } else { pos.right = nodeInsert; }
 nodeInsert.left = null; nodeInsert.right = null; nodeInsert.color = RbTree.RED;
 insertFixup(tree, nodeInsert); }
 public void insertFixup(RbTree tree, RbNode nodeFixup) {
 while (nodeFixup.p != null && nodeFixup.p.color == RbTree.RED) { RbNode uncle = null; if (nodeFixup.p == nodeFixup.p.p.left) { uncle = nodeFixup.p.p.right; if (uncle != null && uncle.color == RbTree.RED) { nodeFixup.p.color = RbTree.BLACK; //第一种情况 uncle.color = RbTree.BLACK; //第一种情况 nodeFixup.p.p.color = RbTree.RED; //第一种情况 nodeFixup = nodeFixup.p.p; //第一种情况 } else { if (nodeFixup == nodeFixup.p.right) { nodeFixup = nodeFixup.p; //第二种情况 leftRotate(tree, nodeFixup); //第二种情况 } else { nodeFixup.p.color = RbTree.BLACK; //第三种情况 nodeFixup.p.p.color = RbTree.RED; //第三种情况 rightRotate(tree, nodeFixup.p.p); //第三种情况 } } } else { uncle = nodeFixup.p.p.left; if (uncle != null && uncle.color == RbTree.RED) { nodeFixup.p.color = RbTree.BLACK;//对称的第一种情况 uncle.color = RbTree.BLACK; //对称的第一种情况 nodeFixup.p.p.color = RbTree.RED;//对称的第一种情况 nodeFixup = nodeFixup.p.p; //对称的第一种情况 } else { if (nodeFixup == nodeFixup.p.left) { nodeFixup = nodeFixup.p; //对称的第二种情况 rightRotate(tree, nodeFixup); //对称的第二种情况 } else { nodeFixup.p.color = RbTree.BLACK; //对称的第三种情况 nodeFixup.p.p.color = RbTree.RED; //对称的第三种情况 leftRotate(tree, nodeFixup.p.p); //对称的第三种情况 } } } } tree.root.color = RbTree.BLACK; // 最后，如果根是红色，直接赋值为黑色，应对空树插入情况 }
 public static void main(String[] args) { int[] array = new int[] {11,9,8,7,6,5,4,3,2,1}; System.out.println(Arrays.toString(array)); RbTree tree = new RbTree(); for (int i = 0; i < array.length; i++) { RbNode newNode = new RbNode(); newNode.aValue = array[i];  tree.treeInsert(tree, newNode); }  System.out.print("walk tree: "); tree.accessTree(tree.root); System.out.println();
 }}