考研笔记

二叉排序树（BST）

构造一棵二叉排序树的目的并不是排序，而是提高查找、插入和删除关键字的速度。

这是教材开篇的第一句，值得原样记住。它回答了「既然中序遍历能得到有序序列，为什么不直接排好序放数组里」——因为数组插一个元素要移动 个位置，而 BST 只要改指针。 折半查找 是静态查找表的最优解，BST 是动态查找表的对应物，两者的分工在 7.1 那张静态 / 动态表里已经画好了。

BST 是本章后面三节的共同祖先：平衡二叉树 是「加了平衡因子约束的 BST」，红黑树 是「加了红黑性质的 BST」，B 树 是「多路化的 BST」。它们的插入删除全都以 BST 的插入删除为第一步，再补一段调整。

机制

定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

  1. 若左子树非空，则左子树上所有结点的值均小于根结点的值
  2. 若右子树非空，则右子树上所有结点的值均大于根结点的值
  3. 左、右子树也分别是一棵二叉排序树

「所有结点」这三个字是定义的全部重量。 只保证「左孩子 < 根 < 右孩子」的树不是 BST——这是最经典的判断题陷阱。

由定义得 左子树结点值 < 根结点值 < 右子树结点值，因此对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

边界辨析：

中序遍历有序是 BST 的充要条件，可以拿来当判据用： 给一棵二叉树，中序走一遍，序列递增则是 BST，否则不是。 但反过来不能推形态——中序序列相同的二叉树有很多棵（5.3.1）， 所以「已知中序序列」不能唯一确定一棵 BST，还要知道插入顺序。

查找

从根结点开始，沿某个分支逐层向下比较。非递归算法：

BSTNode *BST_Search(BiTree T, ElemType key){
    while(T != NULL && key != T->data){    //若树空或等于根结点值，则结束循环
        if(key < T->data) T = T->lchild;   //小于，则在左子树上查找
        else              T = T->rchild;   //大于，则在右子树上查找
    }
    return T;
}

非递归版本的空间复杂度是 ，递归版本是 。教材的措辞是「递归算法比较简单，但执行效率较低」。

插入

BST 作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

  • 若原树为空，则直接插入
  • 若关键字 小于根结点值，则插入到左子树；大于则插入到右子树
  • 新插入的结点一定是一个叶结点，且是查找失败时查找路径上访问的最后一个结点的左孩子或右孩子
int BST_Insert(BiTree &T, KeyType k){
    if(T == NULL){                        //原树为空，新插入的记录为根结点
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;                         //返回 1，插入成功
    }
    else if(k == T->data)                 //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k < T->data)                  //插入 T 的左子树
        return BST_Insert(T->lchild, k);
    else                                  //插入 T 的右子树
        return BST_Insert(T->rchild, k);
}

BiTree &T 是引用参数——因为要在树为空时修改调用者的指针本身。这是 408 算法设计题里最容易写漏的一个符号。

相同关键字插入失败返回 0，不是插入到某一侧。教材构造例子用的序列是 ，含重复的 45 和 24，最终树里只有 4 个结点——重复的两个都被拒绝了。

构造

从一棵空树出发，依次输入元素，将它们插入 BST 中的合适位置。

void Creat_BST(BiTree &T, KeyType str[], int n){
    T = NULL;                    //初始时 T 为空树
    int i = 0;
    while(i < n){                //依次将每个关键字插入二叉排序树
        BST_Insert(T, str[i]);
        i++;
    }
}

同一组关键字，插入顺序不同会生成不同的 BST。 这是 BST 与折半查找判定树最本质的区别，也是它性能不稳定的根源（见下面「查找效率」）。

删除：三种情况

删除时不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从链表上摘下，重新链接，同时确保二叉排序树的性质不会丢失。按 3 种情况处理：

情况处理
① 被删结点 是叶结点直接删除，不会破坏 BST 性质
② 只有一棵左子树或右子树让 的子树成为 父结点的子树，替代 的位置
③ 有左、右两棵子树令 的直接后继（或直接前驱）替代 ，然后从 BST 中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况
flowchart TD
    Z{"被删结点 z"} --> L["① 叶结点<br/>直接删"]
    Z --> O["② 只有一棵子树<br/>子树上移顶替"]
    Z --> T["③ 左右子树都有"]
    T --> S["找中序直接后继<br/>（右子树中最小的结点）"]
    S --> R["用它的值替换 z"]
    R --> D["转化为删除那个后继<br/>→ 回到 ① 或 ②"]

    classDef easy fill:#c8e6c9,stroke:#1b5e20
    classDef hard fill:#ffcdd2,stroke:#b71c1c
    classDef mid fill:#e3f2fd,stroke:#1565c0
    class L,O easy
    class T,S hard
    class R,D mid

情况 ③ 为什么一定能化归：直接后继是右子树中最小的结点，它必然没有左孩子，所以至多只有一棵子树——正好是情况 ① 或 ②。

边界辨析：

「直接后继」和「直接前驱」都可以，教材两个都列了。 选后继就是右子树的最左结点， 选前驱就是左子树的最右结点。题目不指定时两个答案都对，但同一道题里要前后一致。 阅卷时若中途换了口径，得到的树会自相矛盾。

查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

  • 若左、右子树的高度之差的绝对值不超过 1（即平衡二叉树，下一节），平均查找长度和 成正比
  • 最坏情况下，即构造 BST 的输入序列是有序的，则会形成一个只有右孩子的单支树，树的高度为 ，此时

最坏情况的 与 顺序查找 完全相同——单支树退化成了链表。

教材图 7.8 用同一组关键字给出了两棵 BST：

与折半查找的四点对比

折半查找二叉排序树
平均时间性能，差不多
形态是否唯一判定树唯一不唯一，取决于插入顺序
维护有序性的代价插入删除要移动元素，无须移动结点，只改指针，平均
适用有序表是静态查找表时，用顺序表 + 折半有序表是动态查找表时，用 BST 作为逻辑结构

这张表就是教材 7.3.1 末尾那一整段的压缩，也是 7.2 与 7.3 之间的接缝。

手算模板

构造 BST：逐个插入，每个新元素从根开始按大小走到空位挂上去。重复关键字直接丢弃。

删除结点 ：

  1. 数 的孩子个数 → 落到 ①/②/③。
  2. 若为 ③：走 的右子树，一路向左到底，得到直接后继 。
  3. 把 的值写进 ，然后在原位置删除 （ 无左孩子，必为 ① 或 ②）。

算 ：与 判定树 完全一样——成功数结点所在层、除以 ；失败补 个方形结点、数到父结点、除以 。

边界

说法判断说明
「只要左孩子 < 根 < 右孩子就是 BST」❌要求整棵左子树都小于根，不只是左孩子
「BST 的中序遍历是递增序列」✅且是充要判据
「已知中序序列可唯一确定一棵 BST」❌中序序列就是排好序的那一列，任何 BST 都给出同一个中序序列
「BST 的目的是排序」❌是提高查找、插入、删除的速度（教材首句）
「插入相同关键字会插到右子树」❌插入失败，返回 0
「新插入的结点可能是内部结点」❌一定是叶结点
「删除有两个孩子的结点必须用后继」❌后继或前驱都可以
「删除再插入同一个结点，树不变」❌教材 2013 命题追踪的思考题：一般会变。删除时用后继顶替改变了形态，再插入只会挂到叶子上
「BST 查找的时间复杂度是 」⚠️平均是；最坏退化成单支树，为 ，
「BST 是平衡的」❌不保证。要平衡得靠 AVL 或 红黑树

口径差异：

算法竞赛里用 BST 一般直接上 std::map / set（底层是红黑树），从不手写朴素 BST， 因为朴素 BST 会被有序数据卡成 。所以「退化成单支树」在算竞里是要避开的坑， 在 408 里却是必考的结论——题目专门爱问「关键字有序输入时 BST 的 是多少」，答案 。 算竞的直觉是「别用它」，考试的要求是「算清楚它有多差」。

对照速查

操作平均最坏
查找
插入
删除
最坏 ASL—
删除情况判据动作
①无孩子直接删
②一个孩子孩子顶替
③两个孩子后继（或前驱）顶替，转 ① 或 ②

考点

  • 定义里的「所有结点」，以及中序遍历有序这个充要判据。
  • 构造过程（2020 命题追踪），重复关键字被丢弃。
  • 删除的三种情况，尤其 ③ 的化归理由。
  • 删除后再插入，树是否与原来相同（2013 命题追踪的思考题）。
  • 最坏退化为单支树，。
  • 与折半查找的四点对比，尤其「判定树唯一 vs BST 不唯一」。
  • BiTree &T 引用参数——算法设计题的高频扣分点。

链接

反向链接