vlambda博客
学习文章列表

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

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

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

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指针指向其父结点,然后对其父结点执行旋操作

第三种情况:如果要调整的结点的父结点是红色,其叔父结点是黑色,并且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();
}}





------结束------