1、红黑树

(1)、概念

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

ii>根结点为黑的；

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

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

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

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

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

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

3、红黑树与AVL树

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

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

4、红黑树的插入

全部代码用C实现：

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

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

结构体控制头：

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

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

模型示意图如下：

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

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

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

(1)、错误的方式

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

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

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

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

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

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

左旋代码实现：

voidleftRotate(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;}elseif(p==p->parent->leftChild){p->parent->leftChild=s;}else{p->parent->rightChild=s;}s->leftChild=p;p->parent=s;}

右旋代码实现：

voidrightRotate(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;}elseif(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_#include<malloc.h>typedefenum{RED,BLACK}Color;typedefstructNode{Colorcolor;Typedata;structNode*leftChild,*rightChild,*parent;}Node;typedefstructRBTree{Node*root;Node*NIL;}RBTree;Node*createNode();//创建一个结点空间voidinitRBTree(RBTree**t);//初始化红黑树voidleftRotate(RBTree*t,Node*p);//坐旋转函数voidrightRotate(RBTree*t,Node*p);//右旋转函数voidinsertFixup(RBTree*t,Node*x);//插入的调整函数boolinsert(RBTree*t,Typex);//插入函数voidshowRBTree(RBTreerb);//显示函数voidshow(RBTreerb,Node*t);//真正的显示函数voidshow(RBTreerb,Node*t){if(t!=rb.NIL){show(rb,t->leftChild);printf("%d:%d\n",t->data,t->color);show(rb,t->rightChild);}}voidshowRBTree(RBTreerb){show(rb,rb.root);}boolinsert(RBTree*t,Typex){Node*s=t->root;Node*p=t->NIL;while(s!=t->NIL){//找插入位置p=s;if(p->data==x){returnfalse;}elseif(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;}elseif(x<p->data){p->leftChild=q;}else{p->rightChild=q;}q->leftChild=t->NIL;//都指向空结点q->rightChild=t->NIL;q->color=RED;//插入结点颜色为红insertFixup(t,q);//调用一个调整函数returntrue;}voidinsertFixup(RBTree*t,Node*x){Node*s;while(x->parent->color==RED){if(x->parent==x->parent->parent->leftChild){//leftChilds=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;}elseif(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{//rightChilds=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;}elseif(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;}voidrightRotate(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;}elseif(p==p->parent->leftChild){p->parent->leftChild=s;}else{p->parent->rightChild=s;}s->rightChild=p;p->parent=s;}voidleftRotate(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;}elseif(p==p->parent->leftChild){p->parent->leftChild=s;}else{p->parent->rightChild=s;}s->leftChild=p;p->parent=s;}voidinitRBTree(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;returnp;}#endif

(2)、测试代码：

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

(3)、测试结果：

6、删除算法

红黑树的删除思路：

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

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