W4

  1. 数据结构相关笔记①
  2. 数据结构相关笔记②
  3. 数据结构相关笔记③
  4. 数据结构相关笔记④
  5. 数据结构相关笔记⑤
  6. 数据结构相关笔记⑥
  7. 数据结构相关笔记⑦

二叉搜索树（Binary Search Tree）

  • 定义：二叉搜索树（Binary Search Tree，BST）是一种二叉树，存储键或键值对，满足以下性质：

    • 对于每个节点 v，其左子树中的所有节点的键值都小于 v 的键值。
    • 其右子树中的所有节点的键值都大于 v 的键值。
    • 中序遍历 (Inorder Traversal) 二叉搜索树将会以递增顺序访问键值。

  • 特点：任意节点 v 的左子树节点值均小于 v，右子树节点值均大于 v。搜索、插入、删除操作的时间复杂度与树的高度相关。

二叉搜索树的操作

1. 搜索（Search）

从根节点开始，沿着树向下遍历，依次比较要查找的键 k 与当前节点的键值：

  • 如果 k 小于当前节点的键值，继续递归搜索左子树。
  • 如果 k 大于当前节点的键值，继续递归搜索右子树。
  • 如果找到外部节点（空节点），则说明树中没有该键。
def search(k, v): 
    if v.isExternal():
        return v  # 失败的搜索
    if k == key(v):
        return v  # 成功的搜索
    elif k < key(v):
        return search(k, v.left)  # 递归搜索左子树
    else:
        return search(k, v.right)  # 递归搜索右子树

2. 插入（Insertion）

首先按照搜索的方式找到适合插入的外部节点 w。替换该外部节点，创建一个新的内部节点以存储键值。

def insert(k, v):
    w = search(k, root)
    if w.isExternal():
        replace w with internal node holding (k, o)

3. 删除（Deletion）

需要先找到要删除的节点 w。删除分为两种情况：

  • 情况1： 如果 w 有一个外部子节点，直接移除该节点并提升另一个子节点的位置。
  • 情况2： 如果 w 有两个内部子节点，需要找到后继节点（右子树中键值最小的节点），替换内容并移除该后继节点。
def remove(k): 
    w = search(k, root)
    if w.isExternal():
        return null  # 找不到该键
    elif w has one external child:
        remove external child z, promote other child
    else:
        y = immediate successor of w
        replace w with y, remove y as above

二叉搜索树的时间复杂度

二叉搜索树的操作时间复杂度与树的高度 h 成正比：

  • 最坏情况： 当树退化成链表时，树的高度为 n，时间复杂度为 O(n)。
  • 最好情况： 树是平衡的，高度为 O(logn)，操作的时间复杂度为 O(logn)。

因此，二叉搜索树在平衡的情况下，搜索、插入和删除操作都可以在 O(logn) 时间内完成，但在最坏情况下可能退化为 O(n)。

区间查询（Range Query）

区间查询的目的是在二叉搜索树中找到所有键值在给定区间 [k1, k2] 之间的节点，并将它们按顺序输出。通常，区间查询涉及遍历树的某些部分，并跳过那些不可能包含目标值的分支，以减少遍历的工作量。

区间查询的工作原理

由于二叉搜索树的结构特性（左子树节点的键值小于根节点，右子树节点的键值大于根节点），我们可以通过以下方法来高效地查找范围内的所有节点。

  1. 基本思想

    • 当当前节点的键值小于 k1 时，意味着该节点和它的左子树中的所有节点的键值都小于 k1，因此我们可以忽略左子树，直接继续在右子树中查找。
    • 当当前节点的键值大于 k2 时，意味着该节点和它的右子树中的所有节点的键值都大于 k2，因此我们可以忽略右子树，直接在左子树中查找。
    • 如果当前节点的键值在 [k1, k2] 范围内，那么这个节点就是一个有效节点，我们可以将其输出，并继续递归地在它的左右子树中查找。

  2. 区间查询的伪代码

def range_query(node, k1, k2, result):
    # 如果节点为空，直接返回
    if node is None:
        return

    # 如果当前节点的键值大于 k1，则它的左子树可能包含符合条件的节点
    if node.key > k1:
        range_query(node.left, k1, k2, result)

    # 如果当前节点的键值在 k1 和 k2 之间，输出该节点
    if k1 <= node.key <= k2:
        result.append(node.key)

    # 如果当前节点的键值小于 k2，则它的右子树可能包含符合条件的节点
    if node.key < k2:
        range_query(node.right, k1, k2, result)
  1. 时间复杂度分析
    • 最优情况下（即树是平衡的，且区间较小），只需遍历树的一部分，时间复杂度为 O(logn + k)，其中 n 是树中的节点数，k 是返回的符合条件的节点数量。
    • 最坏情况下（例如，树退化为链表或区间很大），需要遍历树的每个节点，时间复杂度为 O(n)。

AVL 树 (Adelson-Velsky and Landis Tree)

AVL树是一种自平衡二叉搜索树，通过严格控制树的高度来确保高效的查找、插入和删除操作。它以两位发明者Adelson-Velsky和Landis的名字命名。下面是AVL树的详细介绍：

1. AVL树的定义

  • 二叉搜索树 (BST) 特性：

    • 左子树中所有节点的值都小于当前节点的值。
    • 右子树中所有节点的值都大于当前节点的值。

  • 平衡因子 (Balance Factor)：

    • 对于任意一个节点，平衡因子定义为该节点的左子树高度与右子树高度的差值：
    • 平衡因子 = 左子树的高度 - 右子树的高度
    • 一个AVL树的每个节点的平衡因子必须是 -1、0 或 1。如果某个节点的平衡因子不在此范围内，树就不再平衡，需要通过旋转操作恢复平衡。

2. AVL树的操作

插入操作 (Insertion)

AVL树的插入操作和普通的二叉搜索树相同，但插入后可能导致某些节点的平衡因子超出范围，因此需要进行旋转操作来重新平衡树。

  • 步骤：
    1. 按照二叉搜索树的规则插入新节点。
    2. 从插入节点开始向上回溯，更新每个祖先节点的平衡因子。
    3. 一旦某个祖先节点的平衡因子超出范围（即平衡因子不是 -1、0、1），需要对该节点进行旋转操作。

旋转操作 (Rotations)

AVL树的关键在于通过旋转来恢复平衡。有四种旋转操作：

  • 单右旋转 (Right Rotation, RR)：

    • 发生在左子树高度超过右子树时。
    • 通过旋转将右子树的高度提升，恢复平衡。

  • 单左旋转 (Left Rotation, LL)：

    • 发生在右子树高度超过左子树时。
    • 通过旋转将左子树的高度提升，恢复平衡。

  • 左-右旋转 (Left-Right Rotation, LR)：

    • 先对左子树进行左旋转，然后再对根节点进行右旋转。

  • 右-左旋转 (Right-Left Rotation, RL)：

    • 先对右子树进行右旋转，然后再对根节点进行左旋转。

删除操作 (Deletion)

AVL树的删除操作和普通的二叉搜索树相同，但删除后也可能导致树失衡，因此需要进行旋转来重新平衡树。

  • 步骤：
    1. 按照二叉搜索树的规则找到要删除的节点并删除它。
    2. 从删除节点的父节点开始，向上回溯，更新每个祖先节点的平衡因子。
    3. 一旦某个祖先节点的平衡因子超出范围，进行旋转操作恢复平衡。

3. 时间复杂度

由于AVL树是严格平衡的，树的高度最多为 O(logn)，因此各种操作（如查找、插入和删除）的时间复杂度都是 O(logn)。