5 平衡二叉树（AVL树）3题

sy357: 二叉查找树的平衡因子

https://sunnywhy.com/sfbj/9/5/357

对一棵二叉查找树来说，我们把结点的左子树和右子树的高度之差称为结点的平衡因子。

现将 n 个互不相同的正整数先后插入到一棵空的二叉查找树中，然后按中序遍历的顺序，给出二叉查找树中各结点的平衡因子。

输入

第一行一个整数 $n(1\le n\le 50)$，表示二叉查找树的结点个数；

第二行个整数 $a_i(1\le a_i\le 100)$，表示插入序列。

输出

输出 n 个整数，表示 n 个结点的平衡因子，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

7
5 2 3 6 1 8 7

输出

0 0 0 -1 -2 0 1

解释

生成的二叉查找树和每个结点的平衡因子计算过程如图所示。

To solve this problem, you can follow these steps:

1. Read the input sequence.
2. Insert the values into a binary search tree (BST).
3. Perform an inorder traversal of the BST and calculate the balance factor for each node. The balance factor of a node is the height of its left subtree minus the height of its right subtree.
4. Print the balance factors in the order they were visited during the inorder traversal.

Here is the Python code that implements this plan:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)
        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

    def _get_height(self, node):
        if node is None:
            return 0
        return node.height

    def balance_factors(self):
        return self._balance_factors(self.root)

    def _balance_factors(self, node):
        if node is None:
            return []
        balance_factor = self._get_height(node.left) - self._get_height(node.right)
        return self._balance_factors(node.left) + [balance_factor] + self._balance_factors(node.right)

n = int(input().strip())
sequence = list(map(int, input().strip().split()))

bst = BST()
for value in sequence:
    bst.insert(value)

print(' '.join(map(str, bst.balance_factors())))

This code reads the sequence from the input, inserts its values into a BST, calculates the balance factors of the nodes during an inorder traversal of the BST, and then prints the results.

sy358: 平衡二叉树的判定

https://sunnywhy.com/sfbj/9/5/358

将 n 个互不相同的正整数先后插入到一棵空的二叉查找树中，判断最后生成的二叉查找树是否是平衡二叉树（AVL树）。

输入

第一行一个整数 $n(1\le n\le 50)$，表示二叉查找树的结点个数；

第二行个 n 整数 $a_i(1\le a_i\le 100)$，表示插入序列。数据保证序列元素互不相同。

输出

如果是平衡二叉树，那么输出Yes，否则输出No。

样例1

输入

5
5 2 3 6 1

输出

Yes

解释

对应的二叉查找树如下所示，是平衡二叉树。

样例2

输入

4
5 2 3 1

输出

No

解释

对应的二叉查找树如下所示，不是平衡二叉树。

To solve this problem, you can follow these steps:

1. Read the input sequence.
2. Insert the values into a binary search tree (BST).
3. Check if the BST is balanced. A BST is balanced if the absolute difference between the heights of the left and right subtrees of every node is at most 1.
4. Print "Yes" if the BST is balanced, otherwise print "No".

Here is the Python code that implements this plan:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)
        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

    def _get_height(self, node):
        if node is None:
            return 0
        return node.height

    def is_balanced(self):
        return self._is_balanced(self.root)

    def _is_balanced(self, node):
        if node is None:
            return True
        balance_factor = abs(self._get_height(node.left) - self._get_height(node.right))
        return balance_factor <= 1 and self._is_balanced(node.left) and self._is_balanced(node.right)

n = int(input().strip())
sequence = list(map(int, input().strip().split()))

bst = BST()
for value in sequence:
    bst.insert(value)

if bst.is_balanced():
    print("Yes")
else:
    print("No")

This code reads the sequence from the input, inserts its values into a BST, checks if the BST is balanced, and then prints the result.

sy359: 平衡二叉树的建立

https://sunnywhy.com/sfbj/9/5/359

将 n 个互不相同的正整数先后插入到一棵空的AVL树中，求最后生成的AVL树的先序序列。

输入

第一行一个整数 $n(1\le n\le 50)$，表示AVL树的结点个数；

第二行 n 个整数$a_i(1\le a_i\le 100)$，表示表示插入序列。

输出

输出 n 个整数，表示先序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

5
5 2 3 6 8

输出

3 2 6 5 8

解释

插入的过程如下图所示。

To solve this problem, you can follow these steps:

1. Read the input sequence.
2. Insert the values into an AVL tree. An AVL tree is a self-balancing binary search tree, and the heights of the two child subtrees of any node differ by at most one.
3. Perform a preorder traversal of the AVL tree and print the result.

Here is the Python code that implements this plan:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class AVL:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self.root = self._insert(value, self.root)

    def _insert(self, value, node):
        if not node:
            return Node(value)
        elif value < node.value:
            node.left = self._insert(value, node.left)
        else:
            node.right = self._insert(value, node.right)

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

        balance = self._get_balance(node)

        if balance > 1:
            if value < node.left.value:	# 树形是 LL
                return self._rotate_right(node)
            else:	# 树形是 LR
                node.left = self._rotate_left(node.left)
                return self._rotate_right(node)

        if balance < -1:
            if value > node.right.value:	# 树形是 RR
                return self._rotate_left(node)
            else:	# 树形是 RL
                node.right = self._rotate_right(node.right)
                return self._rotate_left(node)

        return node

    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _rotate_left(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        return y

    def _rotate_right(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
        return x

    def preorder(self):
        return self._preorder(self.root)

    def _preorder(self, node):
        if not node:
            return []
        return [node.value] + self._preorder(node.left) + self._preorder(node.right)

n = int(input().strip())
sequence = list(map(int, input().strip().split()))

avl = AVL()
for value in sequence:
    avl.insert(value)

print(' '.join(map(str, avl.preorder())))

This code reads the sequence from the input, inserts its values into an AVL tree, performs a preorder traversal of the AVL tree, and then prints the result.