数据结构平衡二叉排序树

### 平衡二叉排序树概述

平衡二叉排序树是一种特殊的二叉排序树，其特点是任何节点的两棵子树的高度差不超过1。这种结构能够保证在最坏情况下操作的时间复杂度仍为O(log n)，从而提高了查询、插入和删除等操作的效率[^1]。

#### 特性说明

为了保持上述性质，在进行插入或删除结点之后可能需要调整整棵树来恢复平衡状态。具体来说，当某处失衡时会通过一系列称为旋转的操作来进行修正，主要包括四种基本形式：

- **LL型**：新节点插入到左孩子的左侧；
- **RR型**：新节点插入到右孩子的右侧；
- **LR型**：先对当前节点做一次单向右旋再做一次单向左旋；
- **RL型**：先对当前节点做一次单向左旋再做一次单向右旋；

这些旋转方式可以有效地维持AVL树（即自平衡二叉搜索树的一种）的高度平衡属性。

#### Python实现示例

下面给出一段简单的Python代码用于创建并维护一棵平衡二叉排序树:

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


def get_height(node):
    if not node:
        return 0
    return node.height


def update_height(node):
    if node is not None:
        node.height = max(get_height(node.left), get_height(node.right)) + 1


def balance_factor(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)


def rotate_right(y):
    x = y.left
    T2 = x.right
    
    # Perform rotation
    x.right = y
    y.left = T2
    
    # Update heights
    update_height(y)
    update_height(x)

    return x


def rotate_left(x):
    y = x.right
    T2 = y.left
    
    # Perform rotation
    y.left = x
    x.right = T2
    
    # Update heights
    update_height(x)
    update_height(y)

    return y


def insert(root, key):
    # Step 1 - Perform normal BST insertion
    if not root:
        return Node(key)
    
    elif key < root.key:
        root.left = insert(root.left, key)
        
    else:
        root.right = insert(root.right, key)

    # Step 2 - Update the height of ancestor nodes
    update_height(root)

    # Step 3 - Get the balance factor and decide whether this node became unbalanced
    bf = balance_factor(root)

    # If it becomes unbalanced, then there are four cases...

    # Case 1 - Left Left (LL)
    if bf > 1 and key < root.left.key:
        return rotate_right(root)

    # Case 2 - Right Right (RR)
    if bf < -1 and key > root.right.key:
        return rotate_left(root)

    # Case 3 - Left Right (LR)
    if bf > 1 and key > root.left.key:
        root.left = rotate_left(root.left)
        return rotate_right(root)

    # Case 4 - Right Left (RL)
    if bf < -1 and key < root.right.key:
        root.right = rotate_right(root.right)
        return rotate_left(root)

    return root

此段程序定义了一个`Node`类表示树中的每一个节点，并实现了四个主要函数用来处理不同类型的不平衡情况以及完成标准BST插入后的重新平衡过程。