数据结构干货笔记：平衡二叉树（AVL）的调整和构建C代码实现

/*
    平衡二叉树：左单旋(LL)、左右双旋(LR)、右单旋转(RR)、右左双旋(RL)旋转 
               以插入方式构建平衡二叉树
*/

typedef struct AVLNode *AVLTree;
struct AVLNode{
    int data;
    AVLTree left;
    AVLTree right;
    int height;
};

int max(int a, int b){
    return a > b ? a : b;
}
int getHeight(AVLTree T){//求树的高度高 树的高度= 1 + 左右子树高度的最大值
    if(T == NULL)//孔数
        return  0;
    else
        return max(getHeight(T->left),getHeight(T->right)) + 1;
}

//1.LL旋转
AVLTree singleLeftRotation(AVLTree A){
    AVLTree B = A->left;
    A->left = B->right;
    B->right = A;
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->left), getHeight(B->right)) + 1;
    return B;
}
//2.RR旋转
AVLTree singleRightRotation(AVLTree A){
    AVLTree B = A->right;
    A->right = B->left;
    B->left = A;
    A->height = max(getHeight(A->left), getHeight(A->right)) + 1;
    B->height = max(getHeight(B->left), getHeight(B->right)) + 1;
    return B;
}

//3.LR旋转
AVLTree doubleLeftRightRotation(AVLTree A){
    A->left = singleRightRotation(A->left);
    return singleLeftRotation(A);
}
//4.RL旋转
AVLTree doubleRightLeftRotaion(AVLTree A){
    A->right = singleLeftRotation(A->right);
    return singleRightRotation(A);
}
//5.在平衡二叉树上插入 并调整使其继续平衡  可以用来构建一棵AVL树
AVLTree insert(AVLTree T, int e){
    if(T == NULL){
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->data = e;
        T->left = T->right = NULL;
        T->height = 0;
    }
    else if(e < T->data){//插入到左子树
        T->left = insert(T->left, e);//将e插入到左子树 并指向新的左子树根结点
        if(getHeight(t->left) - getHeight(t->right) == 2){//如果插入造成不平衡
            if(e < T->left->data)//如果插入到左子树的左子树 则LL旋转
                T = singleLeftRotation(T);
            else//如果插入到左子树的右子树 则LR旋转
                T = doubleLeftRightRotaion(T);
        }
    }
    else if(e > T->data){//插入到右子树
        T->right = insert(T->right, e);
        if(getHeight(t->left) - getHeight(t->right) == -2){
            if(e > T->right->data)
                T = singleRightRotation(T);
            else
                T = doubleRightLeftRotaion(T);
        }
    }
    T->heght = max(getHeight(T->left), getHeight(T->right)) + 1;
    return T;
}