B-树、B+树、红黑树

你的名字 2022-08-02 04:49 180阅读 0赞

# B-树 #

**[B-tree][]树即[B树][B]**，B即Balanced，平衡的意思，B-树又称为多路平衡查找树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，**B-tree就是指的B树。**

**一、定义**

**B-树是一种多路搜索树（并不一定是二叉的）**

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的 [树][Link 1] ，它是一种平衡的多叉树，称为B树（或B-树、B\_树）。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

[![7e3e6709c93d70cf4021a04dfddcd100bba12b92.jpg][]][7e3e6709c93d70cf4021a04dfddcd100bba12b92.jpg 1]

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故 **内部子树** 个数 k 满足：┌m/2┐ <= k <= m ；

4、所有的叶子结点都位于同一层。

在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

**![http://img851.ph.126.net/qN4ZWmgY8YXAk3rClFR-jw==/2715670575304874531.png][http_img851.ph.126.net_qN4ZWmgY8YXAk3rClFR-jw_2715670575304874531.png]**

**二、概念**

M为树的 [阶数][Link 2]，B-树或为空树，否则满足下列条件：

1.  定义任意非 [叶子结点][Link 3]最多只有M个儿子；且M>2；

2. [根结点][Link 4]的儿子数为\[2, M\]；

3.除根结点以外的非叶子结点的儿子数为\[M/2, M\]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个 [关键字][Link 5]；（至少2个关键字,根 [节点][Link 6]至少一个关键字）；

5.非叶子结点的关键字个数=指向儿子的 [指针][Link 7]个数-1；

6.非叶子结点的关键字：K\[1\], K\[2\], …, K\[m-1\]，m<M+1；且K *\[i\]< K\[i+1\] ；*

7.非叶子结点的指针：P\[1\], P\[2\], …, P\[m\]；其中P\[1\]指向 [关键字][Link 5]小于K\[1\]的子树，P\[m\]指向关键字大于K\[m-1\]的子树，其它P\[i\]指向关键字属于(K\[i-1\], K\[i\])的子树；

8.所有 [叶子结点][Link 3]位于同一层；

如：（M=3）

[![M=3的B-树][M_3_B-]][M_3_B-_M_3_B-] M=3的B-树

B-树的搜索，从 [根结点][Link 4]开始，对结点内的关键字（有序）序列进行 [二分查找][Link 8]，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子 [指针][Link 7]为空，或已经是 [叶子结点][Link 3]。

**三、特性**

1.[关键字][Link 5]集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非[叶子结点][Link 3]结束；

4.其搜索性能[等价][Link 9]于在关键字全集内做一次[二分查找][Link 8]；

5.自动层次控制；

由于限制了除[根结点][Link 4]以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B-树的性能总是等价于二分查找（与M值无关），也就没有[B树][B 1]平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟[节点][Link 6]合并.

**(1)根结点只有1个，关键字字数的范围\[1,m-1\]，分支数量范围\[2,m\]；**

**(2)除根以外的非叶结点，每个结点包含分支数范围\[\[m/2\],m\]，即关键字字数的范围是\[\[m/2\]-1,m-1\]，其中\[m/2\]表示取大于m/2的最小整数；**

**(3)非叶结点是由叶结点分裂而来的，所以叶结点关键字个数也满足\[\[m/2\]-1,m-1\]；**

**四、B树查找的算法思想**

**1、B-树的查找**

**B-树的查找过程：根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程：**

**若比结点的第一个关键字小，则查找在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。**

**2.B-树的插入**

**插入的过程分两步完成：**

**（1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。**

**（2）判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足，则说明该结点还有空位置，直接把关键字k插入到该结点的合适位置上。若不满足，说明该结点己没有空位置，需要把结点分裂成两个。**

**分裂的方法是：生成一新结点。把原结点上的关键字和k按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ -]][29_B-_ - _ -]  
[![29、B-树的插入、查找、删除 - EdwardLewis - 墨涵天地][29_B-_ - EdwardLewis -]][29_B-_ - EdwardLewis -]

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 1]][29_B-_ - _ - 1]

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 2]][29_B-_ - _ - 2]

**3、B-树的删除**

**在B-树上删除关键字k的过程分两步完成：**

**（1）利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。**

**（2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key\[i\]，则可从指针son\[i\]所指的子树中找出最小关键字Y，代替key\[i\]的位置，然后在叶结点中删去Y。**

**因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。**

**在B-树叶结点上删除一个关键字的方法是**

**首先将要删除的关键字k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：**

**（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。**

**（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。**

**调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。**

**（3）如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。**

**总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 3]][29_B-_ - _ - 3]

如图示：

a、**被删关键字****Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 4]][29_B-_ - _ - 4]

**b、被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。调整过程如上面所述。**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 5]][29_B-_ - _ - 5]

**c、被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，假设该结点有右兄弟，且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后，它所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中（若无右兄弟，则合并到左兄弟结点中）。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 6]][29_B-_ - _ - 6]

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 7]][29_B-_ - _ - 7]

**五、B-树的C语言描述**

**1、存储结构**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 8]][29_B-_ - _ - 8]

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 9]][29_B-_ - _ - 9]

**2、插入**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 10]][29_B-_ - _ - 10]

**3、查找**

[![29、B-树及其查找 - 墨涵 - 墨涵天地][29_B-_ - _ - 11]][29_B-_ - _ - 11]

**六、B-树的C语言实现**

**\#include "stdio.h"  
\#include "stdlib.h"  
\#include "math.h"  
\#define OK 1  
\#define ERROR -1  
\#define m 3 //3阶树  
\#define N 16 //数据元素个数  
\#define MAX 5 //字符串最大长度＋1  
typedef int KeyType;  
struct Others //记录的其它部分  
\{  
char info\[MAX\];  
\};  
struct Record  
\{  
KeyType key; //关键字  
Others others; //其它部分  
\};  
typedef struct BTNode  
\{  
int keynum; //结点中关键字个数  
BTNode \*parent;//指向双亲节点  
struct Node //结点向量类型  
\{  
KeyType key; //关键字向量  
BTNode \*ptr;//子树指针向量  
Record \*recptr; //记录向量指针  
\}node\[m+1\]; //key,recptr的0号单元未用  
\}BTNode,\*BTree;  
struct Result //B树的查找结果类型  
\{  
BTNode \*pt; //指向找到的结点  
int i; //在节点中关键字序号，1...m  
int tag; //1表示查找成功，0表示查找失败。  
\};  
  
int InitDSTable(BTree &DT)  
\{  
DT=NULL;  
return OK;  
\}//InitDSTable  
  
void DestroyDSTable(BTree &DT)  
\{  
int i;  
if(DT) //非空树  
\{  
for(i=0;i<=DT->keynum;i++)  
DestroyDSTable(DT->node\[i\].ptr);  
free(DT);  
DT=NULL;  
\}//if  
\}//DestroyDSTable  
  
int Search(BTree p,KeyType K)  
\{//在p->node\[1...keytype\].key中查找i,使得p->node\[i\].key<=K<  
//p->node\[i+1\].key  
int i=0,j;  
for(j=1;j<=p->keynum;j++)  
if(p->node\[j\].key<=K)  
i=j;  
return i;  
\}//Search  
  
void Insert(BTree &q,int i,Record \*r,BTree ap)  
\{//将r->key、r和ap分别插入到q->key\[i+1\]、  
//q->recptr\[ i+1\]和q->ptr\[i+1\]中  
int j;  
for(j=q->keynum;j>i;j--) //空出q->node\[i+1\]  
q->node\[j+1\]=q->node\[j\];  
q->node\[i+1\].key=r->key;  
q->node\[i+1\].ptr=ap; //前加入的结点，还没有儿子结点  
q->node\[i+1\].recptr=r;  
q->keynum++;  
\}//Insert  
  
void NewRoot(BTree &T,Record \*r,BTree ap)  
\{// 生成含信息(T,r,ap)的新的根结点\*T，原T和ap为子树指针  
BTree p;  
p=(BTree)malloc(sizeof(BTNode));  
p->node\[0\].ptr=T;  
T=p;  
if(T->node\[0\].ptr)  
T->node\[0\].ptr->parent=T;  
T->parent=NULL;  
T->keynum=1;  
T->node\[1\].key=r->key;  
T->node\[1\].recptr=r;  
T->node\[1\].ptr=ap;  
if(T->node\[1\].ptr)  
T->node\[1\].ptr->parent=T;  
\}//NewRoot  
  
void split(BTree &q,BTree &ap)  
\{// 将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap  
int i,s=(m+1)/2;  
ap=(BTree)malloc(sizeof(BTNode));//生成新结点ap  
ap->node\[0\].ptr=q->node\[s\].ptr;//原来结点中间位置关键字相应指针指向的子树放到  
//新生成结点的0棵子树中去  
for(i=s+1;i<=m;i++) //后一半移入ap  
\{  
ap->node\[i-s\]=q->node\[i\];  
if(ap->node\[i-s\].ptr)  
ap->node\[i-s\].ptr->parent=ap;  
\}//for  
ap->keynum=m-s;  
ap->parent=q->parent;  
q->keynum=s-1; // q的前一半保留，修改keynum  
\}//split  
  
void InsertBTree(BTree &T,Record \*r,BTree q,int i)  
\{//在m阶B树T上结点\*q的key\[i\]与key\[i+1\]之间插入关键字K的指针r。若引起  
// 结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。  
BTree ap=NULL;  
int finished=false;  
int s;  
Record \*rx;  
rx=r;  
while(q&&!finished)  
\{  
Insert(q,i,rx,ap);//将r->key、r和ap分别插入到q->key\[i+1\]、  
//q->recptr\[i+1\]和q->ptr\[i+1\]中  
if(q->keynum<m)  
finished=true;  
else  
\{//分裂结点\*q  
s=(m+1)/2;  
rx=q->node\[s\].recptr;  
split(q,ap);//将q->key\[s+1..m\],q->ptr\[s..m\]和q->recptr\[s+1..m\]  
//移入新结点\*ap  
q=q->parent;  
if(q)  
i=Search(q,rx->key);//在双亲结点\*q中查找rx->key的插入位置  
\}//else  
\}//while  
if(!finished) //T是空树(参数q初值为NULL)或根结点已分裂为  
//结点\*q和\*ap  
NewRoot(T,rx,ap);  
\}//InsertBTree  
  
Result SearchBTree(BTree T,KeyType K)  
\{// 在m阶B树T上查找关键字K，返回结果(pt,i,tag)。若查找成功，则特征值  
// tag=1，指针pt所指结点中第i个关键字等于K；否则特征值tag=0，等于K的  
// 关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间。  
BTree p=T,q=NULL; //初始化，p指向待查结点，q指向p的双亲  
int found=false;  
int i=0;  
Result r;  
while(p&&!found)  
\{  
i=Search(p,K);//p->node\[i\].key≤K<p->node\[i+1\].key  
if(i>0&&p->node\[i\].key==K)  
found=true;  
else  
\{  
q=p;  
p=p->node\[i\].ptr;//在子树中继续查找  
\}//else  
\}//while  
r.i=i;  
if(found)  
\{  
r.pt=p;  
r.tag=1;  
\}//if  
else  
\{  
r.pt=q;  
r.tag=0;  
\}//else  
return r;  
\}//SearchBTree  
  
void print(BTNode c,int i) // TraverseDSTable()调用的函数  
\{  
printf("(%d,%s)",c.node\[i\].key,c.node\[i\].recptr->others.info);  
\}//print  
void TraverseDSTable(BTree DT,void(\*Visit)(BTNode,int))  
\{// 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数  
// 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次  
int i;  
if(DT) //非空树  
\{  
if(DT->node\[0\].ptr) // 有第0棵子树  
TraverseDSTable(DT->node\[0\].ptr,Visit);  
for(i=1;i<=DT->keynum;i++)  
\{  
Visit(\*DT,i);  
if(DT->node\[i\].ptr) // 有第i棵子树  
TraverseDSTable(DT->node\[i\].ptr,Visit);  
\}//for  
\}//if  
\}//TraverseDSTable  
  
void InputBR(BTree &t,Record r\[\])  
\{  
Result s;  
for(int i=0;i<N;i++)  
\{  
s=SearchBTree(t,r\[i\].key);  
if(!s.tag)  
InsertBTree(t,&r\[i\],s.pt,s.i);  
\}  
\}//InputBR  
void UserSearch(BTree t)  
\{  
int i;  
Result s;  
printf("\\n请输入待查找记录的关键字: ");  
scanf("%d",&i);  
s=SearchBTree(t,i);  
if(s.tag)  
print(\*(s.pt),s.i);  
else  
printf("没找到");  
printf("\\n");  
\}//UserSearch  
void DeleteIt(BTree t,BTNode \*dnode,int id)  
\{  
if(dnode->keynum>=ceil(m/2))  
\{  
dnode->keynum--;  
dnode->node\[id\].ptr=NULL;  
\}//if被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。  
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node\[id+1\].ptr->keynum>(ceil(m/2)-1))  
\{  
for(int i=1;i<m&&dnode->parent->node\[i\].key < dnode->parent->node\[id+1\].ptr->node\[1\].key;i++)  
dnode->node\[i\].key=dnode->parent->node\[i\].key;  
dnode->parent->node\[1\].key=dnode->parent->node\[id+1\].ptr->node\[1\].key;  
(dnode->parent->node\[id+1\].ptr->keynum)--;  
\}//else if 被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与右兄弟调整  
else if((dnode->keynum==(ceil(m/2)-1))&&((id-1)>0 )&&dnode->parent->node\[id-1\].ptr->keynum>(ceil(m/2)-1))  
\{  
for(int i=1;i<m&&dnode->parent->node\[i\].key > dnode->parent->node\[id-1\].ptr->node\[dnode->parent->node\[id-1\].ptr->keynum\].key;i++)  
dnode->node\[i\].key=dnode->parent->node\[i\].key;  
dnode->parent->node\[1\].key=dnode->parent->node\[id-1\].ptr->node\[dnode->parent->node\[id-1\].ptr->keynum\].key;  
(dnode->parent->node\[id-1\].ptr->keynum)--;  
\}//2-else if被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与左兄弟调整  
else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node\[id+1\].ptr->keynum==(ceil(m/2)-1))  
\{  
do  
\{  
BTree tmp;  
tmp=dnode;  
dnode->parent->node\[id+1\].ptr->node\[2\]=dnode->parent->node\[id+1\].ptr->node\[1\];  
dnode->parent->node\[id+1\].ptr->node\[1\]=dnode->parent->node\[1\];  
dnode->parent->node\[id+1\].ptr->keynum++;  
dnode->parent->node\[id+1\].ptr->node\[0\].ptr=dnode->node\[1\].ptr;  
dnode->parent->keynum--;  
dnode->parent->node\[id\].ptr=NULL;  
tmp=dnode;  
if(dnode->parent->keynum>=(ceil(m/2)-1))  
dnode->parent->node\[1\]=dnode->parent->node\[2\];  
dnode=dnode->parent;  
free(tmp);  
\}while(dnode->keynum<(ceil(m/2)-1)); //双亲中keynum<  
\}//3-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设右兄弟存在  
else if((dnode->keynum==(ceil(m/2)-1))&&(id-1)>0 &&dnode->parent->node\[id-1\].ptr->keynum==(ceil(m/2)-1))  
\{  
do  
\{  
BTree tmp;  
tmp=dnode;  
dnode->parent->node\[id-1\].ptr->node\[2\]=dnode->parent->node\[id-1\].ptr->node\[1\];  
dnode->parent->node\[id-1\].ptr->node\[1\]=dnode->parent->node\[1\];  
dnode->parent->node\[id-1\].ptr->keynum++;  
dnode->parent->node\[id-1\].ptr->node\[0\].ptr=dnode->node\[1\].ptr;  
dnode->parent->keynum--;  
dnode->parent->node\[id\].ptr=NULL;  
tmp=dnode;  
if(dnode->parent->keynum>=(ceil(m/2)-1))  
dnode->parent->node\[1\]=dnode->parent->node\[2\];  
dnode=dnode->parent;  
free(tmp);  
\}while(dnode->keynum<(ceil(m/2)-1)); //双亲中keynum<  
\}//4-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设左兄弟存在  
else printf("Error!"); //出现异常  
\}//DeleteIt  
void UserDelete(BTree t)  
\{  
KeyType date;  
Result s;  
printf("Please input the date you want to delete:\\n");  
scanf("%d",&date);  
s=SearchBTree(t,date);  
if(!s.tag) printf("Search failed,no such date\\n");  
else DeleteIt(t,s.pt,s.i);  
\}//UserDelete  
  
int main()  
\{  
Record r\[N\]=\{ \{24,"1"\},\{45,"2"\},\{53,"3"\},\{12,"4"\},\{37,"5"\},  
\{50,"6"\},\{61,"7"\},\{90,"8"\},\{100,"9"\},\{70,"10"\},  
\{3,"11"\},\{30,"12"\},\{26,"13"\},\{85,"14"\},\{3,"15"\},  
\{7,"16"\}\};  
BTree t;  
InitDSTable(t);  
InputBR(t,r);  
printf("按关键字的顺序遍历B\_树:\\n");  
TraverseDSTable(t,print);  
UserSearch(t);  
UserDelete(t);  
TraverseDSTable(t,print);  
DestroyDSTable(t);  
return 1;  
\}**

**七、复杂度分析**

**B-树查找包含两种基本动作：**

**●在B-树上查找结点**

**●在结点中找关键字**

**前一操作在磁盘上进行，后一操作在内存进行。因此查找效率主要由前一操作决定。在磁盘上查找的次数取决于关键字结点在B-树上的层次数。**

**定理：若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高度h至多为logt((n+1)/2)+1，t= ceil(m/2)。也就是说根结点到关键字所在结点的路径上涉及的结点数不超过logt((n+1)/2)+1。推理如下：**

[![29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地][29_B-_ - _ - 12]][29_B-_ - _ - 12]

[![29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地][29_B-_ - _ - 13]][29_B-_ - _ - 13]

[![29、B-树的插入、查找、删除 - 墨涵 - 墨涵天地][29_B-_ - _ - 14]][29_B-_ - _ - 14]

**B+树**

**B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。**

**一、定义**

B+树是应文件系统所需而出的一种[B-树][B-]的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

1.有n棵子树的结点中含有n个[关键字][Link 5]，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的[指针][Link 7]，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是[索引][Link 10]部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

[![902397dda144ad3495c012dfd1a20cf431ad856f.jpg][]][902397dda144ad3495c012dfd1a20cf431ad856f.jpg 1]

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。  
  
二、B+树的查找、插入和删除

### B+树的查找 ###

对B+树可以进行两种查找运算：

1.从最小关键字起[顺序查找][Link 11]；

2.从根结点开始，进行随机查找。

在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

以下是从根节点查找叶子节点k的伪代码：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>Function:&nbsp;search&nbsp;(k)&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code>&nbsp; 
      <code>tree_search&nbsp;(k,&nbsp;root);&nbsp;Function:&nbsp;tree_search&nbsp;(k,&nbsp;node)&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code>&nbsp; 
      <code>node&nbsp;is&nbsp;a&nbsp;leaf&nbsp;then&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code>&nbsp; 
      <code>node;&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>switch</code>&nbsp; 
      <code>k&nbsp;</code> 
      <code>do</code>&nbsp;&nbsp;&nbsp;&nbsp; 
      <code>case</code>&nbsp; 
      <code>k&nbsp;&lt;&nbsp;k_0&nbsp;&nbsp;&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code>&nbsp; 
      <code>tree_search(k,&nbsp;p_0);&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>case</code>&nbsp; 
      <code>k_i&nbsp;≤&nbsp;k&nbsp;&lt;&nbsp;k_{i+</code> 
      <code>1</code> 
      <code>}&nbsp;&nbsp;&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code>&nbsp; 
      <code>tree_search(k,&nbsp;p_{i+</code> 
      <code>1</code> 
      <code>});&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>case</code>&nbsp; 
      <code>k_d&nbsp;≤&nbsp;k&nbsp;&nbsp;&nbsp;&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code>&nbsp; 
      <code>tree_search(k,&nbsp;p_{d+</code> 
      <code>1</code> 
      <code>});</code> 
     </div> 
     <div> 
      <code>//伪代码假设没有重复值</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

### B+树的插入 ###

**m阶B树的插入操作在叶子结点上进行，假设要插入关键值a，找到叶子结点后插入a，做如下算法判别：**

**①如果当前结点是根结点并且插入后结点[关键字][Link 5]数目小于等于m，则算法结束；**

**②如果当前结点是非根结点并且插入后结点关键字数目小于等于m，则判断若a是新[索引][Link 10]值时转步骤④后结束，若a不是新索引值则直接结束；**

**③如果插入后关键字数目大于m(阶数)，则结点先分裂成两个结点X和Y，并且他们各自所含的关键字个数分别为：u=大于(m+1)/2的最小整数，v=小于(m+1)/2的最大整数；**

**由于索引值位于结点的最左端或者最右端，不妨假设索引值位于结点最右端，有如下操作：**

**如果当前分裂成的X和Y结点原来所属的结点是根结点，则从X和Y中取出索引的关键字，将这两个关键字组成新的根结点，并且这个根结点指向X和Y，算法结束；**

**如果当前分裂成的X和Y结点原来所属的结点是非根结点，依据假设条件判断，如果a成为Y的新[索引][Link 10]值，则转步骤④得到Y的双亲结点P，如果a不是Y结点的新索引值，则求出X和Y结点的双亲结点P；然后提取X结点中的新索引值a’，在P中插入[关键字][Link 5]a’，从P开始，继续进行插入算法；**

**④提取结点原来的索引值b，自顶向下，先判断根是否含有b，是则需要先将b替换为a，然后从根结点开始，记录结点地址P，判断P的孩子是否含有索引值b而不含有索引值a，是则先将孩子结点中的b替换为a，然后将P的孩子的地址赋值给P，继续搜索，直到发现P的孩子中已经含有a值时，停止搜索，返回地址P。**

### B+树的删除 ###

**B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取[上界][Link 12]，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。  
  
三、B+树与B树的区别**

一棵m阶的B+树和m阶的B树的异同点在于：

*  所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且 叶子结点本身依关键字的大小自小而大的顺序链接。(而B 树的叶子节点并没有包括全部需要查找的信息)
 *  所有的非终端结点可以看成是索引部分， 结点中仅含有其子树根结点中最大（或最小）关键字。(而B 树的非终节点也包含需要查找的有效信息)

四、B+树与操作系统的文件索引和数据库索引

为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引？  
B+树的磁盘读写代价更低

*  B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
    
    举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶 [B-tree][B-tree 1](一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
 *  B+树的查询效率更加稳定
    
    由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在[计算机][Link 13]科学中用到的一种[数据结构][Link 14]，典型的用途是实现[关联数组][Link 15]。

它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

一、性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点（NIL节点，空节点）是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些特性确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

在很多树[数据结构][Link 14]的表示中，一个节点有可能只有一个子节点，而[叶子节点][Link 16]不包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本ul **文中我们使用 "nil 叶子" 或"空(n** l)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好象同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

注意：由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。

# 二. 数据结构定义    #

RBT数据结构在基本二叉树数据结构之上增加一个color和parent，color用于保存节点颜色，parent指向父节点。

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \#define COLOR\_RED 0
2.  \#define COLOR\_BLACK 1
3.  
4.  typedef int keyType;
5.  
6.  // 定义而二叉树节点数据结构
7.  struct BinaryTreeNode \{
8.  keyType key;
9.  int color;
10. BinaryTreeNode\* parent; // 保存父节点
11. BinaryTreeNode\* left; // left child
12. BinaryTreeNode\* right; // right child
13. \};
14. 
15. // define red-black tree node
16. typedef BinaryTreeNode rbnode;
17. 
18. // define red-black tree
19. typedef BinaryTreeNode rbtree;

# 三、 插入Key #

无论怎么样操作，性质1和性质3是始终能够保持的。**新插入节点的时候，新节点的初始颜色为红色，这样可以不直接破坏性质5**，这个时候可能性质4受到威胁，需要调整节点颜色或这左一些旋转等操作。**假设新插入的节点为N，其父节点为P，祖父节点为G，叔父节点为U**，下面具体分析一下插入新节点的各种情况。

**情形1 、空树**

当树为空的时候，直接将N节点设为黑色作为树的根节点返回。![20131207005222937][]

**情形2 、P为黑色节点**

![20131207003053968][]

图中所示为N插入到P左孩子节点中，这个过程完全满足性质 1 - 5 的要求，并没有破坏 RBT 的规则，因此，此时即可停止检查，插入过程结束。

同理，若P为黑色节点，N插入后作为P的右孩子节点也不会破坏 RBT的规则。

（下面开始讨论 P 为红色 的情形，由 性质2 推导出 G 一定存在，根据性质 4，G一定是黑色）

**情形3 、P为红色节点，U存在且为红色节点**

![20131207021556125][]这种情况下， **将G变为红色，P和U变为黑色**，这样维持了G为Root的子树内性质4和5， **然后以G作为新的插入节点，从情形1开始迭代。**

**情形4 、P为红色节点，U不存在或者U为黑色**

<table style="border-collapse:collapse; border-spacing:0px; padding:0; margin:0"> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131207013248078" alt="" width="350" height="169" style="float:left"></td> 
   <td>（a） 若P在G的左侧，插入点N也在P的左侧 ------ LL 型<br> 假设G的右侧有 路径有 x个黑色节点，则c有x个黑色节点，G为root的子树路径有x+1个黑色节点。 此时， 只需要以P为中心<strong>右旋</strong>，将P变为黑色，G变为红色，G的左子树替换为c，这样就可以继续保证以P为root的子树有x+1个黑色节点，检查停止。</td> 
  </tr> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131207015840078" alt="" width="490" height="170"></td> 
   <td>（b）若P在G的左侧，N在P的右侧&nbsp; -----LR型<br> 这时候先将节点P和节点N做调整，进行<strong>左旋</strong>，变化成（a）的形态，然后做一次<strong>右旋</strong>。到此，调整完毕。</td> 
  </tr> 
  <tr> 
   <td>图略</td> 
   <td>（c）若P在G的右侧，N在P的右侧 ----------RR型<br> 情形和（a）正好相反，做一次<strong>左旋</strong>即可。</td> 
  </tr> 
  <tr> 
   <td>图略</td> 
   <td>（d）若P在G的右侧，N在P的左侧 ----------RL型<br> 情形和（b）正好相反，先做做一次<strong>右旋，</strong>后进行一次<strong>左旋</strong>即可。</td> 
  </tr> 
 </tbody> 
</table>

RBT插入算法过程代码如下：

1.  // 向右旋转
2.  void rb\_right\_rotate(rbnode\* g) \{
3.  rbnode \* p = g->left;
4.  keyType k = g->key;
5.  g->key = p->key;
6.  p->key = k;
7.  g->left = p->left;
8.  if (NULL != p->left) \{
9.  p->left->parent = g;
10. \}
11. p->left = p->right;
12. p->right = g->right;
13. if (NULL != g->right) \{
14. g->right->parent = p;
15. \}
16. g->right = p;
17. \}
18. 
19. // 向左旋转
20. void rb\_left\_rotate(rbnode\* g) \{
21. rbnode\* p = g->right;
22. keyType k = g->key;
23. g->key = p->key;
24. p->key = k;
25. g->right = p->right;
26. if (NULL != p->right) \{
27. p->right->parent = g;
28. \}
29. p->right = p->left;
30. p->left = g->left;
31. if (NULL != g->left) \{
32. g->left->parent = p;
33. \}
34. g->left = p;
35. \}
36. 
37. // check and adjust after insertion
38. void rbt\_insert\_check(rbnode\* node) \{
39. // CASE 1 : if the node equals the root
40. // set the color of the node black and return.
41. if (NULL == node->parent) \{
42. node->color = COLOR\_BLACK;
43. return;
44. \}
45. // CASE 2 : when the parent of the node is black
46. // All features have been met, stop check and return
47. if (node->parent->color == COLOR\_BLACK) \{
48. return;
49. \}
50. 
51. // Otherwise, the the parent node is RED, and this means the grandfather node exists.
52. rbnode\* gf = node->parent->parent;
53. rbnode\* uf = (gf->left == node->parent) ? gf->right : gf->left;
54. 
55. // CASE 3 : When the uncle node exists and it's RED
56. if (NULL != uf && uf->color == COLOR\_RED) \{
57. // set parent and uncle black, set grandfather red
58. node->parent->color = COLOR\_BLACK;
59. uf->color = COLOR\_BLACK;
60. gf->color = COLOR\_RED;
61. // then re check the tree at grandfather node from CASE 1.
62. rbt\_insert\_check(gf);
63. return;
64. \}
65. 
66. // CASE 4 : when the uncle is NULL or its color is Black.
67. if (node->parent == gf->left) \{ // the node in the left of its grandfather
68. // (a) LL model
69. if (node == node->parent->left) \{ // the node in the left of its parent
70. rb\_right\_rotate(gf);
71. \}
72. // (b) LR model
73. else if (node == node->parent->right) \{ //the node in the right of its parent.
74. rb\_left\_rotate(node->parent);
75. rb\_right\_rotate(gf);
76. \}
77. \} else if (node->parent == gf->right) \{ //the node in the right of its grandfather
78. // (c) RR model
79. if (node == node->parent->right) \{ //the node in the right of its parent.
80. rb\_left\_rotate(gf);
81. \}
82. // (d) RL model
83. else if (node == node->parent->left) \{ //the node in the left of its parent.
84. rb\_right\_rotate(node->parent);
85. rb\_left\_rotate(gf);
86. \}
87. \}
88. \}
89. 
90. // 插入新的关键字
91. int rbt\_insert(rbtree\* &tree, keyType key) \{
92. if (NULL == tree) \{ // if the tree is NULL
93. tree = (rbtree\*) malloc((sizeof(rbnode)));
94. tree->key = key;
95. tree->color = COLOR\_BLACK;
96. tree->parent = tree->left = tree->right = NULL;
97. return 1;
98. \}
99. // find insert point
100. rbnode \*n = tree, \*p = tree->parent;
101. while (NULL != n) \{
102. if (key == n->key) \{
103. return 0;
104. \}
105. p = n;
106. n = (key > p->key) ? p->right : p->left;
107. \}
108. // insert the node
109. n = (rbtree\*) malloc((sizeof(rbnode)));
110. n->key = key;
111. n->color = COLOR\_RED;
112. n->parent = p;
113. n->right = n->left = NULL;
114. ((key > p->key) ? p->right : p->left) = n;
115. 
116. // adjust the tree
117. rbt\_insert\_check(n);
118. 
119. return 1;
120. \}

# 四、删除Key #

从RBT中删除指定的Key时，需要重新调整树的形态使之满足红黑树的特性。下面来具体分析一下删除Key的过程。

（1）根据key找到要删除的节点Node：如果没有找到，直接返回，否则，进行下一步操作；

（2）如果Node有两个孩子节点，那么删除Node之后该如何放置其孩子节点呢？

这个时候需要进行预处理，转化为删除只有一个孩子的节点的情形。

找到Node的中序前驱（后继）节点，将前驱（后继）节点的值复制到Node中，Node指向前驱（后继）节点；

（3）到此步骤，Node确切的指示为待删除的节点，且Node最多只有一个孩子节点。

删除Node节点，将Node的孩子节点顶替Node的位置.（注意Node为Root的情形）

（4）调整RBT树使其满足规定的5大特性。  
假设上一步中顶替上来的节点为 N ，其父节点为 P ，其兄弟节点为 S ，Sl 和 Sr 分别为 S 的左右孩子节点 ，假设 N 在 P 的左侧， 调整过程如下：  
（右侧与左侧对称，这里分析一种即可）

**情形1 、N节点为红色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211020728750" alt=""></td> 
   <td>当N节点为红色的时候，由于左侧缺少一个黑色的节点，可以将N节点的颜色修改为黑色，这样即可从新满足性质5.<br> <br> 调整完毕。</td> 
  </tr> 
 </tbody> 
</table>

**情形2、S节点为红色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211020734531" alt=""></td> 
   <td>当S节点为红色节点时，则可以将P节点向左旋转，旋转之后P为红色，S为黑色，这个时候S-Sl这条简单路径黑色节点数目合法，S-P-Sl节点数目也合法，S-P-N路径黑色节点数目少一个。<br> <br> 相当于，P的左侧删除了一个黑色节点，应当重新调整 P，S，Sl，Sr所指向的节点，进行后续操作。<br> 后续可能的情形为：3，5，6</td> 
  </tr> 
 </tbody> 
</table>

**情形3、P节点为红色，S，Sl，Sr为黑色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211020740171" alt=""></td> 
   <td>当P为红色，S为黑色，Sl和Sr均为黑色的时候，则可以简单的交换P节点和S节点的颜色，这样即可使各条简单路径的黑色节点数目和删除节点前相等。<br> <br> 调整完毕。</td> 
  </tr> 
 </tbody> 
</table>

**情形4、P，S，Sl，Sr均为黑色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211022832640" alt=""></td> 
   <td>当P、S、Sl、Sr均为黑色节点的时候，只需要简单的将S节点标记为红色，这样以P节点为根的个简单路径黑色节点数目比删除之前少一个。<br> <br> 因此，P相当与N的位置，从P的父节点开始递归进行调整。<br> （如果此时P为树的根节点，即可停止调整）</td> 
  </tr> 
 </tbody> 
</table>

**情形5、Sl为红色节点并且Sr为黑色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211023321703" alt=""></td> 
   <td>这种情况下，可以将Sl进行右旋操作，右旋之后，Sl为黑色，S为红色，Sr不变，这样保持P节点右子树中各简单路径黑色节点数目和旋转前一样。<br> 这个时候，原来的S相当于Sl的位置，Sl相当与a，Sr相当与S。<br> <br> 更新S，Sl，Sr新指向的位置，进行下一步操作。<br> 后续情形为：6.</td> 
  </tr> 
 </tbody> 
</table>

**情形6、Sr为红色**

<table> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdn.net/20131211023850953" alt=""></td> 
   <td>这时，将P节点做一次左旋操作，将Sr的颜色设置为黑色，P和S交换颜色，调整之后，各简单路径的黑色节点数目和删除节点之前一样。<br> <br> 此时调整结束。</td> 
  </tr> 
 </tbody> 
</table>

1.  int is\_black(rbnode \* node) \{
2.  if (node == NULL) return 1;
3.  if (node->color == COLOR\_BLACK) return 1;
4.  return 0;
5.  \}
6.  
7.  // check and adjust after deletion
8.  void rbt\_delete\_check(rbnode\* p, bool delLeft) \{
9.  rbnode \* n = delLeft ? p->left : p->right;
10. // case 1: n is red
11. if (NULL != n && n->color == COLOR\_RED) \{
12. n->color = COLOR\_BLACK;
13. return;
14. \}
15. // else the other subtree of p at least has one more node.
16. rbnode \* s = delLeft ? p->right : p->left;
17. rbnode \* sl = s->left;
18. rbnode \* sr = s->right;
19. 
20. // case 2 : S is red , p left rotate
21. if (s->color == COLOR\_RED) \{
22. if (delLeft) \{
23. rb\_left\_rotate(p);
24. \} else \{
25. rb\_right\_rotate(p);
26. \}
27. p = s;
28. s = delLeft ? sl : sr;
29. sl = s->left;
30. sr = s->right;
31. \}
32. // Other cases : S is black
33. // when SL and SR are black
34. if (is\_black(sl) && is\_black(sr)) \{
35. // case 3 : P is red, S SL and SR are black
36. if (!is\_black(p)) \{
37. p->color = COLOR\_BLACK;
38. s->color = COLOR\_RED;
39. \}
40. // case 4: P ,S, SL and SR are black
41. else \{
42. s->color = COLOR\_RED;
43. if (NULL == p->parent) \{
44. return;
45. \}
46. delLeft = (p == p->parent->left);
47. rbt\_delete\_check(p->parent, delLeft);
48. \}
49. return;
50. \}
51. // when SL and SR has red node
52. if (delLeft) \{
53. if (is\_black(sr)) \{ // case 5(a) : delLeft is true and SR is black
54. rb\_right\_rotate(s);
55. sr = s->right;
56. \}
57. rb\_left\_rotate(p); // case 6(a) : rotate the p node
58. sr->color = COLOR\_BLACK;
59. \} else \{
60. if (is\_black(sl)) \{ // case 5(b) : delLeft is false and SL is black
61. rb\_left\_rotate(s);
62. sl = s->left;
63. \}
64. rb\_right\_rotate(p); // case 6(b) : rotate the p node
65. sl->color = COLOR\_BLACK;
66. \}
67. \}
68. 
69. // delete a key from the RBT
70. int rbt\_delete(rbtree\* &tree, keyType key) \{
71. if (NULL == tree) \{
72. return 0;
73. \}
74. // find the node
75. rbnode \*curr, \*temp;
76. for (curr = tree;;) \{
77. if (key == curr->key) \{
78. break;
79. \}
80. curr = (key > curr->key) ? curr->right : curr->left;
81. if (NULL == curr) \{
82. return 0;
83. \}
84. \}
85. // if the node to delete has two children
86. if (NULL != curr->left && NULL != curr->right) \{
87. for (temp = curr->left; NULL != temp->right; temp = temp->right) \{
88. \}
89. curr->key = temp->key;
90. curr = temp;
91. \}
92. if (NULL == curr->parent) \{ // it is the tree root
93. tree = (NULL == curr->left) ? curr->right : curr->left;
94. if (tree != NULL) \{
95. tree->color = COLOR\_BLACK;
96. tree->parent = NULL;
97. \}
98. free(curr);
99. return 1;
100. \}
101. // delete the node
102. rbnode\* fa = curr->parent;
103. temp = (NULL == curr->left) ? curr->right : curr->left;
104. bool delLeft = (fa->left == curr);
105. if (NULL != temp) \{
106. temp->parent = fa;
107. \}
108. delLeft ? fa->left = temp : fa->right = temp;
109. if (curr->color != COLOR\_RED) \{ // adjust after deletion
110. rbt\_delete\_check(fa, delLeft);
111. \}
112. free(curr);
113. return 1;
114. \}

[B-tree]: http://baike.baidu.com/subview/363832/363832.htm
[B]: http://baike.baidu.com/subview/298408/298408.htm
[Link 1]: http://baike.baidu.com/view/143352.htm
[7e3e6709c93d70cf4021a04dfddcd100bba12b92.jpg]: /images/20220731/ad06dafe23a146c488131d22fea72f0b.png
[7e3e6709c93d70cf4021a04dfddcd100bba12b92.jpg 1]: http://baike.baidu.com/picture/2228473/2228473/0/7e3e6709c93d70cf4021a04dfddcd100bba12b92.html?fr=lemma&ct=single
[http_img851.ph.126.net_qN4ZWmgY8YXAk3rClFR-jw_2715670575304874531.png]: http://img851.ph.126.net/qN4ZWmgY8YXAk3rClFR-jw==/2715670575304874531.png
[Link 2]: http://baike.baidu.com/view/3028897.htm
[Link 3]: http://baike.baidu.com/view/2335663.htm
[Link 4]: http://baike.baidu.com/view/549553.htm
[Link 5]: http://baike.baidu.com/view/390935.htm
[Link 6]: http://baike.baidu.com/view/47398.htm
[Link 7]: http://baike.baidu.com/view/159417.htm
[M_3_B-]: http://d.hiphotos.baidu.com/baike/s%3D250/sign=22e58eb98a13632711edc536a18ea056/c8ea15ce36d3d539853a1da63a87e950352ab04b.jpg
[M_3_B-_M_3_B-]: /images/20220731/eb4a4dc69c5947eabb186125728415a7.png
[Link 8]: http://baike.baidu.com/view/610605.htm
[Link 9]: http://baike.baidu.com/view/1256077.htm
[B 1]: http://baike.baidu.com/view/298408.htm
[29_B-_ - _ -]: http://img851.ph.126.net/NPzxmBUhVQk0zwDDvjqxjg==/2715670575304874544.png
[29_B-_ - EdwardLewis -]: http://img.ph.126.net/3UTmc4_7TZUrcY4KD4zYgg==/3256102530589836924.png
[29_B-_ - _ - 1]: http://img161.ph.126.net/-3FWAp9kUZIQe8RveB3KpA==/1443685155550413546.png
[29_B-_ - _ - 2]: http://img161.ph.126.net/el1pVFdtgU-TlYVudHPk7Q==/1443685155550413550.png
[29_B-_ - _ - 3]: http://img161.ph.126.net/mK30SAlbWZJS6ZQJzOg08w==/1443685155550413560.png
[29_B-_ - _ - 4]: http://img842.ph.126.net/TBEBr7dmNsywOSQ0oivxmw==/872572427804609467.png
[29_B-_ - _ - 5]: http://img842.ph.126.net/yF6PSGyHlGudFo-t5-zAeQ==/872572427804609474.png
[29_B-_ - _ - 6]: http://img768.ph.126.net/lKatTbe-Pc58l7f6WXmZ1g==/1257630195944293555.png
[29_B-_ - _ - 7]: http://img39.ph.126.net/Kp_M2gy11F-K_7JhuYv1XA==/3133660915721480375.png
[29_B-_ - _ - 8]: http://img39.ph.126.net/0Zcj2-oM4HNZOTN1v2pKFA==/3133660915721480379.png
[29_B-_ - _ - 9]: http://img39.ph.126.net/U7rUDNgIgv57opuCFv7lSw==/3133660915721480383.png
[29_B-_ - _ - 10]: http://img764.ph.126.net/SPflL7dsm2oQ2i-FIwSpGw==/1253971021246979247.png
[29_B-_ - _ - 11]: http://img458.ph.126.net/SLUJT6zCt-H6X5w_W1COxQ==/2545659689372018333.png
[29_B-_ - _ - 12]: http://img58.ph.126.net/AYIVtWu3O7mFcZHhDZ4mSw==/1828461448713684495.png
[29_B-_ - _ - 13]: http://img158.ph.126.net/4bz48OaFfstAPpbIZCpGXg==/2176364519928063671.png
[29_B-_ - _ - 14]: http://img458.ph.126.net/mkus1sc13uCKwiD9i1b7mQ==/2553540988719968477.png
[B-]: http://baike.baidu.com/view/2228473.htm
[Link 10]: http://baike.baidu.com/view/262241.htm
[902397dda144ad3495c012dfd1a20cf431ad856f.jpg]: /images/20220731/e58945be19c347e0a46c4645cd258733.png
[902397dda144ad3495c012dfd1a20cf431ad856f.jpg 1]: http://baike.baidu.com/picture/1168762/1168762/0/902397dda144ad3495c012dfd1a20cf431ad856f.html?fr=lemma&ct=single
[Link 11]: http://baike.baidu.com/view/499747.htm
[Link 12]: http://baike.baidu.com/view/45901.htm
[B-tree 1]: http://baike.baidu.com/view/363832.htm
[Link 13]: http://baike.baidu.com/view/3314.htm
[Link 14]: http://baike.baidu.com/view/9900.htm
[Link 15]: http://baike.baidu.com/view/1654988.htm
[Link 16]: http://baike.baidu.com/view/544292.htm
[view plain]: http://blog.csdn.net/whucyl/article/details/17254801#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/95894
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/95894/fork
[20131207005222937]: /images/20220731/57cf0b40903e44969126633b2b3633b9.png
[20131207003053968]: /images/20220731/578559386310456aa2b0267ae001fd83.png
[20131207021556125]: /images/20220731/5cb64d8828cf48798443e733ff363ca6.png