二叉搜索树(binary search tree,BST)是一棵二叉树,任意结点满足两条:左子树里所有结点的值都不大于它,右子树里所有结点的值都不小于它,左右子树各自也是二叉搜索树。这三句话合起来的结果很直接:中序遍历输出一个有序序列。但反过来不成立,输出同一串有序值,树的形状可以完全不同,这是后面所有平衡结构的起点。

定义约束的是整棵子树,不是两个孩子

新手最常读错的一句是"左边比根小、右边比根大"。如果只要求孩子满足,下面这棵树也能通过逐层检查:

    8
   /
  3
   \
    9

3 < 8、9 > 3,局部都对,但 9 落在 8 的左子树里却比 8 大。查找 9 时第一比较就判定"比 8 大,往右走",从此再也碰不到它。定义里的主语是"左子树上的所有结点",不是"左孩子",查找算法每往左走一步都依赖这个承诺。

课件的定义把两条写成"小于等于"和"大于等于",紧接着又说"可以支持插入相等的值,也可以不支持"。这两句放在一起,规则是松的:允许重复时,相等的值从左侧或右侧进来都合定义;不允许重复时,两条都带等号就自相矛盾,一个相等的值两侧都合法。真正拦住它的是插入代码里的 else return false,而不是定义。这两套规则要分开写:不允许重复的版本用严格的小于和大于;允许重复的版本保留等号,但插入方向必须固定。

按 8、3、1、10、6、4、7、14、13 的顺序依次插入得到的树:每个结点左子树里的值都不大于它、右子树里的值都不小于它,中序输出 1 3 4 6 7 8 10 13 14

二叉搜索树能支持重复值,也能不支持,取决于使用场景。标准库这一族容器就是按这条分的:map/set 不接受相等的键,multimap/multiset 接受。相等值怎么走,课件在插入步骤里给了唯一一条硬要求:前后一致,不能一次往右、一次往左。

插入和查找走的是同一条路径

插入只有两种情况:树空,新结点直接当根;树不空,从根开始比,比当前结点大往右、小往左、相等按约定方向走,直到走出空位。空位不是"结点",所以需要一个 parent 记住落脚点的父亲,最后把新结点挂到 parent 的对应成员上。

插入 16 的走位:16 比 8 大往右,比 10 大往右,比 14 大往右,落在空位;红色结点是新结点,每步只比较当前结点的 key

下面几段是 template<class K> class BSTree 的成员函数,Node 是 BSTNode<K> 的别名,_root 是根指针。

#include <iostream>
 
template<class K>
struct BSTNode
{
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;
 
    BSTNode(const K& key)
        : _key(key), _left(nullptr), _right(nullptr)
    {}
};
 
    bool Insert(const K& key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
 
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
 
        Node* newNode = new Node(key);
        if (parent->_key < key)
        {
            parent->_right = newNode;
        }
        else
        {
            parent->_left = newNode;
        }
        return true;
    }
 
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }

查找和插入的循环结构一模一样,区别只在命中时返回结点、走空时返回空指针。代价都由树高决定:最多走高度步,走到空就说明值不存在。课件这句"最多查找高度次"是整篇里最该记住的复杂度结论。

有重复值时,"找到"不等于"找对"。课件在查找那一节要求返回中序里第一个 x,并画了一棵树:8 左边是 3,3 左边是 1,1 的右孩子还是 3。

树里有两个 3:查找要返回中序最先出现的那个,也就是 1 的右孩子上的 3,不是从根往下先撞见的那个

课件在这一节给的查找代码一遇到相等就 return true。如果照那棵树走,从根到 3 的第一站是左上那个 3,返回的就是它,而不是 1 的右孩子——这一节的文字和代码在这里对不上。要满足"中序第一个",只在命中时记下候选、然后继续往左:

    Node* FindFirst(const K& key)
    {
        Node* cur = _root;
        Node* candidate = nullptr;
        while (cur)
        {
            if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else
            {
                candidate = cur;
                cur = cur->_left;
            }
        }
        return candidate;
    }

这段对两种插入约定都成立:相等值都往右走时,路径上第一个相等的结点本来就是所有相等结点的祖先,也就是中序第一个;相等值都往左走时,继续往左才会走到更靠前的那一个,候选会一直被刷新。前提仍是课件那句——相等值的方向不能一会儿左一会儿右,否则"第一个"没有定义。

删除:四种情况,三种形状

课件把删除拆成四种:左右都空、左空、右空、两个孩子都在。前三种的处理动作只差"接上哪个孩子",所以代码里合成两个分支:

待删结点 N 的孩子动作
左空(含叶子)父亲的孩子指针改指 N 的右孩子
右空父亲的孩子指针改指 N 的左孩子
两个孩子都在用左子树最大值或右子树最小值替换 N 的值,转而删除那个结点

两个孩子都在时为什么能换?右子树的最小结点是 N 的中序后继,它左边所有值都比 N 小,右边所有值都比 N 大,放到 N 的位置,整棵树的有序关系不动。它还有一个结构上的好处:右子树最小结点一定没有左孩子,左子树最大结点一定没有右孩子,替换之后问题自动落到前两种形状。删根时父亲是空指针,必须先改 _root,不能走 parent->_left。

课件标出的两个替换法样例:删除 3 和删除 8。删 3 时它的右子树最小结点是 4,删 8 时右子树最小结点是 10,都是把后继的值搬上来、再删掉后继结点

    bool Erase(const K& key)
    {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                break;
            }
        }
        if (cur == nullptr)
        {
            return false;
        }
 
        if (cur->_left == nullptr)
        {
            Node* child = cur->_right;
            if (parent == nullptr)
            {
                _root = child;
            }
            else if (parent->_left == cur)
            {
                parent->_left = child;
            }
            else
            {
                parent->_right = child;
            }
            delete cur;
            return true;
        }
 
        if (cur->_right == nullptr)
        {
            Node* child = cur->_left;
            if (parent == nullptr)
            {
                _root = child;
            }
            else if (parent->_left == cur)
            {
                parent->_left = child;
            }
            else
            {
                parent->_right = child;
            }
            delete cur;
            return true;
        }
 
        Node* rightMinP = cur;
        Node* rightMin = cur->_right;
        while (rightMin->_left)
        {
            rightMinP = rightMin;
            rightMin = rightMin->_left;
        }
        cur->_key = rightMin->_key;
 
        if (rightMinP->_left == rightMin)
        {
            rightMinP->_left = rightMin->_right;
        }
        else
        {
            rightMinP->_right = rightMin->_right;
        }
        delete rightMin;
        return true;
    }
 
    void InOrder() const
    {
        _InOrder(_root);
        std::cout << '\n';
    }
 
private:
    void _InOrder(Node* root) const
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        std::cout << root->_key << ' ';
        _InOrder(root->_right);
    }
 
    Node* _root = nullptr;
int main()
{
    BSTree<int> t;
    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    for (int e : a)
    {
        t.Insert(e);
    }
    t.InOrder();          // 1 3 4 6 7 8 10 13 14
 
    t.Erase(8);
    t.InOrder();          // 1 3 4 6 7 10 13 14
    return 0;
}

Node* rightMinP = cur; 而不是 nullptr,是这段代码最容易写错的一行。待删结点的右子树根本身就可能是最小结点(根没有左孩子),此时 while 一次都不进,rightMinP 只能靠初值。课件在替换分支里留了注释"一定要把 cur 给 rightMinP",说的就是这件事。

删除还有一个只在 key/value 版本里出现的问题。课件 key/value 版的 Erase 在替换时写的是 cur->_key = rightMin->_key;,只搬了 key,没搬 value。结点里存着两个字段,只搬一个会让键和值错位:字典里删 left(根),后继是 right,根结点的 key 变成 "right"、value 还是 "左边",之后再查 right,屏幕上出来的是"左边",而树的形状和中序看起来都正常。

中序有序证明不了树高

中序遍历的代码就是递归的三行,已经在 InOrder 和 _InOrder 里。它能证明"树里存了哪些值、顺序对不对",证明不了"这棵树长什么样"。下面两张图是同一组键的两种形态:

同一组键的两种形状:左边按 8、3、1、10、6、4、7、14、13 的顺序插入,右边按升序插入,已经是一条单支链,中序输出完全相同

把差距量出来:1023 个整数按 1 到 1023 依次插入,树高等于 1023,查找退化成线性扫描;按中点顺序插入,树高是 10。同样的结点数,路径长度差两个数量级。

课件在性能分析里写"最优情况下,二叉搜索树为完全二叉树(或接近完全二叉树),其高度为 log₂N",接着写"最差情况下退化为单支树,高度为 N",最后给出"增删查改时间复杂度为 O(N)"。这三句的口径需要对齐:

  • 高度按层数算是 ⌊log₂N⌋ + 1,按边数是 ⌊log₂N⌋;同一段里 N 一会儿指结点数、一会儿指高度,读起来会差一层。
  • O(N) 是最坏界,不是平均界。插入序列足够乱时,随机二叉搜索树的期望高度是 4.311 ln N(约 2.99 log₂N),这是 Devroye 和 Reed 证明的结论。
  • 二叉搜索树没有"改"这个操作。改 key 等于把结点挪出了它该在的位置,课件后面讲 key/value 场景时自己写了"不支持修改 key"。

"期望"两个字要读准:它对随机序列取平均,不对任何具体序列作保证。按时间戳递增到达的日志、按自增 id 到达的订单、按字母序读进来的词库,都是天然的升序插入。所以标准库不可能用裸 BST,只能自己把树高按住。

另一条常被拿来做对比的路径是二分查找:它能做到 O(log₂N),但要求数据存在支持下标随机访问的结构里并且有序;插入删除要挪动大量元素,平均 O(N)。平衡二叉搜索树要解决的正是这两头。

key 场景与 key/value 场景

二叉搜索树的结点只存 key 时,它只回答"这个值在不在",支持增删查,不支持修改 key。课件给的两个场景很典型:小区无人值守车库把买下车位的车牌号存进树,车来时扫车牌查在不在;英文拼写检查把词库放进树,读文章里的每个单词查一次,不在就标红。这两个场景都只需要 key。

结点多存一个 value,就成了 key/value 结构:增删查仍以 key 为关键字走同一套规则,但允许修改 value。字典存"英文 → 中文",停车系统存"车牌 → 入场时间"(出口用当前时间减入场时间算费用),词频统计存"单词 → 次数"。这三种用法共同点是:查找要拿到 key 对应的数据,而不是只回答在不在。

template<class K, class V>
struct BSTNode
{
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
 
    BSTNode(const K& key, const V& value)
        : _key(key), _value(value), _left(nullptr), _right(nullptr)
    {}
};

课件在这里留了一行被注释掉的 // pair<K, V> _kv;,最终用两个独立成员。两种存法都能工作,分开写的好处是比较时只看 _key,不用记住"pair 默认先比 first 再比 second"。

把上一节的 BSTree<K> 换成 BSTree<K, V>,三个函数改这几处:Insert 多收一个 value 并传给结点构造;Find 返回 Node* 而不是 bool,调用者拿到结点后可以直接改 _value;Erase 的替换分支要同时搬 key 和 value。

    bool Insert(const K& key, const V& value)
    {
        if (_root == nullptr)
        {
            _root = new Node(key, value);
            return true;
        }
 
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
 
        Node* newNode = new Node(key, value);
        if (parent->_key < key)
        {
            parent->_right = newNode;
        }
        else
        {
            parent->_left = newNode;
        }
        return true;
    }
 
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key < key)
            {
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }

Erase 的主体与 key 版相同,只把替换那两行改成:

        cur->_key = rightMin->_key;
        cur->_value = rightMin->_value;

结点里持有裸指针,类就需要管住拷贝和释放。课件给的是标准的"三件套":析构里后序释放整棵树,拷贝构造深拷贝一棵新树,赋值用"传值 + swap"。

    BSTree() = default;
 
    BSTree(const BSTree<K, V>& t)
    {
        _root = Copy(t._root);
    }
 
    BSTree<K, V>& operator=(BSTree<K, V> t)
    {
        std::swap(_root, t._root);
        return *this;
    }
 
    ~BSTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
 
private:
    Node* Copy(Node* root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        Node* newRoot = new Node(root->_key, root->_value);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }
 
    void Destroy(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

形参按值接收,进入函数时已经是一份副本,交换 _root 之后副本随作用域结束自动析构,原对象拿到对方的数据。这种写法的好处是自赋值和异常都不会留下半个对象;代价是多一次深拷贝。

词频统计把上面这些东西拼起来:

int main()
{
    std::string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
                         "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    BSTree<std::string, int> countTree;
 
    for (const auto& str : arr)
    {
        BSTNode<std::string, int>* ret = countTree.Find(str);
        if (ret == nullptr)
        {
            countTree.Insert(str, 1);
        }
        else
        {
            ret->_value++;
        }
    }
 
    countTree.InOrder();      // 按字典序输出每个单词和次数
    return 0;
}

最坏 O(N) 之后

二叉搜索树的价值在于"插入只改一条指针""中序天然有序""按 key 查找",它的短板也全在树高:同一个 key 集合,插入顺序能把树高从 log₂N 推到 N。标准库不能要求用户按随机顺序插入,只能把树高做成不依赖插入顺序的保证。

AVL 树在每个结点上记一个平衡因子,把左右子树高度差压到不超过 1,树高稳定在 1.44 log₂(N+2) 以内;红黑树用颜色规则放宽到"最长路径不超过最短路径的两倍",换来更少的旋转。这两棵树的结点结构、插入挂接、替换删除、后序释放与本篇这棵裸 BST 完全一致,区别只在插入之后多出的那一段维护逻辑。