红黑树之插入-创新互联
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、删除算法
红黑树的删除思路:
在搜索二叉树中,永远记住删除结点,先化为只有左树或右树一个分支在解决;
所以,先找到结点,在转换为只有一个分支的,在删除(只能删除红色的结点),可能通过旋转调整函数进行平衡!!!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站题目:红黑树之插入-创新互联
本文URL:http://myzitong.com/article/csgjgp.html