摘要:本节包含二叉查找树,AVL树,伸展树以及B树

标签: Data-Structures


注意,笔记不是讲各种概念的,只是记录一下个人学习过程中遇到的问题和实现代码。需要知道基本概念,理解各种树的原理。

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;
}

实现Delete时,有点不明白,在删除只有一个子节点的 T 节点时,为什么

T = T->Right;

后来仔细想了一下,纸上画了一下,还是因为指针的本质导致的。

指针本质就是地址,当删除子节点 T 时,父节点 parent 节点的某个指针域需要赋值,而这个值则是孙节点的地址.代码中 T 指针指向 儿子节点,此时 T 变量被赋值为儿子节点的地址,return T意味着返回儿子节点的地址。函数返回时,父节点parent的子树指针域被赋值为孙节点的地址,变成了儿子节点。

感想:可以从二叉查找树的实现代码中看到很多递归调用,极大的简化了实现。不小心指针和递归绕到。

2 AVL树

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

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

当插入节点后,需要更新插入节点处到根节点的路径上的所有平衡信息。如果破化了AVL树的平衡性,需要进行旋转来保持平衡条件。

当在某个节点 T 的某个子树中插入节点后,高度不平衡。

不平衡会出现4种情况:

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

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

单旋转

双旋转

基本例程和二叉查找树一样,不过多了几个用于AVL树旋转的例程.

双旋转可以通过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;
}

在实现时,依次插入节点 1 2 3 4 5 6 7 16 17,节点17插入后,需要对7、16、17进行右单旋转调整保持平衡,但由于对递归和指针不熟悉,未写某个关键代码如下

 //错误代码
SingleRotationWithRight(T);

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

直到单步调试时,发现单旋转没有错误,但是函数返回后,T节点依然是7,而且丢失了右子树,才反应过来调整后的树的根没有被指向。

遍历:

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

3 伸展树

伸展树建立在二叉查找树的基础上,不过为了避免每次操作最坏时间 O(N)。

通过将一个被访问过的节点旋转到根上,那么对于原先处于深度比较深的其它节点在被访问时,会降低访问时间。局部性原理(刚被访问的内容下次可能仍会被访问)。

将要查找的节点自底向上旋转,直至该节点成为树根。

保证了在任意 M 次访问时,最多花费 O(MlogN) 的运行时间,伸展树的每次操作的摊还代价为 O(logN)。

很遗憾,伸展树的思路实现还是很好理解的,但是在实现过程中,遇到了一个很严重的问题。

比如依次插入7 6 5 4 3 2 1,当查找 1 时,只能将3 2 1进行一字型旋转后,就不能进行下去了。

错误代码

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;
}

写得很啰嗦,判断很多种情况。其中几个旋转例程是针对4种情况的,Zig-zag和Zig-zig,以及对称情况

//旋转例程,分为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的子树节点。再根据子树关键字数目,确定是否需要从左右兄弟节点中移动一个节点替代父节点中关键字,把父节点中被替代的关键字放在被删除的位置上

在实现的过程中,一个关键问题就是插入要保证不会满,否则分类;删除要保证节点的关键字数目不能低于M-1,否则破坏B树性质。

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

此部分参考博客以及算法导论18章

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

创建B树

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

在T节点中查找关键字key的索引

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;
}

查找节点T是否包含关键字key

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;
}

总结: B树很不好理解,花了好几天,从概念上理解,在细节上注意,最好每一步都在图上画,尤其是删除部分,许多情况,结构复杂易出错。此外,最让我头疼的是,那个移动关键字很是小心,最后发现,完全可以提取出来作为一个函数,不用每次都重新实现。