树结构中的二分查找：二叉搜索树与 AVL 树比较

# 1. **介绍**
1.1 二分查找的基本概念
- 二分查找，又称折半查找，是一种在有序数组中查找特定元素的算法。
- 算法的基本思想是每次取数组中间的值与目标值比较，如果相等则返回，如果小于目标值则在右半部分继续查找，反之在左半部分继续查找。
- 时间复杂度为 O(log n)，是一种高效的查找算法。
1.2 树结构在查找中的应用
- 树是一种数据结构，常用于表示层次关系或者是树形关系的数据。
- 在查找问题中，树结构的应用可以帮助提高查找效率，如二叉搜索树和AVL树等。
- 二叉搜索树是一种常见的树结构，利用其特点可以加速查找过程，提高算法的效率。

# 2. 二叉搜索树（BST）

二叉搜索树（Binary Search Tree，简称BST）是一种常用的数据结构，具有以下特点：

1. 二叉搜索树是一棵空树，或者是具有以下性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
- 左、右子树也分别为二叉搜索树。

2. 二叉搜索树的插入操作：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

3. 二叉搜索树的查找操作：

def search_bst(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

4. 二叉搜索树的删除操作：

def delete_bst(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        temp = find_min(root.right)
        root.val = temp.val
        root.right = delete_bst(root.right, temp.val)
    return root

5. 二叉搜索树的性质保证了在最坏情况下，插入、查找、删除的时间复杂度均为O(n)，其中n为树中的节点数量。二叉搜索树的效率取决于树的平衡程度，在极端情况下可能退化成链表，导致性能下降。

graph TD
    A(开始) --> B{条件A}
    B --> |是| C[结果A]
    C --> D{条件B}
    D --> |是| E[结果B]
    D --> |否| F[结束]
    B --> |否| F

以上是关于二叉搜索树的基本介绍，下面将进一步探讨 AVL 树的相关内容。

# 3. **AVL 树**

AVL 树是一种自平衡的二叉搜索树，能够保持树的高度平衡，以确保查找、插入和删除操作的时间复杂度不会恶化到 O(n)。接下来将详细介绍 AVL 树的概念、特点、平衡调整和旋转操作。

#### 3.1 AVL 树的概念与特点

AVL 树是由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年发明的自平衡二叉搜索树。它具有以下特点：
- 对于任意节点，其左右子树的高度差（平衡因子）不超过 1；
- 每个子树也是一个 AVL 树。

#### 3.2 AVL 树的平衡调整

在 AVL 树中，插入或删除节点后可能会破坏树的平衡，需要通过旋转操作来恢复平衡。常见的旋转操作包括 LL（左左）、LR（左右）、RR（右右）和 RL（右左）。

下面是一个 AVL 树的旋转操作流程示意图：

graph LR
    A(( ) 
    B(( )
    C(( )
    D(( )
    E(( )

    A --> B
    B --> C
    B --> D
    A --> E

#### 3.3 AVL 树的旋转操作

AVL 树的旋转操作分为四种情况：
1. LL（左左）旋转：在某个节点的左子树的左子树上插入节点；
2. RR（右右）旋转：在某个节点的右子树的右子树上插入节点