二叉查找树与红黑树原理和程序全面介绍
转载请注明出处http://blog.csdn.net/yankai0219/article/details/8273542
学习方法：我主要是参考算法导论以及Nginx中rbtree.h和rbtree.c两部分内容来学习红黑树的。网上有很多关于红黑树的介绍，不可否认，有很多文章讲的很详细，但是我想经典毕竟是经典，去阅读算法导论，将会使你更加明白红黑树的原理。一句话，读算法导论，学红黑树。
0.序
一.二叉查找树
1.性质
2.叶子结点的表示方法：
3.程序中所使用的数据结构：
4.操作之查找
5.操作之某个结点的孩子中最小的孩子结点
6.创建结点
7.遍历二叉树（中序遍历）
8.操作之插入结点
9.操作之删除结点
10.测试程序：
二、红黑树
<一>.红黑树插入的步骤
<二>红黑树插入的修正。
<三>红黑树删除的修正
<四>红黑树删除的实际操作
<五>红黑树删除的总结
<六>红黑树删除的完整代码
0.序 红黑树是块硬骨头。其硬在红黑树必须满足那5条性质。其中4）红结点必须有两个黑孩子结点 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。这两个性质是在插入与删除中会被破坏的性质。插入破坏性质4，删除破坏性质5. 红黑树的5条性质：1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
当然红黑树本质上是一个二叉查找树，因此为了研究红黑树，我们首先必须学习二叉查找树。
一.二叉查找树 1.性质 学习一个数据结构，必须先明白它的一些性质。对于二叉查找树，其性质： 结点的左子树总是小于该结点；结点的右子树总是大于该结点。 2.叶子结点的表示方法： 在算法导论中，叶子结点的表示是用一个结点nil[T]来表示。所有的叶子结点都指向这个结点nil[T]，该结点为哨子结点，与普通结点具有相同的域。如下图所示，下图是借用算法导论中红黑树的图来进行说明。 注意：叶子结点的描述对于后续的操作十分重要
3.程序中所使用的数据结构：（这儿使用的红黑树中的数据结构，去掉color成员变量即可） 1）结点结构，包括key,left,right,parent,color 2）树的结构，包含根结点root，叶子节点sentinel，以及插入函数insert（这个是在红黑树中使用）typedef struct rbtree_node_s rbtree_node_t;typedef struct rbtree_s rbtree_t;typedef void (*insert_node_to_tree_pt)( rbtree_node_t * temp,rbtree_node_t * sentinel,rbtree_node_t * node);
struct rbtree_node_s { rbtree_node_t * left; rbtree_node_t * right; rbtree_node_t * parent; int key; int color;/*color = 1,red;color = 0,black*/};struct rbtree_s{ rbtree_node_t * root; rbtree_node_t * sentinel; insert_node_to_tree_pt insert;
};
4.操作之查找 对于二叉查找树的查找而言，十分简单。 查找可以采用递归的做法，但是递归调用函数，会造成很多资源的浪费。采用非递归方式来进行查找。rbtree_node_t * search_node( rbtree_node_t *node ,rbtree_node_t * sentinel,int key){ rbtree_node_t * temp = node; for(;;){ if(temp == sentinel){ break; } if(temp->key < key) temp = temp->right ; else if (temp->key > key) temp = temp->left ; if(temp->key == key) break; } return temp;} 5.操作之某个结点的孩子中最小的孩子结点 对于二叉查找树而言，其孩子结点中最小的孩子结点，肯定是其最左下角的孩子结点。rbtree_node_t * minimum( rbtree_node_t * node,rbtree_node_t * sentinel){ rbtree_node_t *temp = node; for(;temp-> left != sentinel;){ temp = temp-> left; } return temp;}6.创建结点rbtree_node_t * rbtree_create_node( int key){ rbtree_node_t * newnode = NULL; newnode = ( rbtree_node_t *)malloc(sizeof( rbtree_node_t)); if(NULL == newnode) return NULL; memset(newnode,0,sizeof(rbtree_node_t)); newnode-> key = key;
return newnode;}
7.遍历二叉树（中序遍历）void rbtree_traverse( rbtree_node_t *node,rbtree_node_t * sentinel){ if(node == sentinel) return ; rbtree_traverse(node-> left,sentinel); printf("key : %d color :%d\n" ,node->key,node-> color); rbtree_traverse(node-> right,sentinel);}
8.操作之插入结点
二叉查找树的插入结点A比较简单，只要找到叶子结点，用结点A替换掉这个叶子结点即可。特别注意的是指针间的变化。即插入结点为node。切记一定要对插入结点node的指针进行修改。 首先，必须考虑的是空树的情况，因为如果是空树，我们必须修改rbtree_t中root指针。if(rbtree->root == rbtree->sentinel){ /*empty tree*/ rbtree-> root = node; node ->parent = rbtree->sentinel; node->left = rbtree-> sentinel; node->right = rbtree-> sentinel; return ; }
其次我们要找到 插入该结点node的位置。该 位置为叶子结点，我们需要找到这个位置的父结点，记该父结点为temp。for(;;){/*no-empty tree*/ if(temp->key < node->key) pp = &temp->right; else if (temp->key > node-> key) pp = &temp->left; else{ printf("existing node\n" ); return; } if(*pp == rbtree-> sentinel) break; temp = * pp; }
最后，我们需要修改该父结点temp和结点node的指针即可。/*modify pointer*/ if(temp->key < node->key) temp-> right = node; else temp-> left = node;
node-> parent = temp; node-> left = rbtree->sentinel ; node-> right = rbtree->sentinel; 二叉树插入的完整代码void insert_node_to_tree( rbtree_t *rbtree,rbtree_node_t * node){ rbtree_node_t ** pp; rbtree_node_t * temp = rbtree->root ; if(rbtree->root == rbtree->sentinel){ /*empty tree*/ rbtree-> root = node; node -> parent = rbtree-> sentinel ; node-> left = rbtree-> sentinel ; node-> right = rbtree-> sentinel ;
return ; } /*find the location where the node will insert into * temp is used to store the node which is the last non-leaf node * the location is the leaf child of temp * */ for(;;){/*no-empty tree*/ if(temp->key < node->key) pp = &temp->right ; else if (temp->key > node-> key) pp = &temp->left ; else{ printf("existing node\n" ); return; } if(*pp == rbtree->sentinel ) break; temp = *pp; } /*modify pointer*/
if(temp->key < node->key) temp-> right = node; else temp-> left = node;
node-> parent = temp; node-> left = rbtree->sentinel ; node-> right = rbtree->sentinel ; return ;
}
9.操作之删除结点 我们记删除的结点为node，实际被删除的结点为subst，要取代该删除结点subst的结点为temp，叶子结点为sentinel 1）删除分为几种情况：
case1:删除结点node的两个孩子均为叶子结点sentinel，那么subst就是node，temp为叶子结点，直接删除即可。 case2：删除结点node只有一个孩子child，那么subst就是node，temp就是该孩子结点child，更改其指针即可。 case3：情况稍微复杂。删除结点node有两个孩子结点lchild 和rchild，我们要寻找rchild这颗子树上最小的结minnode，那么subst就是minnode。 令node的key的取值等于minnode的key的取值，然后删除subst（也就是minnode）即可，情况转化为case1 or case2。2）我们将上面这三种情况进一步说明： 上述三种情况中，有以下几个共性和个性点。共性1：都是实际删除结点subst的父结点的孩子指针 =取代subst的结点 temp。共性2：都要修改temp的父结点指针（即使temp为叶子结点），temp的父结点指针即为subst的父结点指针。通过共性1和共性2，实现了这一对结点中parent指针和left、right指针的对应，这种对应关系，在二叉树中是十分重要的。（算法导论中关于叶子结点的说明：对于一颗红黑树T来说，哨兵nil[T]是一个与树内普通结点有相同域的对象。它的color域为BLACK，而它的其他域-p,left,right and key 可以设置成任意允许的值。） 终结版说明： 我们可以将上述三种情况概括为一种通用的方式。我们会发现上述三种情况都是对真正要删除的结点进行处理。 （1）首先寻找真正要删除的结点subst和要取代subst的结点temp。对于case1 and case2 而言，subst就是node，temp就是subst的某个子节点；而对于case3而言，subst是node右子树的最小结点，temp就是subst的右结点（因为如果subst有左节点，那么subst就不是node的右子树的最小结点了）。因此只要找到subst，即可找到结点temp。
对于case3，需要更加详细的说明：
根据叔叔结点颜色，分为case1 ， case2+case3 根据左右结点，分为case2 ，case3关于case2 和case3的区别 case2：node和P[node]不是同为左节点或者同为右结点。举例：P[node]为P[P[node]]的左结点，然而node为P[node]的右结点，二者不同为左节点或者同为右结点，因此为case2.反之，如果同为左节点或者同为右结点，就是case3. 详细说明： case1:如果node的叔叔结点temp为红色，那么修改temp 和P[node]，即P[P[node]] 的颜色，同时修改node为P[P[node]]。（为什么修改P[P[node]]的颜色，因为将temp 和P[node]变为黑色时，我们必须减少该子树上的黑色结点，才能使其满足性质5）。 temp = node->parent ->parent-> right;
修正 完整代码： while((node != *root) && (node_is_red(node-> parent))){ if(node->parent == node->parent-> parent->left ){ temp = node-> parent->parent ->right;
详细描述： 1）如果 被删除的结点subst为红色，则不需要进行修正 red = node_is_red(subst); if(1 == red){ printf("delete red node\n" ); return ; } 2）如果temp为根结点或者temp为红色，那么对其染黑即可。while ((temp != rbtree->root) && (node_is_black( temp)) ) 不进入该while 循环 node_black (temp); 3）两大类的区分条件if (temp == temp->parent-> left){/* temp is left node*/ case1:双黑结点temp的兄弟结点为红色时，我们需要通过旋转将temp的兄弟结点变为黑色，从而将其转化为case2、case3、case4这三种情况。我们对temp的父结点进行旋转，通过旋转后，temp的兄弟结点w的一个子节点变为双黑结点的新的兄弟结点，新的兄弟结点为黑色。同时，我们必须在旋转的同时，进行变色，不然会影响性质5.下图给出了case1只是旋转不变色以及case1正确时的两种情况。 概括为：旋转+变色，侄子结点变兄弟。 if(node_is_red(w)){ /*it is essential to change color*/ node_black(w); node_red(temp-> parent); rbtree_left_rotate(&rbtree-> root,rbtree->sentinel ,temp->parent); /*rotate temp->parent*/ w = temp->parent ->right; }
<五>红黑树删除的总结
