2021-04-04 PAT A1066

在学数据结构的时候就特别怕AVL树，没想到有一天我自己能写出一个，很开心啊

#include<cstdio>
#include<algorithm>
using namespace std;

struct node {
    int weight, height;
    node* lchild, * rchild;
    node(int a) { height = 1, weight = a; lchild = rchild = NULL; }
};
int getHeight(node* root) { if (root == NULL)return 0; return root->height; }

void updateHeight(node*& root) {
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void Lrotate(node*& root) {
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updateHeight(root), updateHeight(temp);
    root = temp;
}

void Rrotate(node* &root) {
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root), updateHeight(temp);
    root = temp;
}


int getBalanceFactor(node* &root) {
    return getHeight(root->lchild) - getHeight(root->rchild);
}

void insert(node*& root, int v) {
    if (root == NULL) {
        root = new node(v);
        return;
    }
    if (v < root->weight) {
        insert(root->lchild, v);
        updateHeight(root);
        int Factor = getBalanceFactor(root);
        if (getBalanceFactor(root) == 2) {
            if (getBalanceFactor(root->lchild) == 1) Rrotate(root);
            else {
                Lrotate(root->lchild);
                Rrotate(root);
            }
        }
    }
    else {
        insert(root->rchild, v);
        updateHeight(root);
        if (getBalanceFactor(root) == -2) {
            if (getBalanceFactor(root->rchild) == -1) Lrotate(root);
            else {
                Rrotate(root->rchild);
                Lrotate(root);
            }
        }
    }
}

node* Create(int n) {
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        int temp; scanf("%d", &temp);
        insert(root, temp);
    }
    return root;
}
int main() {
    int n; scanf("%d", &n);
    node* root = Create(n);
    printf("%d", root->weight);
}