PAT A1066 Root of AVL Tree

题目链接

解题思路

这个题目的意思其实就是按照给定序列构建一棵AVL树，按照算法笔记上给出的思路。在插入的时候，如果插入的是左边，先更新root的高度，然后要看平衡因子是否等于2，如果等于，说明该树不平衡，就进一步判断是LL型还是LR型，因为插入的是左边的子树，所以只有这两种可能。同样的道理，如果插入的是右边，就要看平衡因子是否等于-2，如果等于，说明该树不平衡，进一步判断是RR型还是RL型，然后分别进行左旋和右旋操作。

在编写旋转代码时，可以画一下树来理解，注意先将连接在B上的另一个节点移动到root节点，然后在把root节点移动到B(temp)节点，然后先更新root的高度，再更新temp的高度，因为temp的高度会根据root来求解，最后将root节点指向temp即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=30;
int n,nums[maxn];
struct Node{
    int v,h;
    Node *left,*right;
    Node(int v=0,int h=1,Node* l=NULL,Node* r=NULL):v(v),h(h),left(l),right(r){}
};
Node* root=NULL;
int getHeight(Node* root){//获取当前节点的高度
    if (root==NULL) return 0;
    return root->h;
}
void updateHeight(Node* &root){//更新树的高度等于左右子树最高的加一
    root->h=max(getHeight(root->left),getHeight(root->right))+1;
}
int getBF(Node* root){//获取平衡因子等于左子树高度减右子树高度
    return getHeight(root->left)-getHeight(root->right);
}
void R(Node* &root){
    Node* temp=root->left;
    root->left=temp->right;
    temp->right=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}
void L(Node* &root){
    Node* temp=root->right;
    root->right=temp->left;
    temp->left=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}


void insert(Node* &root,int x){
    if(root==NULL){
        root=new Node(x);
        return;
    }else if(root->v>x){//往左子树插入
        insert(root->left,x);
        updateHeight(root);//插完后更新树的高度
        if(getBF(root)==2){//往左插不平衡时平衡因子应该为2
            if(getBF(root->left)==1){//LL型--只需进行一次右旋即可平衡
                R(root);
            }else if(getBF(root->left)==-1){//LR型--需要先进行一次左旋变成LL型，再进行一次右旋
                L(root->left);//对左子树进行一次左旋
                R(root);
            }
        }
    } else{
        insert(root->right,x);
        updateHeight(root);//插完后更新树的高度
        if(getBF(root)==-2){//往右插不平衡时平衡因子为-2
            if(getBF(root->right)==-1){//RR型--只需要进行一次左旋即可
                L(root);
            } else if(getBF(root->right)==1){//RL型-需要先进行一次右旋变成RR型，再进行一次左旋
                R(root->right);//对右子树进行一次右旋
                L(root);
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    int x;
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        insert(root,x);
    }
    printf("%d",root->v);
    return 0;
}