[PAT解题报告] Root of AVL Tree

#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

struct node {
int val, height;
node *left, *right;
};

node all[22];
int total;

int height(node *a) {
    return a?a->height:(-1);
}

node *LL(node *k2) {
node *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), height(k1->right)) + 1;
    return k1;
}


node *RR(node *k1) {
node *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(height(k1->left), height(k1->right)) + 1;
    k2->height = max(height(k2->left), height(k2->right)) + 1;
    return k2;
}

node *LR(node *k3) {
    k3->left = RR(k3->left);
    return LL(k3);
}

node *RL(node *k1) {
    k1->right = LL(k1->right);
    return RR(k1);
}

node *insert(node *root,int x) {
    if (root == 0) {
        root = &all[total++];
        root->left = root->right = 0;
        root->val = x;
        root->height = 0;
    }
    else if (x < root->val) {
        root->left = insert(root->left, x);
        if (height(root->left) - height(root->right) == 2) {
            root = (x < root->left->val)?LL(root):LR(root);
        }
    }
    else {
        root->right = insert(root->right, x);
        if (height(root->right) - height(root->left) == 2) {
            root = (x > root->right->val)?RR(root):RL(root);
        }
    }
    root->height = max(height(root->left), height(root->right)) + 1;
    return root;
}

int main() {
int n;
node *root = 0;
    for (scanf("%d",&n);n;--n) {
        int x;
        scanf("%d",&x);    
        root = insert(root, x);
    }
    printf("%d\n",root->val);
    return 0;
}