算法11---红黑树不带父结点指针的插入实现

  1 #include <iostream>  2 using namespace std;  3 #define BLACK 0  4 #define RED 1  5 #define Nil -1  6 #define LEN sizeof(struct Tree)  7 struct Tree  8 {  9    struct Tree*left; 10    struct Tree*right; 11    int key; 12    int color; 13 }; 14 struct Tree*root=NULL; 15 struct Tree*nil=NULL; 16 //非递归版本的二叉查找树查找函数 17 struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k,struct Tree*&p1,struct Tree*&p2) 18 {// 19     while (x!=nil&&k!=x->key) 20     { 21         p1=x; 22         if (k<x->key) 23         { 24             x=x->left; 25         } 26         else x=x->right; 27         if(k!=x->key)//如果没找到了待查找值，那么继续记录其祖父和父结点值。 28         { 29             p2=p1; 30             p1=x; 31         } 32     } 33     return x; 34 } 35 void LEFT_ROTATE(struct Tree*T,struct Tree*x) 36 {//左旋转：分三个步骤①②③来叙述旋转代码的。 37     struct Tree*p1=nil,*p2=nil; 38     struct Tree*y=x->right;//设置y结点。 39     x->right=y->left;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。① 40     ITERATIVE_TREE_SEARCH(root,x->key,p1,p2); 41     if(p1==nil)//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。② 42     { 43        root=y; 44     } 45     else if(x==p1->left) 46     { 47        p1->left=y; 48     } 49     else p1->right=y; 50     y->left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③ 51 } 52 void RIGHT_ROTATE(struct Tree*T,struct Tree*x) 53 {//右旋转 54     struct Tree*p1=nil,*p2=nil; 55     struct Tree*y=x->left; 56     x->left=y->right; 57     ITERATIVE_TREE_SEARCH(root,x->key,p1,p2); 58     if(p1==nil) 59     { 60         root=y; 61     } 62     else if(x==p1->right) 63     { 64         p1->right=y; 65     } 66     else p1->left=y; 67     y->right=x; 68 } 69 void RB_INSERT_INSERT_FIXUP(struct Tree*T,struct Tree*z) 70 { 71    struct Tree*p1=nil,*p2=nil;  72    ITERATIVE_TREE_SEARCH(root,z->key,p1,p2);//p1=z->parent,p2=z->parent->parent 73    while (1) 74    { 75        ITERATIVE_TREE_SEARCH(root,z->key,p1,p2);//p1是父结点 p2是祖父结点 76        if (p1->color!=RED) 77        { 78            break; 79        } 80        if (p1==p2->left) 81        { 82            struct Tree*y=p2->right;//叔结点 83            if (y->color==RED)//情况一：叔结点为红色 84            {//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题 85                p1->color=BLACK; 86                y->color=BLACK; 87                p2->color=RED; 88                z=p2;//把z的祖父结点当成新结点z进入下一次循环 89            } 90            else 91            { 92                if (z==p1->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点 93                {//使用一个左旋让情况2转变为情况3 94                    z=p1; 95                    LEFT_ROTATE(T,z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。 96                 ITERATIVE_TREE_SEARCH(root,z->key,p1,p2);//p1=z->parent,p2=z->parent->parent 97                } 98                p1->color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5。 99                p2->color=RED;100                if(p2!=nil) RIGHT_ROTATE(T,p2);//由于p2可能是叶子结点，所以最好还是用一个if判断101            }102        }103        else//下面else分支类似于上面104        {105            struct Tree*y=p2->left;106            if (y->color==RED)107            {108                p1->color=BLACK;109                y->color=BLACK;110                p2->color=RED;111                z=p2;112            }113            else114            {115                if (z==p1->left)116                {117                    z=p1;118                    RIGHT_ROTATE(T,z);119                    ITERATIVE_TREE_SEARCH(root,z->key,p1,p2);120                }121                p1->color=BLACK;122                p2->color=RED;123                if(p2!=nil) LEFT_ROTATE(T,p2);124            }125        }126    }127    root->color=BLACK;//最后给根结点着为黑色。128 }129 void RB_INSERT(struct Tree*T,struct Tree*z)130 {131     struct Tree*y=nil;132     struct Tree*x=root;133     while (x!=nil)134     {135         y=x;136         if (z->key<x->key)137         {138             x=x->left;139         }140         else x=x->right;141     }142     if (y==nil)143     {144         root=z;145     }146     else if(z->key<y->key)147     {148         y->left=z;149     }150     else y->right=z;151     z->left=nil;152     z->right=nil;153     z->color=RED;154     RB_INSERT_INSERT_FIXUP(T,z);155 }156 //中序遍历157 void InOderTraverse(struct Tree *p)158 {159     if (p!=nil)160     {       161         InOderTraverse(p->left);162         cout<<p->key<<" "<<p->color<<" "<<endl;163         InOderTraverse(p->right);164     }165 }166 void main()167 {168     nil=new struct Tree[LEN];169     nil->key=Nil;nil->color=BLACK;170     root=nil;171     int i=0;172     struct Tree*ROOT=new struct Tree[LEN];173     cin>>ROOT->key;174     RB_INSERT(nil,ROOT);175     root=ROOT;176     while (i!=12)177     {178         struct Tree*z=new struct Tree[LEN];179         cin>>z->key;180         RB_INSERT(root,z);181         i++;182     }183     InOderTraverse(root);184 }