Home PAT 1066 Root of AVL Tree
Post
Cancel

PAT 1066 Root of AVL Tree

Link

AVL 模板题, 我之前也写过一篇相关的题解, 有图, 较为详细.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,v;
struct node{
    int val;
    struct node *lch,*rch;
};
int getHeight(node *root){
    if(root==NULL) return 0;
    return max(getHeight(root->lch),getHeight(root->rch))+1;
}
node *leftRotate(node *root){
    if(root->rch==NULL) return NULL;
    node *p=root->rch;
    root->rch=p->lch;
    p->lch=root;
    return p;
}
node *rightRotate(node *root){
    if(root->lch==NULL) return NULL;
    node *p=root->lch;
    root->lch=p->rch;
    p->rch=root;
    return p;
}
node *leftRightRotate(node *root){
    if(root->lch==NULL) return NULL;
    if(root->lch->rch==NULL) return NULL;
    node *p=leftRotate(root->lch);
    root->lch=p->rch;
    p->rch=root;
    return p;
}
node *rightLeftRotate(node *root){
    if(root->rch==NULL) return NULL;
    if(root->rch->lch==NULL) return NULL;
    node *p=rightRotate(root->rch);
    root->rch=p->lch;
    p->lch=root;
    return p;
}
node *insert(node *root,int val){
    if(root==NULL){
        root=new node();
        root->val=val,root->lch=root->rch=NULL;
    }else if(val<root->val){
        root->lch=insert(root->lch,val);
        if(getHeight(root->lch)-getHeight(root->rch)==2){
            if(getHeight(root->lch->lch)-getHeight(root->lch->rch)==1) root=rightRotate(root);
            else root=leftRightRotate(root);
        }
    }else{
        root->rch=insert(root->rch,val);
        if(getHeight(root->rch)-getHeight(root->lch)==2){
            if(getHeight(root->rch->rch)-getHeight(root->rch->lch)==1) root=leftRotate(root);
            else root=rightLeftRotate(root);
        }
    }
    return root;
}
int main() {
    node *root=NULL;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&v);
        root=insert(root,v);
    }
    printf("%d\n",root->val);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.