## 摘要：本节包含二叉查找树，AVL树，伸展树以及B树

1 二叉查找树

``````struct TreeNode{
int Elem;
struct Treenode *Left,*Right;
};

SearchTree MakeEmpty(SearchTree T){
if (T != NULL){
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}

Position Find(int X, SearchTree T){
if (T == NULL){
return NULL;
}
if (X < T->Elem)
return Find(X,T->Left);
else if(X > T->Elem)
return Find(X,T->Right);
else
return T;

}

//递归实现查找最小值
Position FindMin(SearchTree T){
if (T == NULL)
return NULL;
else if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}

//非递归查找最大值
Position FindMax(SearchTree T){
if(T != NULL){
while(T->Right != NULL)
T  = T->Right;
}
return T;
}

SearchTree Insert(int X, SearchTree T){
if (T == NULL){
T = malloc(sizeof(struct TreeNode));
T->Elem = X;
T->Left = T->Right = NULL;
}
else if(X < T->Elem)
T->Left = Insert(X,T->Left);
else if (X>T->Elem)
T->Right = Insert(X,T->Right);
return T;
}

SearchTree Delete(int X,SearchTree T){
Position P;
if (T==NULL)
return NULL;
else if (X < T->Elem){
T->Left = Delete(X,T->Left);
}else if(X > T->Elem)
T->Right = Delete(X, T->Right);
else if (T->Left && T->Right){
P = FindMin(T->Right);
T->Elem = P->Elem;
Delete(P->Elem,T->Right);
}else{
P = T;
if (T->Left== NULL)
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free(P);
}
return T;
}
``````

``````T = T->Right;
``````

2 AVL树

AVL树是带有平衡条件的二叉查找树。在插入和删除节点时，必须保持这个平衡条件-每个节点的左子树和右子树的高度最多相差为1。需要给每个节点加个附加域-高度域

``````sttuct AvlNode{
int Elem;
AvlTree *Left,*Right;
int Height;
}
``````

1. T节点的左儿子的左子树插入节点
2. T节点的左儿子的右子树插入节点
3. T节点的右儿子的左子树插入节点
4. T节点的右子树的右子树插入节点

4种情况是2种镜像情况的对称，这里只考虑左左和左右2种情况，可以分为单旋转和双旋转。

``````int Height(Position P){
if (P == NULL)
return -1;
else
return P->Height;
}

int Max(int a,int b){
return a>b?a:b;
}
//左旋转
Position SingleRotationWithLeft(Position K2){//情况 1
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;

K2->Height = Max(Height(K2->Left),Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left),K2->Height) + 1;
return K1;
}

//左双旋转
Position DoubleRotationWithLeft(Position K3){//情况 2
//    K3->Left = SingleRotationWithRight(K3->Left);
//    return SingleRotationWithLeft(K3);
Position K1, K2;
K1 = K3->Left;
K2 = K1->Right;
K1->Right = K2->Left;
K3->Left = K2->Right;
K2->Left = K1;
K2->Right = K3;
K1->Height = Max( Height(K1->Left), Height(K1->Right) ) + 1;
K3->Height = Max( Height(K3->Left), Height(K3->Right) ) + 1;
K2->Height = Max( K1->Height, K3->Height ) + 1;
return K3;
}

Position DoubleRotationWithRight(Position K3){//情况 3
K3->Right = SingleRotationWithLeft(K3->Right);
return SingleRotationWithRight(K3);
}

Position SingleRotationWithRight(Position K2){//情况 4
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K2->Height = Max(Height(K2->Left),Height(K2->Right))+1;
K1->Height = Max(K2->Height,Height(K1->Right))+1;
return K1;
}
``````

``````AvlTree Insert(int X, AvlTree T){
if (T == NULL){
T = malloc(sizeof(struct AvlNode));
T->Elem = X;
T->Left = T->Right = NULL;
T->Height = 0;
}else if (X < T->Elem){
T->Left = Insert(X, T->Left);
if (Height(T->Left) - Height(T->Right) == 2)
if (X < T->Left->Elem)
T = SingleRotationWithLeft(T);
else
T = DoubleRotationWithLeft(T);
}else if ( X > T->Elem){
T ->Right = Insert(X, T->Right);
if (Height(T->Right) - Height(T->Left) == 2)
if (X > T->Right->Elem)
T = SingleRotationWithRight(T);
else
T = DoubleRotationWithRight(T);
}
T->Height = Max(Height(T->Left),Height(T->Right))+1;
return T;
}

AvlTree Delete(int X, AvlTree T){
Position P;
if (T == NULL)
return NULL;
else if( X < T->Elem){
T->Left = Delete(X, T->Left);
if (Height(T->Right) - Height(T->Left) == 2)
T = SingleRotationWithRight(T);
}
else if (X > T->Elem){
T->Right = Delete(X, T->Right);
if (Height(T->Left) - Height(T->Right) == 2)
T = SingleRotationWithLeft(T);
}else if(T->Left && T->Right){
P = FindMin(T->Right);
T->Elem = P->Elem;
T->Right = Delete(P->Elem,T->Right);
}else{
P = T;
if (T->Left == NULL)
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free(P);
}
return T;
}
``````

`````` //错误代码
SingleRotationWithRight(T);

//正确代码
T = SingleRotationWithRight(T);
``````

``````void PrintTree(AvlTree T){
if (T != NULL){
PrintTree(T->Left);
printf(" %d ",T->Elem);
PrintTree(T->Right);
}
}
``````

3 伸展树

``````Position Find(int X, SplayTree T){
if (T == NULL || T->Elem == X)
return T;
else if (X < T -> Elem ){
if( T->Left->Elem == X){//根的左子节点就是所要查找的节点，则和根旋转，单旋转
T->Left = T->Left->Right;
T->Left->Right = T;
return T->Left;
}else if (X < T->Left->Elem){
if( X == T->Left->Left->Elem)
T = OneRotationWithLeft(T);
else
T->Left = Find(X,T->Left);
}else if(X > T->Left->Elem){
if( X == T->Left->Right->Elem){
T = DoubleRotationWithLeft(T);
}else
T->Left = Find(X,T->Left);
}
}else if (X > T->Elem){
if (T->Right->Elem == X){
T->Right = T->Right->Left;
T->Right->Left = T;
return T->Right;
}else if(X < T->Right->Elem){
if (X == T->Right->Left->Elem){
T = DoubleRotationWithRight(T);
}else{
T->Right = Find(X,T->Right);
}
}else if (X > T->Right->Elem){
if ( X == T->Right->Right->Elem){
T = OneRotationWithRight(T);
}else{
T->Right = Find(X,T->Right);
}
}
}
return T;
}
``````

``````//旋转例程，分为Zig-zag和Zig-zig，即之字型旋转和一字型旋转
//左右双旋转
Position DoubleRotationWithLeft(Position G){
Position P,X;
P = G->Left;
X = P->Right;

P->Right = X->Left;
X->Left = P;
G->Left = X->Right;
X->Right = G;

return X;
}
//右左双旋转
Position DoubleRotationWithRight(Position G){
Position P,X;
P = G->Right;
X = P->Left;

G->Right = X->Left;
X->Left = G;
P->Left = X->Right;
X->Right = P;

return X;
}
//左一字型
Position OneRotationWithLeft(Position G){
Position P,X;
P = G->Left;
X = P->Left;

G->Left = P->Right;
P->Left = X->Right;
P->Right = G;
X->Right = P;

return X;
}
//右一字型
Position OneRotationWithRight(Position G){
Position P,X;
P = G->Right;
X = P->Right;
G->Right = P->Left;
P->Left = G;
P->Right = X->Left;
X->Left = P;
}
``````

``````struct SplayNode{
Tree parent; //该结点的父节点，方便操作
ElementType val; //结点值
Tree lchild;
Tree rchild;
SplayNode(int val=0) //默认构造函数
{
parent=NULL;
lchild=rchild=NULL;
this->val=val;
}
};
``````

``````void SplayTree(Tree &root,Tree node)
{
while (root->lchild!=node && root->rchild!=node && root!=node) //当前结点不是根，或者不是其根的左右孩子，则根据情况进行旋转操作
up(root, node);
if (root->lchild==node) //当前结点为根的左孩子，只需进行一次单右旋
root=right_single_rotate(root, node);
else if(root->rchild==node) //当前结点为根的右孩子，只需进行一次单左旋
root=left_single_rotate(root, node);
}

//根据情况，选择不同的旋转方式
void up(Tree &root,Tree node)
{
Tree parent,grandparent;
int i,j;
parent=node->parent;
grandparent=parent->parent;
i=grandparent->lchild==parent ? -1:1;
j=parent->lchild==node ?-1:1;
if (i==-1 && j==-1) //AVL树中的LL型
right_double_rotate(root, node);
else if(i==-1 && j==1) //AVL树中的LR型
LR_rotate(root, node);
else if(i==1 && j==-1) //AVL树中的RL型
RL_rotate(root, node);
else                    //AVL树中的RR型
left_double_rotate(root, node);
}
``````

**总结：

``````        1 遗憾自己没有写出伸展树
2 小Tip：当觉得自己对二叉查找树和AVL树有了一定程度了解后，建议尝试实现伸展树**
``````

4 B树

B树基本操作，查找，插入和删除

• 查找类似于二叉查找树，不过不是二路，而是多路；一趟查找，要么找到关键字的位置，要么能确定关键字所在的子树的指针
• 插入关键字：按照查找的思路，从根节点开始查找，遇到节点的关键字已满2M-1，需要分裂出新节点，每个节点包含M-1个节点，将中间节点移到父节点，在2个节点指针之间。为何是M-1,因为B树的性质保证B树除根节点外的内部节点的关键字数必须介于2*M-1和M-1之间，M称为B树的阶
• 删除关键字：分为几种情况 1 ： 当前T节点为叶子节点，关键字key在T节点中，直接删除 2 ： 当前T节点为内部节点，关键字key在T节点中，根据子节点关键字的数目和M-1比较，决定将关键字key左右子树中的一个关键字替换key，或者需要合并节点 3 ： 关键字不在当前内部节点T中，需要确定可能包含关键字key的子树节点。再根据子树关键字数目，确定是否需要从左右兄弟节点中移动一个节点替代父节点中关键字，把父节点中被替代的关键字放在被删除的位置上

B树以及相关变体，关键在插入关键字判断是否需要分裂节点，向上回溯直到满足B树性质，删除关键字的节点是否需要合并。

``````struct BNodeRecord{
int num;//关键字个数
int leaf;// 1 表示叶子 0 表示内部节点
int key[2*M - 1];
BNode c[2*M];
};
``````

``````BTree CreateBTree(){
BTree T;
T = malloc(sizeof(struct BNodeRecord));
T->num = 0;
T->leaf = 1;
return T;
}
``````

``````BNode BTreeSearch(BTree T, int key, int *index){
int i = 0;
while(i < T->num && T->key[i] < key)
i++;
if (i < T->num && T->key[i] == key){
*index = i;
return T;
}
else if ( T->leaf == 1){
printf("no key in BTree\n");
return NULL;
}
return BTreeSearch(T->c[i], key, index);
}
``````

``````BTree BTreeSplitChild(BTree T, int index){
BNode Y,Z;//Y表示满节点，Z表示新节点
Y = T->c[index];
Z = malloc(sizeof(struct BNodeRecord));
Z-> num = M - 1;
Y-> num = M - 1;
Z->leaf = Y->leaf;
//关键字转移
for (int i = M; i < 2*M-1; ++i) {
Z->key[i-M] = Y->key[i];
}
//如果是内部节点则进行指针转移
if (!Y->leaf){
for (int j = M; j < 2*M; ++j) {
Z->c[j-M] = Y->c[j];
}
}

for(int k = T->num-1; k>= index; k--){
T->key[k+1] = T->key[k];
}
for (int l = T->num; l >= index+1; ++l) {
T->c[l+1] = T->c[l];
}
T->key[index] = Y->key[M-1];
T->c[index+1] = Z;
T->num++;
return T;
}
``````

``````BTree BTreeInsert(BTree T, int key){
if(T->num == 2*M - 1){
BNode S;
S = malloc(sizeof(struct BNodeRecord));
S->num = 0;
S->leaf = 0;
S->c[0] = T;
T = BTreeSplitChild(S,0);
BTreeInsertNotFull(T,key);
}else
BTreeInsertNotFull(T,key);
}
``````

``````BTree BTreeDelete(BTree T, int key){
int index, i, flag;
//在T节点中查询关键字是否存在，在的话，返回其下标index，
index = BTreeSearchIndex(T, key, &flag);
//falg标志T->key[index] == key，即节点T中有关键字key

/* 第一种情况：关键字在叶子节点中，直接删除它 */
if (T->leaf == 1 && flag == 0){
//flag=0表示T节点中有关键字，且T是叶子节点
//把index后面的所有关键字向前移动一位，关键字数目减1
memmove(&T->key[index], &T->key[index+1], sizeof(int) * (T->num - index -1));
T->num--;
return T;
}else if (T->leaf && flag != 0){
//关键字不在T节点中
return T;
}

/* 第二种情况：关键字在内部节点 T 中，根据3种情况- T 的子节点的关键字数目来删除和移动*/

if (flag != 0){
// Y :T->key[index]的前一个指针所指向的子节点，Z :T->key[index]的后一个指针所指向的子节点
//                T->key[index](关键字)
//    T->c[index](T中指针）       T->c[index+1](T中指针）
//      |                              |
//      Y                              Z
BNode Y, Z;
Y = T->c[index];
Z = T->c[index + 1];

// a : Y中至少有M个关键字，在Y子树中找到key的前驱关键字key',递归删除key',将key'移到key中；
if (Y->num >= M){
int pre_key = Y->key[Y->num - 1];
//Y子树中删除pre_key
T->c[index] = BTreeDelete(Y, pre_key);
T->key[index] = pre_key;
return T;
}

// b : Y中关键字数目低于M个，对称地将 Z子树 中的第一个节点移动到T->key[index]中
if (Z->num >= M){
int next_key = Z->key[0];
//Z子树中删除next_key
T->c[index+1] = BTreeDelete(Z,next_key);
T->key[index] = next_key;
return T;
}

// c :  Y和Z每一个关键字数目都是M - 1,则合并Y、Z以及关键字key，在Y中递归删除关键字Key
if( (Y->num == M-1) && (Z->num == M-1)){
//将关键字key放在Y和Z关键字之间
Y->key[Y->num++] = key;
//关键字复制
memmove(&Y->key[Y->num], &Z->key[0], sizeof(int) * Z->num);
//指针复制
memmove(&Y->c[Y->num], &Z->key[0], sizeof(struct BNodeRecord) * (Z->num + 1));
Y->num += Z->num;

//判断T节点删除一个关键字后是否为空，是则Y子节点作为当前的返回节点
if (T->num > 1){
memmove(&T->key[index], &T->key[index+1], sizeof(int) * (T->num - index - 1));
memmove(&T->c[index+1], &T->c[index+2], sizeof(struct BNodeRecord)*(T->num - index - 1));
T->num--;
}else{//为空，释放节点
free(T);
T = Y;
}
free(Z);
BTreeDelete(Y, key);
return T;
}
}

// 第三种情况 : 关键字key不在内部节点T中，如果key关键字在T的子节点T->c[index]中，根据子节点的关键字数目是否低于M，是则需要父节点中一个关键字移动到兄弟节点子节点T->c[index]中，再把兄弟节点中一个关键字移动到父节点，
BNode child;//可能含有关键字的子节点
if ((child = T->c[index]) && child->num == M-1){

// 1:child子节点中含有M-1个关键字，相邻左或者右兄弟节点中含有至少M个节点，先将父节点中移一个关键字到child节点中，再将兄弟节点中一个关键字移到父节点中

// 先假设左兄弟节点至少有M个节点
BNode sibling;
if ( (index > 0) && (sibling = T->c[index-1]) && sibling->num >= M){
//child子节点关键字和指针向后移动一位，父节点关键字放入child关键字下表0的位置
memmove(&child->key[1],&child->key[0], sizeof(int) * child->num);
memmove(&child->c[1],&child->c[0], sizeof(struct BNodeRecord) * (child->num + 1));
child->key[0] = T->key[index-1];
T->key[index-1] = sibling->key[sibling->num-1];
child->c[0] = sibling->c[sibling->num];

child->num++;
sibling->num--;
}else
//右兄弟节点至少有M个节点
if((index<T->num) && (sibling = T->c[index+1]) && (sibling->num >= M)){
child->key[child->num++] = T->key[index];
T->key[index] = sibling->key[0];
child->c[child->num] = sibling->c[0];
sibling->num--;
memmove(&sibling->key[0],&sibling->key[1], sizeof(int) *(sibling->num));
memmove(&sibling->c[0],&sibling->c[1], sizeof(struct BNodeRecord) * sibling->num+1);

}

// 2 ：左右兄弟节点关键字数目都是M-1,合并其中一个兄弟节点和child节点

//合并child节点和右兄弟节点
else if ((index<T->num) && (sibling = T->c[index+1]) && (sibling->num == M-1)){
child->key[child->num++] = T->key[index];
memmove(&child->key[child->num],&sibling->key[0], sizeof(int) * sibling->num);
memmove(&child->c[child->num], &sibling->c[0], sizeof(struct BNodeRecord) * (sibling->num + 1));
child->num +=sibling->num;

if (T->num > 1){
memmove(&T->key[index],&T->key[index+1], sizeof(int) * (T->num - index - 1));
memmove(&T->c[index+1],&T->c[index+2], sizeof(struct BNodeRecord) * (T->num-index -1));
T->num--;
}else{
free(T);
T= child;
}
free(sibling);
}else if((index>0) && (sibling = T->c[index-1]) && (sibling->num == M-1)){
sibling->key[sibling->num++] = T->key[index - 1];
memmove(&sibling->key[sibling->num], &child->key[0], sizeof(int) * child->num);
memmove(&sibling->c[sibling->num], &child->c[0], sizeof(struct BNodeRecord) * (child->num + 1));
sibling->num += child->num;

if (T->num - 1 > 0)
{
memmove(&T->key[index - 1], &T->key[index], sizeof(int) * (T->num - index));
memmove(&T->c[index], &T->c[index + 1], sizeof(struct BNodeRecord) * (T->num - index));
T->num--;
}
else
{
free(T);
T = sibling;
}

free(child);

child = sibling;
}

}

BTreeDelete(child,key);
return T;
}
``````

``````BTree BTreeInsertNotFull(BTree T, int key){
int i = T->num - 1;
if (T->leaf){
while(i>=0 && T->key[i]>key){
T->key[i+1] = T->key[i];
i--;
}
T->key[i+1] = key;
T->num++;
}else{
while(i>=0 && T->key[i]>key)
i--;
i++;
if (T->c[i]->num == 2*M-1){
BTreeSplitChild(T,i);
if (key > T->key[i])
i++;
}
BTreeInsertNotFull(T->c[i],key);
}
return T;
}
``````

``````int BTreeSearchIndex(BTree T, int key, int *flag){
int i;
for (int i = 0; i < T->num && (*flag = T->key[i] - key) < 0; ++i) {
;
}
return i;
}
``````