前言

在准备考研复习专业课数据结构，所以我在mooc平台上找了浙江大学的数据结构课程重新学习，感觉老师留的课后题都很有趣，所以想记录下自己的学习过程。

题目：

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.

F1.jpg

F2.jpg

F3.jpg

F4.jpg

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
#include<cstdio>
#include<cstdlib>
//定义平衡二叉树结构
struct AVL_Node {
    int data;           //节点数据
    int height;          //树高
    AVL_Node* left;       //左子树
    AVL_Node*  right;      //右子树
};
typedef AVL_Node *AVLTree;

AVLTree avl = NULL;

//取最大值
int Max(int a,int b){
    return a > b ? a : b;
}

//获取树的高度
int GetHeight(AVLTree avl){
    if(!avl)
        return 0;
    else
        return Max(GetHeight(avl->left), GetHeight(avl->right)) + 1;
}

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 ){
    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->left), 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->right = SingleLeftRotation(A->right);
    return SingleRightRotation(A);
}

//给平衡二叉树插入结点
AVLTree InsertAVLNode(AVLTree avl,int x){
    if(avl==NULL){
        avl = (AVLTree)malloc(sizeof(struct AVL_Node));
        avl->data = x;
        avl->left = avl->right = NULL;
        avl->height = 1;
    }
    else if(x < avl->data){
        /* 插入T的左子树 */
        avl->left = InsertAVLNode( avl->left, x);
        /* 如果需要左旋 */
        if ( GetHeight(avl->left)-GetHeight(avl->right) == 2 )
            if ( x < avl->left->data ) 
               avl = SingleLeftRotation(avl);      /* 左单旋 */
            else 
               avl = DoubleLeftRightRotation(avl); /* 左-右双旋 */
    }
    else if(x > avl->data){
        /* 插入T的右子树 */
        avl->right= InsertAVLNode( avl->right, x);
        /* 如果需要右旋 */
        if ( GetHeight(avl->right)-GetHeight(avl->left) == 2 )
            if ( x > avl->right->data ) 
               avl = SingleRightRotation(avl);      /* 右单旋 */
            else 
               avl = DoubleRightLeftRotation(avl); /* 右-左双旋 */
    }

    avl->height = Max(GetHeight(avl->left), GetHeight(avl->right)) + 1;
    return avl;
}


int main(){
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n;i++){
        scanf("%d", &x);
        avl = InsertAVLNode(avl, x);
    }
    printf("%d", avl->data);
    return 0;
}