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
", solve.A[root]);
    return 0;
}