AVL树的建立与删除

Jun 16, 2010

用到的树的节点如下所示:

struct node{
     int data;
     int bf;
     node *lchild;
     node *rchild;
};

其中data表示该节点存储数据,bf表示当前节点的高度,lchild指向当前节点的左儿子,rchild指向当前节点的右儿子。

对于二叉树的建立与节点的插入在本次实验中采用递归的方法,首先找到插入节点,然后递归的判断,如果节点左儿子与右儿子的高度差大于等于2,则对该节点进行平衡调整。

对于二叉树的删除操作,先递归的搜索要删除的节点A,用该节点的右儿子的最左儿子B代替该节点,以A的右儿子和B当前的数值作为线索继续遍历,只到找到B,删除B。然后递归的对B的祖先节点进行平衡调整,具体调整操作和二叉树的插入操作的平衡调整相同。

对二叉树的平衡调整过程,主要包含四种旋转操作:LL,LR,RR,RL。

LR由当前节点左儿子的一次RR旋转和当前节点的一次LL旋转构成。同理,RR由当前节点右儿子的一次LL旋转和当前节点的一次RR旋转构成。

例如输入0-19这20个数,建立的AVL树为:

7       root
Left    3       [parent:7]
Left    1       [parent:3]
Left    0       [parent:1]
Right   2       [parent:1]
Right   5       [parent:3]
Left    4       [parent:5]
Right   6       [parent:5]
Right   15      [parent:7]
Left    11      [parent:15]
Left    9       [parent:11]
Left    8       [parent:9]
Right   10      [parent:9]
Right   13      [parent:11]
Left    12      [parent:13]
Right   14      [parent:13]
Right   17      [parent:15]
Left    16      [parent:17]
Right   18      [parent:17]
Right   19      [parent:18]

删除其中的3, 7, 10后的AVL树为:

8       root
Left    4       [parent:8]
Left    1       [parent:4]
Left    0       [parent:1]
Right   2       [parent:1]
Right   5       [parent:4]
Right   6       [parent:5]
Right   15      [parent:8]
Left    11      [parent:15]
Left    9       [parent:11]
Right   13      [parent:11]
Left    12      [parent:13]
Right   14      [parent:13]
Right   17      [parent:15]
Left    16      [parent:17]
Right   18      [parent:17]
Right   19      [parent:18]

鉴于更多节点的测试同二十个节点测试没有本质上区别,可以判断程序运行良好,符合实验要求。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

char chos;
int input;
bool unbalanced = false;
struct node{
    int data;
    int bf;
    node *lchild;
    node *rchild;
};
typedef struct node *BST;
BST R = NULL;

void Chose(){
    printf("i) Insert a point\n"
           "d) Delete a point\n"
           "e) exit\n"
           "Input your choose:");
    scanf(" %c", &chos);
}

int Height(BST T){     /*返回当前节点的高度*/
    if(T == NULL)
        return -1;
    else
        return T->bf;
}

int Max(int A, int B){
    return ((A > B) ? A:B);
}

BST SingleRotateWithRight(BST K2){          /*RR型旋转*/
    BST K1;
    K1 = K2->rchild;
    K2->rchild = K1->lchild;
    K1->lchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST SingleRotateWithLeft(BST K2){           /*LL型旋转*/
    BST K1;
    K1 = K2->lchild;
    K2->lchild = K1->rchild;
    K1->rchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST DoubleRotateWithLeft(BST K3){           /*LR = RR(K3->lchild) + LL(K3)*/
    K3->lchild = SingleRotateWithRight(K3->lchild);
    return SingleRotateWithLeft(K3);
}

BST DoubleRotateWithRight(BST K3){          /*LL = LL(K3->lchild) + RR(K3)*/
    K3->rchild = SingleRotateWithLeft(K3->rchild);
    return SingleRotateWithRight(K3);
}

void OUT(BST T){                /*树的输出递归函数*/
    if(T->lchild){
        printf("Left\t%d\t[parent:%d]\n", T->lchild->data, T->data);
        OUT(T->lchild);
    }
    if(T->rchild){
        printf("Right\t%d\t[parent:%d]\n", T->rchild->data, T->data);
        OUT(T->rchild);
    }
}

BST Rotate(BST T){              /*对于单个节点进行的AVL调整*/
    if(Height(T->lchild) - Height(T->rchild) == 2){
        if(Height(T->lchild->lchild) >= Height(T->lchild->rchild)){
            T = SingleRotateWithLeft(T);
        }
        else{
            T = DoubleRotateWithLeft(T);
        }
    }
    if(Height(T->rchild) - Height(T->lchild) ==2){
        if(Height(T->rchild->rchild) >= Height(T->rchild->lchild)){
            T = SingleRotateWithRight(T);
        }
        else{
            T = DoubleRotateWithRight(T);
        }
    }
    return T;
}

BST AVLInsert(BST T){           /*AVL数的插入操作*/
    if(T == NULL){
        T = (BST)malloc(sizeof(struct node));
        T->data = input;
        T->lchild = T->rchild = NULL;
        T->bf = 0;
    }
    else if(input < T->data){
        T->lchild = AVLInsert(T->lchild);
        if(Height(T->lchild) - Height(T->rchild) == 2){
            if(input < T->lchild->data){
                T = SingleRotateWithLeft(T);            /*LL旋转*/
            }
            else{
                T = DoubleRotateWithLeft(T);            /*LR旋转*/
            }
        }
    }
    else if(input > T->data){
        T->rchild = AVLInsert(T->rchild);
        if(Height(T->rchild) - Height(T->lchild) == 2){
            if(input > T->rchild->data){
                T = SingleRotateWithRight(T);           /*RR旋转*/
            }
            else{
                T = DoubleRotateWithRight(T);           /*RL旋转*/
            }
        }
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    return T;
}

void Output(BST T){
    if(T == NULL){
        printf("None\n");
    }
    else{
        printf("%d\troot\n", T->data);
        OUT(T);
    }
}

void Insert(){
    printf("\nInput the point your want to Insert: ");
    scanf("%d", &input);
    R = AVLInsert(R);
    Output(R);
}

BST AVLDelete(BST T, int key){
    if(T == NULL)
        return NULL;
    if(key == T->data){
        if(T->rchild == NULL){          /*如果T得右儿子为空则直接删除*/
            BST temp = T;
            T = T->lchild;
            free(temp);
        }
        else{                           /*否则找到T->rchild的最左儿子代替T*/
            BST temp = T->rchild;
            while(temp->lchild != NULL){
                temp = temp->lchild;
            }
            T->data = temp->data;
            T->rchild = AVLDelete(T->rchild, temp->data);      /*对于替代后的T及其各个子节点进行一些列调整,正到再次递归到T->rchild的最左儿子,删除它*/
            T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
        }
        return T;
    }
    else if(key < T->data){
        T->lchild = AVLDelete(T->lchild, key);
    }
    else{
        T->rchild = AVLDelete(T->rchild, key);
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    if(T->lchild != NULL){
        T->lchild = Rotate(T->lchild);
    }
    if(T->rchild != NULL){
        T->rchild = Rotate(T->rchild);
    }
    T = Rotate(T);
    return T;
}

void Delete(){
    printf("\nInput the point you want to Delete: ");
    scanf("%d", &input);
    R = AVLDelete(R, input);
    Output(R);
}

int main(){
    while(1){
        Chose();
        switch(chos){
            case 'i':
                Insert();
                break;
            case 'd':
                Delete();
                break;
            case 'e':
                exit(0);
        }
    }
    return 0;
}
Posted by admin avl树 , 删除 , 建立 , 源代码

Comments

  1. 数据结构之AVL树 | 董的博客 Reply August 19, 2011 @ 11:07 AM

    [...] (4)http://www.asiteof.me/2010/06/avl/ [...]

    Avatar

Get In Touch With Us ...