1066. Root of AVL Tree (25)【AVL树】——PAT (Advanced Level) Practise

题目信息

1066. Root of AVL Tree (25)

时间限制100 ms

内存限制65536 kB

代码长度限制16000 B

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树,没啥技巧

AC代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    node *left, *right;
    int v, w;
    node(int value, node* l, node* r) : v(value), left(l), right(r), w(0) {}
};
node *nil = new node(0, NULL, NULL);
node *head = nil;
void leftrotate(node *&head){
    node *t = head->right;
    head->right = t->left;
    t->left = head;
    head = t;
    head->left->w = max(head->left->right->w, head->left->left->w) + 1;
    head->w = max(head->right->w, head->left->w) + 1;
}
void rightrotate(node *&head){
    node *t = head->left;
    head->left = t->right;
    t->right = head;
    head = t;
    head->right->w = max(head->right->right->w, head->right->left->w) + 1;
    head->w = max(head->right->w, head->left->w) + 1;
}
void insert(node *&head, int v){
    if (head == nil){
        head = new node(v, nil, nil);
    }else if (v > head->v){
        insert(head->right, v);
        if (2 == head->right->w - head->left->w){
            if (v > head->right->v){
                leftrotate(head);
            }else{
                rightrotate(head->right);
                leftrotate(head);
            }
        }
    }else{
        insert(head->left, v);
        if (2 == head->left->w - head->right->w){
            if (v <= head->left->v){
                rightrotate(head);
            }else{
                leftrotate(head->left);
                rightrotate(head);
            }
        }
    }
    head->w = max(head->left->w, head->right->w) + 1;
}
int main()
{
    int n, a;
    scanf("%d", &n);
    while (n--){
        scanf("%d", &a);
        insert(head, a);
    }
    printf("%d\n", head->v);
    return 0;
}

个人游戏推广:

《10云方》与方块来次消除大战!

时间: 12-26

1066. Root of AVL Tree (25)【AVL树】——PAT (Advanced Level) Practise的相关文章

1043. Is It a Binary Search Tree (25)【二叉树】——PAT (Advanced Level) Practise

题目信息 1043. Is It a Binary Search Tree (25) 时间限制400 ms 内存限制65536 kB 代码长度限制16000 B A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than

1086. Tree Traversals Again (25)【二叉树】——PAT (Advanced Level) Practise

题目信息 1086. Tree Traversals Again (25) 时间限制200 ms 内存限制65536 kB 代码长度限制16000 B An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to

1067. Sort with Swap(0,*) (25)【贪心】——PAT (Advanced Level) Practise

题目信息 1067. Sort with Swap(0,*) (25) 时间限制150 ms 内存限制65536 kB 代码长度限制16000 B Given any permutation of the numbers {0, 1, 2,-, N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For exa

1016. Phone Bills (25)——PAT (Advanced Level) Practise

题目信息: 1016. Phone Bills (25) 时间限制 400 ms 内存限制 32000 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue A long-distance telephone company charges its customers by the following rules: Making a long-distance call costs a certain amount per minute, depending

1078. Hashing (25)【Hash + 探测】——PAT (Advanced Level) Practise

题目信息 1078. Hashing (25) 时间限制100 ms 内存限制65536 kB 代码长度限制16000 B The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be "H(

1085. Perfect Sequence (25)【二分查找】——PAT (Advanced Level) Practise

题目信息 1085. Perfect Sequence (25) 时间限制300 ms 内存限制65536 kB 代码长度限制16000 B Given a sequence of positive integers and another positive integer p. The sequence is said to be a "perfect sequence" if M <= m * p where M and m are the maximum and minim

1083. List Grades (25)【水题】——PAT (Advanced Level) Practise

题目信息 1083. List Grades (25) 时间限制400 ms 内存限制65536 kB 代码长度限制16000 B Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of w

1082. Read Number in Chinese (25)【字符串处理】——PAT (Advanced Level) Practise

题目信息 1082. Read Number in Chinese (25) 时间限制400 ms 内存限制65536 kB 代码长度限制16000 B Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output "Fu" first if it is negative. For example, -123456789 is

04-树4. Root of AVL Tree (25)

04-树4. Root of AVL Tree (25) 时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 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 tim