题目

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.

img img

img img

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

题解

思路

  • 考纲里没有AVL树的内容，所以应该是不考的。
  • 写法就是按照题目意思，构造一个AVL BST。

数据结构

  • Node 是一个节点，属性包含
  • val
  • left
  • right

算法

  • rotateLeft 是左旋
    • 就是当右边太长的时候
    • 把右节点当成根节点
    • 方法是，根的右节点改为右节点的左节点，而右节点的左节点改为根。
    • 返回这个新的根节点
  • rotateRight 是右旋
    • 就是当左边太长的时候
    • 把左节点当成根节点
    • 方法是，原根的左节点改为左节点的右节点，而左节点的右节点改为原根。
    • 返回这个新的根节点
  • 以上两步画图就好理解了。
  • getHeight 找到这个节点的高度，这个没什么问题
  • insert 插入一个数，并返回根节点。
    • 插入的时候，从根节点不断比大小找到应该放的位置
    • 放完了后，判断有没有造成不平衡
    • 即左子树和右子树的差的绝对值有没有大于2
    • 不平衡了那么就需要rotate
    • 但是要注意一件事情
    • 举例来说，如果我往左侧插入一个数，造成了不平衡，左边太长了，这时候想到要右旋
    • 如果要插入的数比根结点的左侧还要大，即，它应该才是根的左节点
    • 这种情况下，要先对左子树进行左旋。
    • 为什么要这样做呢？因为每次右旋都会使根变成根的左节点，而这时候根的左节点并不是新节点，所以右旋是错误的。
    • 我们这样处理，就相当于把原来的根节点的左节点压下去了。
  • 反正是超纲的，问题不大，不会不用管就行。

代码

  • 因为使用Python3能AC，所以只放了Python的代码。
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
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def rotateLeft(self):
        node = self.right
        self.right = node.left
        node.left = self
        return node

    def rotateRight(self):
        node = self.left
        self.left = node.right
        node.right = self
        return node

    def getHeight(self):
        left = 0 if not self.left else self.left.getHeight()
        right = 0 if not self.right else self.right.getHeight()
        return max(left, right) + 1

    def insert(self, val):
        if not self.val:
            self.val = val
            return self

        if self.val > val:
            self.left = Node(val) if not self.left else self.left.insert(val)
            left = 0 if not self.left else self.left.getHeight()
            right = 0 if not self.right else self.right.getHeight()
            if (left - right) == 2:
                if val >= self.left.val:
                    self.left = self.left.rotateLeft()
                self = self.rotateRight()
        else:
            self.right = Node(val) if not self.right else self.right.insert(val)
            left = 0 if not self.left else self.left.getHeight()
            right = 0 if not self.right else self.right.getHeight()
            if (left - right) == -2:
                if val <= self.right.val:
                    self.right = self.right.rotateRight()
                self = self.rotateLeft()
        return self


root = Node(None)
_ = input()
for i in input().split():
    root = root.insert(int(i))
print(root.val)