红黑树之插入

1、红黑树

(1)、概念

i>每个结点不是红的就是黑的；

ii>根结点为黑的；

iii>红结点的孩子必为黑结点；

iv>(除了根结点)任一结点不管通过什么路径，到达叶子节点的黑结点数目一定相同；

总结概括：一头一脚黑，黑同红不连：根为黑，到脚(叶子节点)的黑结点相同，红结点不相连；

2、递归--->一般先写if结束语句

化非递归------>用while()循环和栈;

enum{RED, BLACK}; 这个枚举是有值得，分别为0、1；

3、红黑树与AVL树

AVL树-------->由高度限定平衡，是严格意义上的平衡，绝对平衡；

RBTree------->由红黑颜色限定平衡，不是太严格；

4、红黑树的插入

全部代码用C实现：

(1)、红黑树是二叉搜索树，按二叉搜索树的大小比较进行插入；

(2)、只能插入红色结点(黑色的话不满足黑同)，红色若相连，通过旋转解决！！！

结构体控制头：

typedef struct Node{  //红黑树结点类型    Color color;  //红或黑色    Type data;    //存储的数据    struct Node *leftChild, *rightChild, *parent; //为了方便操作，左右孩子和父结点指针}Node;typedef struct RBTree{ //红黑树类型    Node *root;   //根结点    Node *NIL;    //指向一个空结点，构造了root有父结点;}RBTree;

我的想法是：用一个指向树类型的指针，申请一个树类型空间，在利用树类型空间里面的root构造一棵树；

模型示意图如下：

在产生的结点中，每个结点的左右开始都赋值为NIL；指向空结点，使root的父为空，便于操作；

只能开始插入时为红结点，最终插入完成，经过旋转可为黑色;

对于要旋转的话，有如下2大种情形：

(1)、错误的方式

直接将根结点与左右孩子交换颜色，但是就不满足根是黑色了;

(2)、正确旋转的两种方式

i>: 先做一次右单旋转，在交换1结点和2结点颜色，如下图：

ii>:先做一次先左后右的双旋转，在交换1结点和4结点的颜色，如下图：

先左后右的旋转在这里可以通过：先左旋在右旋实现；实际上只写左和右旋函数就够了;

以上的2个图在左边的，实际上在右边是为镜像，一个道理；

左旋代码实现：

void leftRotate(RBTree *t, Node *p){    Node *s = p->rightChild;    p->rightChild = s->leftChild;    if(s->leftChild != t->NIL){        s->leftChild->parent = p;    }    s->parent = p->parent;    if(p->parent == t->NIL){        t->root = s;    }else if(p == p->parent->leftChild){        p->parent->leftChild = s;    }else{         p->parent->rightChild = s;    }    s->leftChild = p;    p->parent = s;}

右旋代码实现：

void rightRotate(RBTree *t, Node *p){    Node *s = p->leftChild;    p->leftChild = s->rightChild;    if(s->rightChild != t->NIL){        s->rightChild->parent = p;    }    s->parent = p->parent;    if(p->parent == t->NIL){        t->root = s;    }else if(p == p->parent->leftChild){        p->parent->leftChild = s;    }else{        p->parent->rightChild = s;    }    s->rightChild = p;    p->parent = s;}

5、插入完整代码、测试代码、测试结果

(1)、插入代码：

#ifndef _RBTREE_H_#define _RBTREE_H_#includetypedef enum{RED, BLACK} Color;typedef struct Node{    Color color;    Type data;    struct Node *leftChild, *rightChild, *parent;}Node;typedef struct RBTree{    Node *root;    Node *NIL;}RBTree;Node *createNode();   //创建一个结点空间void initRBTree(RBTree **t);  //初始化红黑树void leftRotate(RBTree *t, Node *p);  //坐旋转函数void rightRotate(RBTree *t, Node *p);  //右旋转函数void insertFixup(RBTree *t, Node *x);   //插入的调整函数bool insert(RBTree *t, Type x);    //插入函数void showRBTree(RBTree rb);       //显示函数void show(RBTree rb, Node *t);   //真正的显示函数void show(RBTree rb, Node *t){    if(t != rb.NIL){        show(rb, t->leftChild);        printf("%d : %d\n", t->data, t->color);        show(rb, t->rightChild);    }}void showRBTree(RBTree rb){    show(rb, rb.root);}bool insert(RBTree *t, Type x){    Node *s = t->root;    Node *p = t->NIL;    while(s != t->NIL){  //找插入位置        p = s;        if(p->data == x){            return false;        }else if(x < p->data){            s = s->leftChild;        }else{            s = s->rightChild;        }    }    Node *q = createNode();    q->data = x;    q->parent = p;    if(p == t->NIL){        t->root = q;    }else if(x < p->data){        p->leftChild = q;    }else{        p->rightChild = q;    }    q->leftChild = t->NIL; //都指向空结点    q->rightChild = t->NIL;    q->color = RED;  //插入结点颜色为红    insertFixup(t, q);  //调用一个调整函数    return true;}void insertFixup(RBTree *t, Node *x){    Node *s;    while(x->parent->color == RED){        if(x->parent == x->parent->parent->leftChild){  //leftChild            s = x->parent->parent->rightChild;            if(s->color == RED){                x->parent->color = BLACK;                s->color = BLACK;                x->parent->parent->color = RED;                x = x->parent->parent;                continue;            }else if(x == x->parent->rightChild){                x = x->parent;                leftRotate(t, x);            }            x->parent->color = BLACK; //交换颜色            x->parent->parent->color = RED;            rightRotate(t, x->parent->parent);                    }else{  //rightChild          s = x->parent->parent->leftChild;            if(s->color == RED){                x->parent->color = BLACK;                s->color = BLACK;                x->parent->parent->color = RED;                x = x->parent->parent;                continue;            }else if(x == x->parent->leftChild){                x = x->parent;                rightRotate(t, x);            }            x->parent->color = BLACK;  //交换颜色            x->parent->parent->color = RED;            leftRotate(t, x->parent->parent);        }    }    t->root->color = BLACK;}void rightRotate(RBTree *t, Node *p){    Node *s = p->leftChild;    p->leftChild = s->rightChild;    if(s->rightChild != t->NIL){        s->rightChild->parent = p;    }    s->parent = p->parent;    if(p->parent == t->NIL){        t->root = s;    }else if(p == p->parent->leftChild){        p->parent->leftChild = s;    }else{        p->parent->rightChild = s;    }    s->rightChild = p;    p->parent = s;}void leftRotate(RBTree *t, Node *p){    Node *s = p->rightChild;    p->rightChild = s->leftChild;    if(s->leftChild != t->NIL){        s->leftChild->parent = p;    }    s->parent = p->parent;    if(p->parent == t->NIL){        t->root = s;    }else if(p == p->parent->leftChild){        p->parent->leftChild = s;    }else{         p->parent->rightChild = s;    }    s->leftChild = p;    p->parent = s;}    void initRBTree(RBTree **t){    (*t) = (RBTree *)malloc(sizeof(RBTree));    (*t)->NIL = createNode();    (*t)->root = (*t)->NIL;    (*t)->NIL->color = BLACK;    (*t)->NIL->data = -1;}Node *createNode(){    Node *p = (Node *)malloc(sizeof(Node));    p->color = BLACK;    p->data = 0;    p->leftChild = p->rightChild = p->parent = NULL;    return p;}#endif

(2)、测试代码：

#includetypedef int Type;#include"RBTree.h"int main(void){    RBTree *rb;    int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};    //int ar[] = {10, 7, 5};    int n = sizeof(ar)/sizeof(int);    int i;    initRBTree(&rb);    for(i = 0; i < n; i++){        insert(rb, ar[i]);    }        printf("0代表红，1代表黑\n");    showRBTree(*rb);    return 0;}

(3)、测试结果：

6、删除算法

红黑树的删除思路：

在搜索二叉树中，永远记住删除结点，先化为只有左树或右树一个分支在解决；

所以，先找到结点，在转换为只有一个分支的，在删除(只能删除红色的结点)，可能通过旋转调整函数进行平衡！！！