二叉搜索树 - Shaw 的小屋

p27（19 分钟）、p28（C/C++ 实现，18 分钟）

为什么需要 BST#

先比较三种存法#

数组：

1
查找：从索引 0 扫到末尾，最坏看全部元素  →  O(N)
2
插入（未满）：递增末尾标记、填值         →  O(1)
3
插入（已满）：新建两倍大小新数组、复制   →  O(N)
4
删除：右侧所有记录左移，最坏移动 N−1 个  →  O(N)

链表：

1
查找：最坏遍历整个链表        →  O(N)
2
插入：头部插入 O(1)；尾部插入也是 O(1)
3
删除：先得遍历查找记录        →  O(N)

数量级直观感受#

1
假设机器每秒能进行 10^6 次比较 → 一次比较代价 10^-6 秒
2
现实数据常有 1 亿甚至数十亿条记录
3
N = 1 亿 → 一次搜索需要 100 秒

一次搜索花 100 秒显然不合理，而搜索往往是频繁操作。

有序数组 + 二分查找#

要求：数据结构是数组，且记录必须排序（不同数据类型比较逻辑不同，字符串按字典序）。

1
查找  →  O(log N)，这是所能达到的最佳运行时间
2
插入  →  先二分找位置（O(log N)），但接着要右移一位 → 整体仍是 O(N)
3
删除  →  同理 O(N)

具体数字：N = 2^31 时只需 31 次比较 → 31 微秒（因为 log₂2^31 = 31）。

结论：搜索问题解决了，但插入/删除仍是 O(N)。

BST 的卖点#

1
三种操作（查找/插入/删除）平均都能做到 O(log N)
2
最坏情况 O(N)
3
通过保持平衡可以避免最坏情况

BST 的定义#

BST 是一种特殊二叉树：对每个节点，左子树中所有节点的值都更小，右子树中所有节点的值都更大。

精确一点的说法是：

1
左子树所有节点值「小于或等于」该节点值
2
右子树所有节点值「大于」该节点值

也就是「左 ≤ 根 < 右」。写成严格的「左 < 根 < 右」口径就不一致了。

而且这个性质对所有节点都成立，不只是根。递归结构：左右子树也必须是 BST。

验证示例#

1
        15
2
       /  \
3
     10    20
4
    /  \   /  \
5
   8   12 17  25

逐节点验证：

1
根 15：左子树 8、12 全 < 15 ✓；右子树 17、20、25 全 > 15 ✓
2
节点 10：左 8 小、右 12 大 ✓
3
节点 20：✓
4
叶节点无需操心

反例#

把 12 改成 16：

1
对节点 10 仍成立（16 在其右侧）
2
但对根节点 15 不成立（左子树中出现了比 15 大的 16）
3
→ 整棵树不再是 BST

所以 BST 性质要全局检查到根，只看局部父子会误判。

为什么 BST 查找能是 O(log N)#

二分查找类比#

1
把整个列表定义为搜索空间（start/end 两指针）
2
与中间元素比较；小则搜左半，大则搜右半，相等则命中
3
每次把搜索空间减半

步数推导：

1
N → N/2 → N/4 → N/8 …
2
若走 K 步，则 N/2^K = 1  →  2^K = N  →  K = log₂N

BST 查找完全类似#

从根开始，与根比较 → 相等则完成；较小去左子树；较大去右子树。每一步舍弃其中一个子树。

演示查找 12：

1
根 15 → 12 < 15 走左（搜索空间缩到 {10, 8, 12}）
2
→ 与 10 比，12 > 10 走右
3
→ 只剩一个节点，匹配命中

平衡（对所有节点左右子树高度差 ≤ 1）时：N → N/2 → N/4 … → 到只剩 1 个节点为止，故 O(log N)。

最坏情况（退化）#

用同样的数据可以排出不平衡的 BST：任意节点都没有右子树（只有左链），这跟链表一样差。

此时搜索空间每步只减少 1：N → N−1 → N−2 → … → 1，总共 N 步 → O(N)。

结论：

1
BST 平均 O(log N)，最坏 O(N)
2
总是试图通过保持平衡来避免最坏情况

同一组记录可有多种合法 BST 排列；完美二叉树是最佳排列（每一步都恰好舍弃 N/2 个节点）。

插入#

1
先找可插入位置  →  O(log N)

演示插入 19：

1
根 15 → 19 更大向右 → 到 20
2
→ 19 更小且左子树非空向左 → 到 17
3
→ 19 比 17 大，17 无右子节点
4
→ 新建值为 19 的节点作为 17 的右子节点

规则：

1
若待插入值较小或相等 → 无左子节点则作为左子节点插入，否则向左走
2
若值较大             → 无右子节点则作为右子节点插入，否则向右行进

成本 = 搜索的成本。因为用指针/引用，不需要像数组那样移位，创建一个链接是恒定时间。

删除：首先也得查找那个节点（O(log N)），删除节点仅意味着调整某些链接，所以平均与搜索同阶。

p27-28 没给删除的具体实现（没讲中序后继/前驱），只说插入和删除会使 BST 变得不平衡，需要恢复平衡。

C/C++ 实现#

节点定义与内存位置#

1
struct btNode {
2
    int data;
3
    struct btNode *left;
4
    struct btNode *right;
5
};

这个节点定义与双向链表节点非常相似（都是两个链接），但双向链表是线性排列，这个定义是针对二叉树的。

所有节点都在应用程序内存的「动态内存区/堆区」，用 C 的 malloc 或 C++ 的 new 创建。

堆中创建的对象不能有名字或标识符，必须通过指针访问。

树的标识#

与链表「始终保存头节点地址」对应：树始终保留的是根节点的地址。

1
struct btNode *rootPtr;      /* 始终存储根节点地址；初始 NULL 表示空树 */

很多人喜欢把这个指针直接叫 root，但它是「指向根的指针」，不是根本身。

C 里不能直接写 btNode* rootPtr，必须写 struct btNode* ...。

insert 的关键设计问题#

问题：如果 root 是 insert 的局部变量，函数内 root = ... 改不了 main 里的 root（作用域只在函数内）。

三种解法：

方案	做法
① 让 insert 返回新根地址	返回类型从 void 改成 `node*`，main 里写 `root = insert(root, data)`。这里选的是这种
② 传根的地址	参数类型变成 `node*`（指针的指针），函数内用 `` 解引用设置 main 中 root 的值，返回类型可为 void
③ 把 root 声明为全局变量	必须在所有函数之外声明，所有函数都能访问，不必传地址

方案 ② 的毛病是「指针的指针」用起来有点棘手。

getNewNode#

1
struct btNode *getNewNode(int data) {
2
    struct btNode *newNode = new btNode;   /* 或 malloc，在堆中创建 */
3
    newNode->data  = data;
4
    newNode->left  = NULL;
5
    newNode->right = NULL;
6
    return newNode;
7
}

insert 的完整逻辑（递归）#

1
struct btNode *insert(struct btNode *root, int data) {
2
    if (root == NULL) {                    /* 树/子树为空（首次插入） */
3
        root = getNewNode(data);
4
    } else if (data <= root->data) {
5
        root->left  = insert(root->left,  data);    /* 递归插入左子树 */
6
    } else {                               /* data > root->data */
7
        root->right = insert(root->right, data);    /* 递归插入右子树 */
8
    }
9
    return root;                           /* 返回路径统一提取到条件之后 */
10
}

插入左子树后，左子树的根可能改变，所以必须 root->left = insert(...) 把返回值接回来。

这种 return root 的写法适用于所有情况，所以把它提到条件语句之后。

树的问题几乎一直要用递归，因为它本身就是自相似的。

逐次插入的内存地址演示#

1
插入 15：树空 → getNewNode 返回地址 200 → 设为根       main 的 root = 200
2
插入 10：10 < 15 → 递归 insert(200->left = 0, 10)
3
        左子树根地址 0 → 树空 → getNewNode 返回 150    200->left = 150
4
插入 20：20 > 15 → else → getNewNode 返回 300          200->right = 300
5
插入 25：25 > 15 向右 → 25 > 20 向右 → 20->right 为空
6
        → getNewNode 返回 500                          300->right = 500

第一次 insert 调用会等待下面递归调用完成并返回，才继续执行 root->left = ... 这一行。

search#

1
int search(struct btNode *root, int data) {
2
    if (root == NULL) return 0;                  /* false */
3
    if (root->data == data) return 1;            /* true */
4
    if (data < root->data) return search(root->left,  data);
5
    else                   return search(root->right, data);
6
}

测试：输入 88 → 找到了；输入 22 → 22 未找到。

insert 完全可以不用递归写（用临时指针 + 循环），但递归处理树时非常直观，把递归理解透很值。

BST 三种操作汇总#

操作	平均	最坏	说明
查找	O(log N)	O(N)	每步舍弃一个子树
插入	O(log N)	O(N)	成本 = 搜索成本 + 创建链接（恒定时间）
删除	O(log N)	O(N)	也要先查找，然后调整链接

坑#

BST 定义是「左 ≤ 根 < 右」，等于归到左侧；而且性质要全局检查到根，只看局部父子会误判（12 改成 16 的反例）。
插入时必须接住返回值 root->left = insert(root->left, data)，且 return root 要放在所有分支之后，否则链接会丢。
root 是局部变量时改不了 main 里的，得用「返回新根 / 双重指针 / 全局变量」之一；「指向根的指针」不是根本身。
BST 最坏是 O(N)（退化成链表），只能靠平衡避免。
有序数组查找快但插入删除慢，链表插入快但查找慢，BST 三者平均都快。