理解红黑树(1)

转自 http://blog.chinaunix.net/uid-27767798-id-3339483.html

红黑树是一种二叉查找树,它是在1972年由Rudolf Bayer发明的,它的性能优于平衡2叉树(avl树),因为avl树过分追求平衡,avl树要求任何节点的左右子树高度之差不能大于1,而红黑树做到的是任何节点的左右子
树高度差不会超过2倍(左子树的高度不会大于右子树高度的2倍,或者右子树的高度不会大于左子树的高度的2倍),由此看出avl树如果要保持平衡需要付出更多的旋转(左旋,右旋),avl更平衡意味着avl树比红黑树的高度更低,查询时更快一些,但是过多旋转的时间代价大于查询带来的优势。红黑树的应用:jdk中的treeMap,内核中CFS调度根据vruntime(虚拟运行时间),来为进程建立红黑树结构,等等
红黑树的性质:
    1.节点不是红色的就是黑色的。
    2.根节点是黑色的
    3.如果一个节点是红色的,那么他们的孩子都必须是红色的(这一条性质也说明这个节点的父节点肯定是黑色,不会存在两个相邻的红色节点)
    4.对于每个节点到其叶子节点的黑色节点的数量是相同的
C语言的实现:
1.涉及到的数据结构:

  1. typedef struct _node {
  2. int color;//代表节点的颜色1表示黑色节点,0表示红色节点
  3.   struct _node *parent;
  4.  struct _node *left;
  5.   struct _node *right;
  6. int value;//代表节点的值
  7. } node;

2.节点操作:

  1. 右旋操作围绕4节点旋转,代码如下:
  2.  void rotateRight(node *target){//如上图4节点就是参数target
  3.      node *left=target>left;//left节点是2节点
  4.      node *parent=target>parent;//parentNode是target的父节点
  5. if(parent!=NULL){
  6. left>parent= parent;//如果父节点不为空,设置父节点的父子关系
  7. if(parent>left==target)
  8.               parent>left=left;//设置父节点到子节点的关系
  9. else
  10.              parent>right=left;//设置父节点到子节点的关系
  11. }
  12.       node *move=left>right;//move节点代表3节点
  13.       left->parent=target->parent;                               
  14.       target>parent=left;//设置target节点到新父节点2的关系
  15. left>right=target;//设置left节点到target节点的关系
  16. if(move!=NULL){//设置move节点(3节点的父子关系)
  17.           target>left=move;//target的左节点是3节点
  18.           move>parent=target;//3节点的父节点target节点
  19. }
  20. if(target==root)
  21.          root=left;                 //如果旋转的节点是跟节点,需要更新跟节点引用
  22. }

  1. void rotateLeft(node *target){//如上图5节点就是参数target
  2.     node *right=target>right;//right节点是7节点
  3.     node *parent=target>parent;//parentNode是target的父节点
  4. if(parent!=NULL){
  5. right>parent= parent;//如果父节点不为空,设置父节点的父子关系
  6. if(parent>right==target)
  7.              parent>right=right;//设置父节点到子节点的关系
  8. else
  9.              parent>left=right;//设置父节点到子节点的关系
  10.      }
  11.      node *move=right>left;//move节点代表7节点
  12.      right->parent=target->parent;
  13.      target>parent=right;//设置target节点到新父节点7的关系
  14. right>left=target;//设置left节点到target节点的关系
  15. if(move!=NULL){//设置move节点(6节点的父子关系)
  16.         target>right=move;//target的左节点是3节点
  17.         move>parent=target;//6节点的父节点target节点
  18. }
  19. if(target==root)
  20.         root=right;                   //如果旋转的节点是跟节点,需要更新跟节点引用
  21. }

节点的后继节点(节点删除时会用到)

  1. node* successor(node *target){
  2.    node* temp;
  3.    if(target->right!=NULL){ //case1 当target节点有右孩子时,返回右子树中最小的节点,即7节点           
  4.       temp=target->right; 
  5.       while(temp->left!=NULL)
  6.          temp=temp->left;
  7.       return temp;
  8.    }
  9.    while(temp->parent!=NULL&&temp==temp->parent->right){ 
  10.    //case 2 当左子树为空时,可以理解为比7节点 小的,但是小节点中最大的节点,这个节点就应该是7节点的             左子树中最大的节点,即6节点。
  11.       temp=temp->parent;
  12.    }
  13.    return temp->parent;
  14. }

红黑树的节点的插入过程,和普通的二叉查找树的插入过程类似。只是每个节点多了一个color域,代表节点的颜色(红色,黑色),新插入的节点的颜色是红色的。每个节点插入之后需要看一下当前插入节点的parent节点是否为红色,如果为黑色,则2叉树继续保持红黑树性质3,4,如果为红色,破坏了红黑树性质3,这时需要调整一下节点节点的颜色。所以当插入节点的父节点为红色时,插入后的节点调整需要分为3case

case1:第一种情况的条件是uncle节点不为空,并且uncle节点为红色节点。target节点是parent节点的左孩子或者右孩子,插入target节点之前,会保证数据结构中没有相邻的红色节点,且到叶子节点的黑色数目相同,这时插入target节点,只需要把parent节点,uncle节点变成黑色,grand节点变为红色即可,这样把grand节点的黑色下降到了孩子节点上(parentuncle),保持了没有相邻的红色节点,且到叶子节点黑色数目相同,但是这样把grand节点变成了红色,可能会影响grand的父节点的红黑树性质(如果grand->parent节点为红色),所以需要把target节点变成grand节点,递归grand节点之上的数据结构。

case2是个过渡阶段,目的是让target节点为parent节点的左孩子,这样在后面的右旋时,target节点才不会成为grand的左孩子,正确的做法是交换targetparent节点,然后左旋target节点,进入case3,结果如右图。反之如果在case2中直接右旋grand节点,(目的是保持没有相邻的红色节点,同时黑色节点数量保持一致)会出现下面几种情况(列举几个都不是不可取的):

第一种情况错误的旋转,交换parent节点和grand结果的颜色,显然这样的结果违反了不能出现两个连续的红色节点的性质

第二种情况错误的旋转,交换uncle节点和parent节点的颜色,同时uncle节点为红色,这样会导致uncle左右子树可能出现连续两个红色节点,剩下的错误旋转情况都是显而易见的,不是黑色节点的个数多了就是违反了红色节点不能相邻。

case3情况是插入的target节点是parent节点左孩子,或是右孩子通过case2的操作变成了左孩子,这种情况直接右旋grand节点,并且交换parent节点和grand节点的颜色即可,这种情况不用在递归parent节点的上层数据结构了因为从grand节点的父节点看到的子节点就是黑色的,case3转换完毕后子节点还是黑色的,并且左右子树黑节点的数量维持不变,所以这种情况不用递归父节点的数据结构了。

插入过程的最后需要将root节点置为黑色,这是因为,case1中有可能grand节点就是root节点,case1的最后将root置为了红色,这时root节点没有父节点了,需要保持红黑树的性质,将root节点置为黑色。

  1. node* insert(node *parent,int data){
  2. if(parent>value>data){//如果data比parent小,则插入parent的左子树
  3. if(parent>left==NULL){//为空直接插入节点
  4.               node* result=malloc(sizeof(node));//设置新节点和parent节点的关系
  5.               result>value=data;
  6.               result>parent=parent;
  7.               parent>left=result;
  8.               result>color=0;
  9.               insertAdjust(result);//新插入节点需要调整一下位置(case1,2,3)
  10.              return result;
  11. }else{
  12.               return insert(parent>left,data);
  13. }
  14. }else{
  15. if(parent>right==NULL){
  16.               node* result=malloc(sizeof(node));
  17.               result>value=data;
  18.              result>parent=parent;
  19.               parent>right=result;
  20.              result>color=0;
  21.              insertAdjust(result);
  22.               return;
  23. }else{
  24.               return insert(parent>right,data);
  25. }
  26. }
  27. }
  1. 插入调整:
  2. void insertAdjust(node *insertNode){
  3.   node* temp=insertNode;
  4. while(temp!=NULL&&temp!=root&&temp>parent>color==0){
  5. //如果父节点为红色,就需要调整了
  6.      node *parent=temp>parent;
  7.      node *grandNode=temp>parent>parent;
  8. //不需要判断grand节点是否为null,因为每次 置root为黑色了,如果parent为红色,必然有grand节点
  9. if(parent==grandNode>left){//case1
  10.          node *uncle=grandNode>right;
  11. if(uncle&&uncle>color==0){
  12.                 grandNode>color=0;
  13.                 parent>color=1;
  14.                 uncle>color=1;
  15.                 temp=grandNode;//递归grand节点之上的数据结构
  16. }else{
  17. if(temp==parent>right){//case2
  18.                    temp=temp>parent;           //交换父节点和当前插入节点
  19.                    rotateLeft(temp);
  20. }
  21.                temp>parent>color=1;//parent节点置为黑色
  22.                temp>parent>parent>color=0;//grand节点置为红色
  23.                rotateRight(temp>parent>parent);//右旋grand节点
  24. }
  25. }
  26. else{
  27.            node *uncle=grandNode>left;
  28. if(uncle&&uncle>color==0){
  29.                grandNode>color=0;
  30.                parent>color=1;
  31.                grandNode>left>color=1;
  32.                temp=grandNode;
  33. }else{
  34. if(temp==parent>left){
  35.                   temp=temp>parent;
  36.                   rotateRight(temp);
  37. }
  38.               temp>parent>color=1;
  39.               temp>parent>parent>color=0;
  40.               rotateLeft(temp>parent>parent);
  41. }
  42. }
  43.     root>color=1;
  44. }
  45. }
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注