企业官网建设流程全解析

前言

普通二叉树更多描述的是一种“节点最多拥有两个孩子”的组织结构，但它本身并没有规定节点之间应该按照什么规则排列。

**二叉搜索树（Binary Search Tree，BST）**则在二叉树的基础上增加了一套明确的排序规则，使得树结构同时具备：

动态存储 + 快速查找 + 有序遍历

这也是二叉搜索树非常重要的原因。

它一方面可以帮助我们理解：

查找 插入 删除 树形递归

这些基本操作；

另一方面又是后续学习：

AVL树 红黑树 set map

等结构的重要基础。

这篇文章将从 BST 的基本性质开始，逐步实现 Key 型和 Key/Value 型二叉搜索树，并分析删除操作、实际应用以及普通 BST 为什么还需要进一步演化成平衡搜索树。

一、二叉搜索树

二叉搜索树首先是一棵二叉树，但它对节点之间的大小关系提出了额外要求。

对于任意一个节点，可以理解为：

左子树中的关键码 < 当前节点关键码 < 右子树中的关键码

并且：

当前节点的左子树和右子树，本身也必须继续满足二叉搜索树的规则。

例如：

8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

以根节点8为例：

左边： 1、3、4、6、7 都小于 8 右边： 10、13、14 都大于 8

再看节点3：

1 < 3 4、6、7 > 3

所以不仅根节点满足规则，每一棵子树也要继续满足相同规则。

这里还有一个需要提前说明的问题：

BST 是否允许重复关键码，并没有唯一答案，要由具体设计决定。

例如我们自己实现一种类似set的结构，可以规定：

key == 当前节点 ↓ 插入失败

也就是整棵树中不允许出现两个相同的 Key。

如果设计的是允许重复数据的结构，则必须规定统一策略，例如：

相同元素统一放左边

或者：

相同元素统一放右边

关键不是必须放哪边，而是：

重复元素的处理规则必须始终一致，否则搜索树原本的顺序关系会变得混乱。

这篇实现采用不允许重复 Key的方案。

中序遍历天然有序

二叉搜索树最漂亮的性质之一就是：

按照“左子树 → 根节点 → 右子树”进行中序遍历，可以直接得到升序序列。

还是前面的树：

8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

进行中序遍历：

左 → 根 → 右

最终得到：

1 3 4 6 7 8 10 13 14

正好是升序。

如果把遍历顺序反过来：

右子树 → 根节点 → 左子树

则能够得到降序：

14 13 10 8 7 6 4 3 1

这也是 BST 和普通二叉树一个非常本质的区别：

普通二叉树的中序遍历只是访问顺序，而 BST 的中序遍历同时具有排序意义。

二、性能分析

二叉搜索树的插入、删除、查找效率，本质上都取决于一个东西：

树的高度h。

因为无论查找还是插入，本质上都是从根节点开始不断：

比较 ↓ 向左 或者 向右

直到找到目标或者走到空节点。

所以更准确地说，BST 的这些核心操作复杂度通常是：

O(h)

真正决定效率的是：

树到底有多高？

假设一棵 BST 比较均衡：

8 / \ 4 12 / \ / \ 2 6 10 14

每向下一层，搜索范围都会明显缩小。

如果共有N个节点，树高通常在：

O(logN)

这个量级。

因此查找、插入、删除也可以达到：

O(logN)

但如果插入顺序变成：

1 2 3 4 5

BST 会形成：

1 \ 2 \ 3 \ 4 \ 5

此时已经非常接近单链表。

树高：

h ≈ N

所以查找一个元素可能需要：

1 → 2 → 3 → 4 → 5

一路查到底。

时间复杂度也就退化成：

O(N)

因此普通 BST 的性能不能简单写成：

查找一定 O(logN)

更加准确的是：

查找 / 插入 / 删除 = O(h) 树较平衡： h = O(logN) 极端退化： h = O(N)

这个结论后面会直接引出 AVL 树和红黑树。

BST 和二分查找有什么区别？

BST 和二分查找都利用了：

有序 + 不断缩小搜索范围

所以容易让人觉得二者差不多。

但它们适合的场景并不完全相同。

例如有一个有序数组：

1 3 4 6 7 8 10 13 14

使用二分查找寻找7：

不断取中间位置 ↓ 一半一半排除

查找效率可以达到：

O(logN)

非常优秀。

问题出现在：

动态插入 动态删除

例如现在向数组中插入：

5

为了继续保持有序：

1 3 4 5 6 7 8 10 13 14

后面的很多元素都可能需要移动。

而 BST 插入节点时，通常只需要：

找到正确位置 + 修改父节点的一条指针

因此 BST 更适合：

数据持续变化 频繁插入 频繁删除 同时还要求快速查找

的场景。

可以简单理解为：

有序数组 + 二分查找 ↓ 更适合数据相对稳定 二叉搜索树 ↓ 更适合动态有序数据

三、Key 型 BST

先实现最基本的一种二叉搜索树：

每个节点只保存一个 Key。

它比较接近：

set

这种“主要关心某个关键码是否存在”的结构。

节点设计

BST 采用链式结构，每一个节点保存：

关键码 左孩子指针 右孩子指针

代码：

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

可以把一个节点理解成：

┌──────────────┐ │ key │ ├──────┬───────┤ │ left │ right │ └──┬───┴───┬───┘ ↓ ↓ 左子树 右子树

树本身只需要保存：

Node* _root;

也就是整棵树的根节点。

类基本框架

template<class K> class BSTree { using Node = BSTNode<K>; public: BSTree() : _root(nullptr) {} ~BSTree() { Destroy(_root); _root = nullptr; } bool Insert(const K& key); bool Find(const K& key) const; bool Erase(const K& key); void InOrder() const { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) const { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; } private: Node* _root; };

这里有一个细节非常值得注意：

销毁树时使用的是：

左子树 ↓ 右子树 ↓ 当前节点

也就是：

后序遍历。

为什么不能一上来就：

delete root;

因为删除root之后：

root->_left root->_right

就已经不能再安全访问了。

所以释放树必须先处理孩子：

先把左右子树释放干净 ↓ 最后释放当前节点

这就是后序遍历特别适合树形资源释放的原因。

插入

BST 的插入逻辑可以概括成：

待插入 key < 当前节点 ↓ 往左走 待插入 key > 当前节点 ↓ 往右走 相等 ↓ 拒绝重复插入

例如向：

8 / \ 3 10

中插入6：

第一步：

6 < 8 ↓ 往左

到3：

6 > 3 ↓ 往右

发现右孩子为空：

8 / \ 3 10 \ 6

于是将新节点挂在那里。

代码：

template<class K> bool BSTree<K>::Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur != nullptr) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; } } Node* newNode = new Node(key); if (key < parent->_key) { parent->_left = newNode; } else { parent->_right = newNode; } return true; }

这里为什么要同时维护：

Node* parent; Node* cur;

这是插入代码中很关键的一点。

cur的任务是：

一路向下寻找空位置

最终一定会变成：

nullptr

但找到空位置以后，我们还需要知道：

新节点到底应该挂到谁下面？

所以需要提前保存：

parent

整个过程实际上是：

parent ↓ 当前节点的父节点 cur ↓ 负责继续向下寻找

当：

cur == nullptr

时：

parent

刚好停在最后一个有效节点。

于是才能决定：

parent->_left = newNode;

还是：

parent->_right = newNode;

这也是 BST 插入代码里parent存在的真正原因。

查找

查找的逻辑和插入非常相似，只是不需要创建节点。

例如查找：

7

当前树：

8 / \ 3 10 / \ 1 6 \ 7

过程：

7 < 8 ↓ 去左子树 7 > 3 ↓ 去右子树 7 > 6 ↓ 继续右 7 == 7 ↓ 找到

代码：

template<class K> bool BSTree<K>::Find(const K& key) const { Node* cur = _root; while (cur != nullptr) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } return false; }

和插入相比，查找不需要：

parent

因为我们不需要在某个位置挂新节点。

只要找到目标：

return true;

一路走到：

nullptr

仍然没有找到：

return false;

即可。

如果树允许重复 Key，查找语义还会进一步复杂，例如到底返回：

任意一个相同节点

还是：

中序顺序中的第一个

必须由数据结构本身明确规定。

四、删除操作

BST 中最值得认真理解的操作不是插入，也不是查找，而是：

删除。

因为删除之后不能只是把节点从内存中释放掉，还必须保证剩余节点继续满足：

左 < 根 < 右

的搜索树性质。

假设待删除节点记为：

cur

按照孩子情况，可以分成四种表面场景：

1. 没有左孩子，也没有右孩子 2. 没有左孩子，但有右孩子 3. 有左孩子，但没有右孩子 4. 左右孩子都存在

其中叶子节点其实可以合并进：

只有一侧子树

的处理逻辑。

因此代码层面通常最终归纳成三类：

左为空 右为空 左右都不为空

左子树为空

例如：

8 \ 10 \ 14

删除10。

10没有左子树：

10 \ 14

所以可以直接让10的父节点8指向：

10 的右子树

变成：

8 \ 14

本质上就是：

父节点 ↓ 跳过待删除节点 ↓ 直接连接其唯一子树

如果待删除的节点本身就是根节点，则：

_root = cur->_right;

即可。

右子树为空

这个逻辑完全对称。

例如：

8 / 3 / 1

删除3：

8 / 1

本质上：

父节点 ↓ 直接连接 cur 的左子树

左右子树都存在

这是删除中真正的难点。

假设要删除：

8 / \ 3 10 / \ \ 1 6 14

直接把8删掉是不行的。

因为：

左边整棵子树 + 右边整棵子树

接下来应该挂到哪里？

这时候通常采用：

替换法。

可以从右子树中找到：

最小节点

作为当前节点的替代者。

或者从左子树找到：

最大节点

也可以。

为什么右子树最小节点适合替换？

例如：

8 / \ 3 12 / \ 10 14

要删除8。

右子树最小值就是：

10

将：

8 → 10

以后：

10 / \ 3 12 \ 14

仍然满足：

左边 < 10 < 右边

因为这个节点本来就是：

右子树中最小的那个元素。

同理：

左子树最大节点

也可以作为替代者。

完整实现：

template<class K> bool BSTree<K>::Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; // 先找到待删除节点 while (cur != nullptr) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { break; } } if (cur == nullptr) { return false; } // 情况1：左子树为空 if (cur->_left == nullptr) { if (parent == nullptr) { _root = cur->_right; } else if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; return true; } // 情况2：右子树为空 if (cur->_right == nullptr) { if (parent == nullptr) { _root = cur->_left; } else if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur; return true; } // 情况3：左右子树都存在 Node* successorParent = cur; Node* successor = cur->_right; // 找右子树最小节点 while (successor->_left != nullptr) { successorParent = successor; successor = successor->_left; } // 用后继节点的key覆盖待删除节点 cur->_key = successor->_key; // 删除原来的后继节点 if (successorParent->_left == successor) { successorParent->_left = successor->_right; } else { // successor 就是 cur->_right successorParent->_right = successor->_right; } delete successor; return true; }

这段删除代码最值得理解的不是每一行怎么背，而是三个思想：

没有左孩子 ↓ 右孩子顶上去 没有右孩子 ↓ 左孩子顶上去 左右孩子都有 ↓ 找前驱/后继替换 ↓ 再删除替代节点

只要把这三条逻辑真正搞懂，删除代码就不需要死记。

测试 BST

可以构造：

int values[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

依次插入：

BSTree<int> bst; for (int value : values) { bst.Insert(value); }

中序遍历：

bst.InOrder();

应该得到：

1 3 4 6 7 8 10 13 14

再测试：

cout << bst.Find(6) << endl; cout << bst.Find(9) << endl;

分别得到：

true false

删除：

bst.Erase(1); // 叶子节点 bst.Erase(14); // 单孩子 bst.Erase(3); // 双孩子

每删除一次再进行中序遍历，如果结果始终保持有序，就说明：

删除以后 BST 的基本性质仍然成立。

五、Key/Value 型 BST

前面的 BST 只保存：

Key

它适合解决：

某个数据存在吗？

例如：

这个车牌是否登记？ 这个单词是否在词库？ 这个ID是否存在？

但很多实际问题需要保存的是：

Key + 与Key对应的数据

例如：

英文单词 → 中文释义 车牌号 → 入场时间 商品编号 → 商品信息 单词 → 出现次数

这时候就需要：

Key/Value 型二叉搜索树。

节点结构

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) {} };

和 Key 型相比，只是多出：

V _value;

但搜索树的排序依据仍然是：

_key

而不是：

_value

也就是说：

Key 负责定位 Value 负责保存与 Key 关联的数据

为什么 Find 要返回节点指针？

Key 型只关心：

存在 还是 不存在

所以返回：

bool

已经够用了。

但是 Key/Value 型通常还希望：

找到 Key ↓ 读取 Value ↓ 甚至修改 Value

所以：

bool Find(const K& key);

已经不够方便。

更适合：

Node* Find(const K& key);

例如：

template<class K, class V> BSTNode<K, V>* BSTree<K, V>::Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return cur; } } return nullptr; }

于是：

auto ret = tree.Find("apple"); if (ret != nullptr) { ret->_value++; }

就可以直接修改 Value。

这也是：

Key型 Find

和：

Key/Value型 Find

设计上的重要区别。

插入

插入时需要同时提供：

key value

例如：

bool Insert(const K& key, const V& value);

核心搜索逻辑仍然只比较 Key：

template<class K, class V> bool BSTree<K, V>::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 != nullptr) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { return false; } } Node* newNode = new Node(key, value); if (key < parent->_key) { parent->_left = newNode; } else { parent->_right = newNode; } return true; }

深拷贝

树中保存的是大量：

new Node(...)

动态申请出来的节点。

因此如果直接依赖编译器生成的浅拷贝：

BSTree<K, V> t2 = t1;

两个对象可能只是复制：

_root

这个指针。

结果就会变成：

t1._root ──┐ ↓ 同一棵树 ↑ t2._root ──┘

最后两个对象析构：

第一次 delete ↓ 节点释放 第二次 delete ↓ 重复释放

显然非常危险。

所以需要：

深拷贝整棵树。

可以递归实现：

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; }

这个过程非常符合树的递归结构：

复制根 ↓ 递归复制左子树 ↓ 递归复制右子树

于是拷贝构造：

BSTree(const BSTree& other) { _root = Copy(other._root); }

赋值可以使用 copy-and-swap：

BSTree& operator=(BSTree other) { std::swap(_root, other._root); return *this; }

这样：

other

先通过拷贝构造得到一棵独立的新树，再交换根指针。

函数结束时：

other

析构并自动释放原来属于当前对象的旧树。

这种写法比手动：

先释放自己 再复制 再处理自赋值

更加简洁，也具有较好的异常安全性。

Key/Value 删除时的一个细节

Key/Value 型删除的结构调整和 Key 型一样。

但是如果双孩子节点使用后继节点替换：

只复制 Key

是不够的。

因为一个节点表示的是：

Key ↔ Value

完整映射关系。

所以应该同步：

cur->_key = successor->_key; cur->_value = successor->_value;

否则就可能出现：

新的 Key + 旧的 Value

错配。

这是实现 Key/Value BST 时非常容易忽略的细节。

六、典型应用

BST 的核心能力可以概括成：

动态 + 有序 + 按 Key 查找

而 Key 型和 Key/Value 型解决的问题并不完全一样。

Key 型：判断“有没有”

例如小区车库系统。

我们只关心：

车牌是否在白名单？

可以把所有允许进入的车牌作为 Key：

赣A12345 赣A88888 赣A66666

插入 BST。

车辆到达时：

扫描车牌 ↓ Find(车牌) ↓ 存在 → 放行 不存在 → 拒绝

如果业主车辆发生变化：

Insert() Erase()

就可以动态更新。

另一个典型场景是：

拼写检查。

将合法词库中的单词作为 Key：

apple binary computer search tree

文章中每出现一个单词，就：

dict.Find(word);

如果不存在：

标记为可能的拼写错误

同时词库还可以动态：

加入新词 删除废弃词

Key/Value：建立映射

最直观的就是：

中英词典。

例如：

BSTree<string, string> dict; dict.Insert("apple", "苹果"); dict.Insert("tree", "树"); dict.Insert("search", "查找"); dict.Insert("binary", "二进制");

查找：

auto ret = dict.Find("search"); if (ret != nullptr) { cout << ret->_value << endl; }

得到：

查找

如果需要修改释义：

ret->_value = "搜索 / 查找";

即可。

而中序遍历又会天然按照：

Key

的大小顺序输出。

单词计数

再来看一个很典型的统计问题：

string words[] = { "apple", "banana", "apple", "orange", "apple", "banana" };

希望得到：

apple → 3 banana → 2 orange → 1

可以建立：

BSTree<string, int> countTree;

遍历每个单词：

for (const auto& word : words) { auto ret = countTree.Find(word); if (ret == nullptr) { countTree.Insert(word, 1); } else { ++ret->_value; } }

逻辑非常自然：

第一次遇见 ↓ Insert(word, 1) 以前出现过 ↓ Find ↓ value++

最后进行中序遍历：

既得到统计结果 + 又天然按照单词顺序排列

Key/Value 结构还适合停车场计时收费。

可以定义：

Key = 车牌号 Value = 入场时间

车辆入场：

Insert(车牌, 当前时间)

车辆离场：

Find(车牌) ↓ 取得入场时间 ↓ 计算停车时长 ↓ 计算费用 ↓ Erase(车牌)

从这个例子也可以看出：

Key/Value 搜索树不只是“查找某个东西存不存在”，还可以维护某个 Key 当前对应的状态。

七、BST 的缺陷

到这里 BST 看起来似乎已经非常优秀：

查找快 插入快 删除快 还能保持有序

但它有一个致命问题：

树形完全取决于数据插入顺序。

例如：

4 2 6 1 3 5 7

得到：

4 / \ 2 6 / \ / \ 1 3 5 7

非常漂亮。

但如果变成：

1 2 3 4 5 6 7

得到：

1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7

搜索树直接退化成链表。

此时原本期待的：

O(logN)

就会退化到：

O(N)

所以普通 BST 最大的问题并不是：

查找算法不够聪明。

而是：

它没有能力主动控制自己的高度。

这也自然引出了：

平衡二叉搜索树

AVL 树

AVL 树是一种对平衡要求比较严格的搜索树。

它要求任意节点：

左子树高度 和 右子树高度

不能相差太大，典型约束是平衡因子绝对值不超过1。

当插入或删除破坏平衡后，会通过：

旋转

重新调整结构。

优势是：

树高控制严格 查找性能稳定

代价则是：

插入删除时 可能需要较频繁调整

红黑树

红黑树也是平衡搜索树，但它不像 AVL 那样追求严格高度平衡，而是通过：

节点颜色 + 一组颜色规则 + 旋转与变色

保证树不会严重失衡。

因此它追求的是：

查询、插入和删除之间更加均衡的综合性能。

这也是工程实现中经常采用红黑树的重要原因。

和 STL 的关系

我们前面自己实现的：

Key 型 BST

可以帮助理解：

set / multiset

这一类只围绕 Key 组织数据的容器。

而：

Key/Value 型 BST

则和：

map / multimap

的设计思想非常接近。

其中：

set map

要求 Key 唯一。

而：

multiset multimap

允许出现重复 Key。

这些有序关联容器的迭代顺序也是：

按 Key 有序

从学习思路上看，可以把它们串成：

普通 BST ↓ 理解有序搜索树 ↓ 平衡搜索树 ↓ 红黑树 ↓ set / map 等有序关联容器

需要稍微严谨一点的是：

C++ 标准规定的是这些容器的行为、复杂度和有序语义，并没有强制所有标准库必须使用某一种具体树结构；主流实现通常采用红黑树一类的平衡搜索树。

这样理解会比单纯记住：

map = 红黑树

更加准确。

总结

二叉搜索树真正重要的地方，并不是学会写几个：

if (key < cur->_key)

而是理解它是如何利用：

“有序”

改变普通二叉树的。

整条逻辑可以串成：

普通二叉树 ↓ 增加大小关系约束 ↓ 二叉搜索树 BST ↓ 左 < 根 < 右 ↓ 中序遍历天然有序 ↓ 按大小关系缩小搜索范围 ↓ Insert / Find / Erase ↓ Key 型 解决“是否存在” ↓ Key/Value 型 解决“映射关系” ↓ 普通 BST 可能退化 ↓ AVL / 红黑树 ↓ set / map 等有序关联容器

如果只记三个最核心的点，我觉得应该是：

第一： 左子树 < 根 < 右子树 第二： 中序遍历天然有序 第三： 增删查复杂度本质取决于树高 h

尤其是第三点。

普通 BST 真正的性能公式其实可以写成：

Insert Find Erase ↓ O(h)

如果：

h ≈ logN

它非常高效。

如果：

h ≈ N

它就退化成接近链表。

所以后续学习 AVL 树和红黑树时，真正要解决的问题并不是推翻 BST，而是：

想办法维持 BST 的有序性质，同时控制树的高度。

理解了这一点，再继续学习平衡树，会发现 AVL 和红黑树并不是突然冒出来的新结构，而是在普通二叉搜索树之上，对“平衡性”这一缺陷进行进一步修正。