红黑树 C++实现


高度为h的二叉查找树在进行插入删除等操作时，时间都是O(h),当树的高度较低的时候，有着很好的执行速度。但是当树的高度较高的时候，这些操作的效率可能并没预想的好。红黑树是一种保证在最坏情况下，操作时间为O(lgn)的一种接近平衡的二叉搜索树，并不像AVL树那样，是严格的高度平衡的。

[cpp]
  1. //A binary search tree is a red-black tree if it satisfies the following red-black properties:   
  2. //  Every node is either red or black.   
  3. //  The root is black.   
  4. //  Every leaf (NIL) is black.   
  5. //  If a node is red, then both its children are black.   
  6. //  For each node, all paths from the node to descendant leaves contain the same number of black nodes.  
上面是红黑树的五个基本性质，只要满足了上面五个性质的二叉排序树就是红黑树。上面第四个性质有的书上面也转化为，红黑树中从根到叶子节点的任何一条路径上，不可以出现连续的两个红色结点。这个性质在维护红黑树的过程中是很重要的。

红黑树的基本操作和二叉排序树的可以说是一样的，也是搜索，插入，删除。

搜索没什么好说的，和二叉排序树的搜索是一样的。

在说插入之前，先说下旋转操作，由于在维护红黑树的五个性质的保持的过程中，需要改变相关结点之间的父子或者是兄弟关系等，这些操作就用旋转来实现，其实就是通过改变指针的指向来实现，和AVL树一样，有两种基本的旋转，左旋和右旋，如下图所示的一样


在插入操作中，先和二叉排序树一样，先找到可以插入的位置，然后插好后，先将该结点涂为红色，然后再对插入后的新的红黑树进行结构的检测，看看该树是否依旧满足红黑树的五个性质。

在将一个红色结点插入红黑树之后，会破坏它的那些性质呢？那就是第二个和第四个啦，就是根必须为黑色和红色结点不可以有红色子树这两个性质。至于为什么大家可以自己想下。

下面先贴出插入算法的伪代码，然后再大概地分析一下，伪代码是算法导论上的

[cpp]
  1. RB-INSERT(T, z)  
  2.  1  y ← nil[T]  
  3.  2  x ← root[T]  
  4.  3  while x ≠ nil[T]  
  5.  4      do y ← x  
  6.  5         if key[z] < key[x]  
  7.  6            then x ← left[x]  
  8.  7            else x ← right[x]  
  9.  8  p[z] ← y  
  10.  9  if y = nil[T]  
  11. 10     then root[T] ← z  
  12. 11     else if key[z] < key[y]  
  13. 12             then left[y] ← z  
  14. 13             else right[y] ← z  
  15. 14  left[z] ← nil[T]  
  16. 15  right[z] ← nil[T]  
  17. 16  color[z] ← RED  
  18. 17  RB-INSERT-FIXUP(T, z)  

[cpp]
  1. RB-INSERT-FIXUP(T, z)  
  2.  1 while color[p[z]] = RED  
  3.  2     do if p[z] = left[p[p[z]]]  
  4.  3           then y ← right[p[p[z]]]  
  5.  4                if color[y] = RED  
  6.  5                   then color[p[z]] ← BLACK                    ▹ Case 1  
  7.  6                        color[y] ← BLACK                       ▹ Case 1  
  8.  7                        color[p[p[z]]] ← RED                   ▹ Case 1  
  9.  8                        z ← p[p[z]]                            ▹ Case 1  
  10.  9                   else if z = right[p[z]]  
  11. 10                           then z ← p[z]                       ▹ Case 2  
  12. 11                                LEFT-ROTATE(T, z)              ▹ Case 2  
  13. 12                           color[p[z]] ← BLACK                 ▹ Case 3  
  14. 13                           color[p[p[z]]] ← RED                ▹ Case 3  
  15. 14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3  
  16. 15           else (same as then clause  
  17.                          with "right" and "left" exchanged)  
  18. 16 color[root[T]] ← BLACK  

其中插入的主调函数RB_INSERT是在二叉查找树的基础上进行修改的，只是将判断指针是否为空的改为是否指向哨兵结点，以及在最后的部分将插入结点的颜色设置为红色，然后就调用插入辅助函数 RB_INSERT_FIXUP 来调整红黑树的结构。在这个调整函数中，有三种情况，其中case2和case3不是互斥的，case2是在case3之内的。这点在看伪代码的时候如果不熟悉它的语法结构，只是形式上的照打代码，那就会出错了，当然如果在理解整个调整过程的前提下，那么也会知道那里是不会互斥的。

前面说了，把一个红结点插进去，只会破坏红黑树的第二和第四条性质，就是树根可能会被变为红色，还有红黑树的某个红色内结点的子树中会有红子树，上面的这个辅助函数就是来维护这两个性质的，其中在第16行，将根结点的颜色设置为黑色，保证了第一条性质的成立，所以函数上面的while循环就是用来维护红黑树的第四条性质的。

分了6种情况，其中三种是对称的，伪代码中没有给出，在写代码的时候只需要把左子树改为右子树，左旋改为右旋就可以了。

分别是以下的三种情况以及解决方法：



在上面的图片中已经演示得很清楚，对应的每种情况是怎样的解决方法。想更加详细了解的同学可以看看算法导论，或者自己看着这几种情况对照代码画一下图，就会理解的。

利用一个数组元素来构建一棵红黑树的过程也就是从一棵空树一步一步插入最后得到一棵树。

  • 1
  • 2
  • 3
  • 4
  • 下一页

相关内容