Root Of AVL Tree

发表于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

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. 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 the root of the resulting AVL tree in one line.

Sample Input 1

1
2
5
88 70 61 96 120

Sample Output 1

1
70

Sample Input 2

1
2
7
88 70 61 96 120 90 65

Sample Output 2

1
88

代码

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<stdio.h>
typedef struct AVLNode * Position;
typedef Position AVLTree;   //AVL树类型
typedef int ElementType;
typedef struct AVLNode {
    ElementType Data;   //结点数据
    AVLTree Left;   //指向左子树
    AVLTree Right;  //指向右子树
    int Height; //树高
};
int Max(int a, int b);
AVLTree Insert(AVLTree T, ElementType X);
int GetHeight(AVLTree T);
AVLTree SingleLeftRotation(AVLTree A);
AVLTree SingleRightRotation(AVLTree A);
AVLTree DoubleLeftRightRotation(AVLTree A);
AVLTree DoubleRightLeftRotation(AVLTree A);
int main()
{
    int N, num;
    AVLTree T = NULL;

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num);
        T = Insert(T, num);
    }
    printf("%d", T->Data);

    return 0;
}
int Max(int a, int b)
{
    return a > b ? a : b;
}
AVLTree Insert(AVLTree T, ElementType X)
{//将X插入AVL树中，并且返回调整后的AVL树
    if (!T)//若插入空树，则新建包含一个结点的树
    {
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 1;
        T->Left = T->Right = NULL;
    }
    else if (X < T->Data)
    {//插入左子树
        T->Left = Insert(T->Left, X);
        //如果需要左旋
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
        {
            if (X < T->Left->Data)
                T = SingleLeftRotation(T);  //左单旋
            else
                T = DoubleLeftRightRotation(T); //左-右双旋
        }
    }
    else if (X > T->Data)
    {
        //插入右子树
        T->Right = Insert(T->Right, X);
        //如果需要右旋
        if (GetHeight(T->Right) - GetHeight(T->Left) == 2)
        {
            if (X > T->Right->Data)
                T = SingleRightRotation(T); //右单旋
            else
                T = DoubleRightLeftRotation(T); //右-左双旋
        }
    }
    //else X==T->Data,无需插入

    //别忘了更新树高
    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;

    return T;
}
int GetHeight(AVLTree T)
{
    if (T)
        return T->Height;
    else
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A)
{//注意：A必须有一个左子结点B
    //将A与B做左单旋，更新A与B的高度，返回新的根节点B
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}
AVLTree SingleRightRotation(AVLTree A)
{//注意：A必须有一个右子结点B
    //将A与B做右单旋，更新A与B的高度，返回新的根节点B
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Right), A->Height) + 1;

    return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A)
{//注意：A必须有一个左子结点B，且B必须有一个右子节点C
    //将A、B与C做两次单旋，返回新的根节点C

    //B与C做右单旋，返回C
    A->Left = SingleRightRotation(A->Left);
    //A与C做左单旋，返回C
    return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A)
{//注意：A必须有一个右子结点B，且B必须有一个左子节点C
    //将A、B与C做两次单旋，返回新的根节点C

    //B与C做左单旋，返回C
    A->Right = SingleLeftRotation(A->Right);
    //A与C做右单旋，返回C
    return SingleRightRotation(A);
}

测试点

1
2
3
4
5
6
7
8
测试点      提示
0           fig 1 - LL
1           fig 2 - RR
2           fig 3 - RL
3           fig 4 - LR
4           深度LL旋转
5           最大N，深度RL旋转
6           最小N