二叉搜索树

约 896 字 预计阅读 3 分钟 本文访问量 0 数据结构与算法 搜索树 二叉树

前言

字典抽象数据类型 (Dictionary Abstract Data Type) 用于表示一组 “键 - 值对” 元素，它支持三大核心操作：

  • Search(S, k)：在集合 S 中查找键为 k 的元素，返回对应的值
  • Insert(S, x)：向集合 S 中插入值为 x 的元素（若键已存在，需考虑更新为新值）
  • Remove(S, x/k)：从集合 S 中删除值为 x / 键为 k 的元素

特别地，如果键是有序的（称有序字典），则可支持以下操作：

  • Min(S)：返回集合 S 中键最小的元素
  • Max(S)：返回集合 S 中键最大的元素
  • Predecessor(S, x/k)：返回集合 S 中键小于 k / 值小于 x 的最大元素
  • Successor(S, x/k)：返回集合 S 中键大于 k / 值大于 x 的最小元素

如何高效实现有序字典 ADT 的数据结构即接下来探讨的问题

概念

定义：一种满足 “左子树所有节点值 <= 根节点值，右子树所有节点值 >= 根节点值” 的二叉树，左、右子树也需满足该规则

核心性质：中序遍历可得到有序序列，这是其用于排序、查找的核心依据

插入、查找、删除的时间复杂度均为 \(O (h)\)（\(h\) 为树的高度，平均为 \(\log n\)，但极端情况下会退化为链表（如插入有序数据时 \(h=n\)），此时复杂度降为 \(O (n)\)）

节点

struct BSTNode
{
    int key;
    // type val;
    BSTNode *left;
    BSTNode *right;
    BSTNode *parent;

    explicit BSTNode(int k):key(k),left(nullptr),right(nullptr),parent(nullptr){}
};

查找

从根节点开始，若当前节点为空或键值等于目标值 k，则返回当前节点；若当前节点键值大于 k，则递归查找左子树，否则递归查找右子树

class BST
{
    BSTNode *root; // 根节点

    BSTNode *BSTSearchRecursive(BSTNode *node,int k)
    {
        if(node == nullptr || node->key == k) // 括号内的判断有先后关系
        {
            return node;
        }

        if(node->key > k)
        {
            return BSTSearchRecursive(node->left,k);
        }
        else
        {
            return BSTSearchRecursive(node->right,k);
        }
    }

public:
    BST():root(nullptr){}

    BSTNode *BSTSearchRecursive(int k) // 对外接口
    {
        return BSTSearchRecursive(root,k);
    }
};

当然也可以用迭代实现，相比递归居然更简洁

class BST
{
    // ···
    BSTNode *BSTSearchIterative(int k)
    {
        BSTNode *curr = root;
        while(curr != nullptr && curr->key != k)
        {
            if(k < curr->key)
            {
                curr = curr->left;
            }
            else
            {
                curr = curr->right;
            }
        }
        return curr;
    }
};

最小、最大

由二叉搜索树的性质可知，最小值一定在左子树的最左端，最大值一定在右子树的最右端

class BST
{
    // ···
    BSTNode* BSTMin(BSTNode* node)
    {
        BSTNode *curr = node;
        while(curr->left != nullptr)
        {
            curr = curr->left;
        }
        return curr;
    }

    BSTNode* BSTMax(BSTNode* node)
    {
        BSTNode *curr = node;
        while(curr->right != nullptr)
        {
            curr = curr->right;
        }
        return curr;
    }
    // 当然也可以保留一个无参版本作为对外接口，传入根节点
};

后继、前驱

后继节点为比当前节点大的最小节点，由中序遍历的有序性，根据当前节点有无右子树，后继节点可能为

  • 有右子树：右子树的最小节点
  • 无右子树：其最近的祖先中左子节点也是该节点祖先者（第一个要“左拐”的祖先）
    x               y               y              // 查找 x 的后继，在这里为 y
   / \             / \             / \             // s 表示子树，在这里不关心
  s   a           x   s           a   s
     / \         /               / \
    y   s       s               s   x
                                   /
                                  s

中序遍历：s x y a s、s x y s、s a s x y s

class BST
{
    // ···
    BSTNode *BSTSuccessor(BSTNode *node)
    {
        if(node == nullptr)
        {
            return nullptr;
        }
        // 如果有右子树
        if(node->right != nullptr)
        {
            return BSTMin(node->right);
        }
        // 如果没有右子树
        while(node->parent != nullptr && node == node->parent->right)
        {
            node = node->parent;
        }
        return node->parent;
    }
};

前驱与后继同理，只不过左右方向相反

插入

为了保存有序性，实则插入也类似做搜索，只不过会停止在某个叶子节点上，然后将待插元素作为该叶子节点的左或右子节点

class BST
{
    // ···
    void BSTInsert(int k)
    {
        BSTNode *newNode = new BSTNode(k);
        BSTNode *parent = nullptr; // 保留父节点
        BSTNode *curr = root; // 遍历完为空
        while(curr != nullptr) // 查找
        {
            parent = curr;
            if(k <= curr->key)
            {
                curr = curr->left;
            }
            else
            {
                curr = curr->right;
            }
        }
        newNode->parent = parent; // 插入
        if(parent == nullptr)
        {
            root = newNode;
        }
        else if(k <= parent->key)
        {
            parent->left = newNode;
        }
        else
        {
            parent->right = newNode;
        }
    }
};

删除

设待删节点为 x，为了保持二叉搜索树的有序性，删除分为三种情况：

  • x 无子节点，直接删除
  • x 只有一个子节点，将子节点 “替换” x
  • x 有两个子节点，用后继 BSTMin(x->right) 替换 x
    • 后继是 x 的直接右子节点（该右子节点无左节点），直接用右子节点替换 x
    • 后继不是 x 的直接右子节点，用后继替换 x，并将后继的右子节点替换后继
case 2:
     r                        r
    / \                      / \
   x   s         ->         w   s
  /
 w  

case 3a:
     r                        r
    / \                      / \
   x   s         ->         y   s
  / \                      / \ 
 w   y                    w   a
      \      
       a        

case 3b:
     r                        r
    / \                      / \
   x   s                    y   s
  / \            ->        / \
 w   z                    w   z
    / \                      / \
   y   a                    b   a 
    \
     b (也可以不存在)

class BST
{
    // 辅助函数：用新节点替换旧节点
    void transplant(BSTNode* u, BSTNode* v) {
        if (u->parent == nullptr) {
            root = v;  // u是根节点
        } else if (u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }
        if (v != nullptr) {
            v->parent = u->parent;
        }
    }

    void BSTRemove(BSTNode* node) {
        if (node == nullptr) return;
        
        // 无左子节点（包括无子节点和只有右子节点）
        if (node->left == nullptr) {
            transplant(node, node->right);
            delete node;
        }
        // 无右子节点（只有左子节点）
        else if (node->right == nullptr) {
            transplant(node, node->left);
            delete node;
        }
        // 有两个子节点
        else {
            // 找到后继节点（右子树的最小节点）
            BSTNode* successor = BSTMin(node->right);
            
            // 如果后继节点不是 node 的直接右子节点
            if (successor->parent != node) {
                transplant(successor, successor->right);
                successor->right = node->right;
                successor->right->parent = successor;
            }
            
            // 用后继节点替换 node
            transplant(node, successor);
            successor->left = node->left;
            successor->left->parent = successor;
            
            delete node;
        }
    }
};

拓展

BST 的旋转

旋转分为左旋和右旋，用以调整 BST 的结构，使其更平衡

性质：选转前后不改变树的中序遍历结果，即仍保持有序性

  • 对 A 左旋，中序遍历：T1 A T2 B T3
  A                    B
 / \                  / \
T1  B        ->      A  T3
   / \              / \
  T2 T3            T1 T2

实现：更新 A 的右子树为 B 的左子树，调整 A 和 B

class BST
{
    void rotateLeft(BSTNode *A){
        BSTNode *B = A->right;

        A->right = B->left; // 更新 A 的右子树
        if(B->left != nullptr){
            B->left->parent = A;
        }

        B->parent = A->parent; // B 继承 A 的父节点
        if(A->parent == nullptr){
            root = B;
        }
        else if(A == A->parent->left){
            A->parent->left = B;
        }
        else{
            A->parent->right = B;
        }

        B->left = A; // 调整 A B 的父子关系
        A->parent = B;
    }
};
  • 对 A 右旋，中序遍历：T1 B T2 A T3
    A                  B
   / \                / \
  B  T3      ->      T1  A
 / \                    / \
T1 T2                  T2 T3

实现：更新 A 的左子树为 B 的右子树，调整 A 和 B

class BST
{
    void rotateRight(BSTNode *A){
        BSTNode *B = A->left;

        A->left = B->right; // 更新 A 的左子树
        if(B->right != nullptr){
            B->right->parent = A;
        }

        B->parent = A->parent; // B 继承 A 的父节点
        if(A->parent == nullptr){
            root = B;
        }
        else if(A == A->parent->left){
            A->parent->left = B;
        }
        else{
            A->parent->right = B;
        }
        B->right = A; // 调整 A B 的父子关系
        A->parent = B;
    }
};

升序数组 => 平衡 BST

平衡二叉树是指所有节点的左右子树的高度相差不超过 1 的二叉树

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}

TreeNode* helper(vector<int>& nums, int left, int right) {
    if (left > right) {
        return nullptr;
    }

    // 选择中间位置作为根节点
    int mid = (left + right) / 2;

    TreeNode* root = new TreeNode(nums[mid]);
    root->left = helper(nums, left, mid - 1);
    root->right = helper(nums, mid + 1, right);
    return root;
}

标题：二叉搜索树

作者：Zwing

创建于：2026-01-16 19:04:31

更新于：2026-08-07 16:17:52

链接：https://zanytriumph.github.io/posts/二叉搜索树.html

版权声明：本文章采用 CC BY-NC-SA 4.0 进行许可