二分搜索树BST、AVL树

发表于 2025/10/13 更新于 2025/12/30

作者 CrabPeelMyShell

10 分钟阅读

二分搜索树BST、AVL树

二分搜索树（Binary Search Tree）

相比于二叉树有更加严格的性质：

无重复元素
从左到右、从上到下依次增大

寻找（Find）

核心想法是一直比较左右节点，然后向下递归查找。

找最小

  
BinaryNode<Comparable>* findMin(BinaryNode<Comparable>* t) const {
  if (t == nullptr)
      return nullptr;
  if (t->left == nullptr)
      return t;
  return findMin(t->left);
}

找最大

  
BinaryNode<Comparable>* findMax(BinaryNode<Comparable>* t) const {
  if (t != nullptr){
      while (t->right != nullptr)
      t = t->right;
  }
  return t;
}

找任意一个

  
bool contains(const Comparable& x, BinaryNode<Comparable>* t) const
{
  if (t == nullptr) return false;
  else if (x < t->element)
      return contains(x, t->left);
  else if (t->element < x)
      return contains(x, t->right);
  else
      return true;
}

时间复杂度都是 $O(h)$ 。

插入（Insert）

插入节点只插在叶子节点后

  
void insert(const Comparable& x, BinaryNode<Comparable>*& t) 
{
    if (t == nullptr)
    {
        t = new BinaryNode<Comparable>(x, nullptr, nullptr);
    }
    else if (x < t->element)
    {
        insert(x, t->left);
    }
    else if (t->element < x)
    {
        insert(x, t->right);
    }
    else
    {
        ; // Duplicate, do nothing
    }
}

移除（Erase）

分为三种情况：

叶子节点 delete 然后其父节点的相应子节点设为 nullptr
该节点有一个子节点子节点接到父节点，删除该节点
该节点有两个子节点（Full Node）选左子树最大/右子树最小，替换该节点，删除该节点（可能会用到前两种情况）

要对原树进行操作，需要传入引用

  
void remove(const Comparable& x, BinaryNode<Comparable>*& t) {
    if (t == nullptr)
        return; // Item not found; do nothing 未找到
    if (x < t->element)
        remove(x, t->left);
    else if (x > t->element)
        remove(x, t->right);
    else if (t->left != nullptr && t->right != nullptr) // Two children 两个子节点
    {
        t->element = findMin(t->right)->element; // 找到右边最小的
        remove(t->element, t->right);
    }
    else // 回到前两种 remove 
    { 
        BinaryNode<Comparable>* oldNode = t; 
        t = (t->left != nullptr) ? t->left : t->right;
        delete oldNode;
    }
}

前驱/后继（Predecessor/Successor）和找到第 k 个元素

也可以理解为前一个小的，后一个大的；以及查找第 $k$ 个，$k$ 是从1开始的索引；

对于如何找到第 $k$ 个元素，这里有一个关键的前提，树中的每个节点必须额外存储该节点（及其所有后代）的总大小 (tree_size) 。由于是递归的查找，所以都是从根节点开始。

假设我们获取了左子树的大小为 $l$ ：

若 $l=k$ ：那么左子树正好有个元素（索引从 0 到 $k-1$）。此时当前节点就是我们要找的索引为 k 的元素。
若 $l>k$ ：左子树的元素数量大于 $k$ ，也就是第 $k$ 个元素在左子树中。需要我们在左子树中递归地查找第 $k$ 个元素。
若 $l<k$ ：不在左子树，也不是根节点，在右子树。我们已经在左子树中跳过了 $l$ 个元素，并跳过了 1 个根节点。因此，我们现在需要寻找的目标在右子树中是第 $(k - l - 1)$ 个元素。递归地在右子树中寻找第 $(k - l - 1)$ 个元素。

对于寻找前驱和后继，其逻辑是镜像对称的，这里用寻找后继来举例解释：

寻找后继节点分为两种情况：