PAT (Advanced Level) Practise 1066 Root of AVL Tree (25)

1066. Root of AVL Tree (25)

時間限制

100 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

Sample Input 1:

5

88 70 61 96 120

Sample Output 1:

70

Sample Input 2:

7

88 70 61 96 120 90 65

Sample Output 2:

88

給定一些數字，生成一棵AVL樹，問樹根是多少。

做了之前那麼多題，不得不說，這題是個奇葩，看了很多人的題解，毫無例外是直接建的avl樹，而這樣的題竟然隻有25分，還是個甲級題。

我不覺得有幾個人能在考場上寫出這種東西來。。。吓得我好幾天沒刷題，去好好看了看avl樹的要點。

其實平衡樹無非就是旋轉操作，而最基本的就是左旋和右旋，其他一切變換都是在這個的基礎上進行的。

了解了何為avl樹以後，直接拿splay的模闆，改動一下，過了樣例一送出就AC了，看來平衡樹我掌握的還不錯。。。

#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
int n, root, x;

struct AVL
{
    const static int maxn = 1e5 + 10;
    int F[maxn], ch[maxn][2], sz;
    int H[maxn], A[maxn];
    int Node(int f, int x){ H[sz] = 1; A[sz] = x; F[sz] = f; ch[sz][0] = ch[sz][1] = 0; return sz++; }
    void clear(){ sz = 1;   F[0] = ch[0][0] = ch[0][1] = A[0] = H[0] = 0; }
    void Count(int x)
    {
        H[x] = max(H[ch[x][0]], H[ch[x][1]]) + 1;
    }
    void rotate(int x, int k)
    {
        int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
        if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
        F[x] = F[y];    F[y] = x;   ch[x][k] = y;
        Count(y);   Count(x);
    }
    int up(int x)
    {
        while (F[x] && F[F[x]])
        {
            Count(F[x]);    Count(F[F[x]]);
            if (abs(H[ch[F[F[x]]][0]] - H[ch[F[F[x]]][1]]) == 2)
            {
                int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
                y^z ? (rotate(x, y), rotate(x, z)) : rotate(F[x], y);
            }
            else x = F[x];
        }
        while (F[x]) { Count(x); x = F[x]; }
        return x;
    }
    void insert(int &x, int y)
    {
        if (!x) { x = Node(0,y); return; }
        for (int i = x; i; i = ch[i][y > A[i]])
        {
            if (!ch[i][y > A[i]])
            {
                ch[i][y > A[i]] = Node(i, y);
                x = up(ch[i][y > A[i]]);
                break;
            }
        }
    }
}solve;

int main()
{
    scanf("%d", &n);
    solve.clear();
    while (n--)
    {
        scanf("%d", &x);
        solve.insert(root, x);
    }
    printf("%d\n", solve.A[root]);
    return 0;
}