二叉搜索树（BST）详解

目录

1. 什么是二叉搜索树

2. 二叉搜索树的特点

时间复杂度分析

最优情况

最坏情况

3.二叉搜索树的中序遍历

中序遍历代码

4. 二叉搜索树 的插入

插入规则

插入过程示例

Insert 实现

5. 二叉搜索树的查找

查找思想

Find 实现

6. 二叉搜索树的删除

情况1：删除叶子节点

情况2：只有右孩子

情况3：只有左孩子

情况4：左右孩子都存在

替换法删除

方法：

删除代码

7.二叉搜索树类型

key 型 二叉搜索树

1. 车牌识别

2. 拼写检查

key/value 型 二叉搜索树

key/value 应用场景

8. 二叉搜索树与二分查找的区别

1. 什么是二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST），又叫二叉排序树，是一种特殊的二叉树。

它满足以下性质：

• 左子树所有节点的值都小于根节点

• 右子树所有节点的值都大于根节点

• 左右子树也分别是二叉搜索树

例如：

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

这棵树中：

• 3 < 8，所以在左边

• 10 > 8，所以在右边

• 6 > 3，所以在 3 的右边

• 4 < 6，所以在 6 的左边

2. 二叉搜索树的特点

BST 最大的优势：

• 查找快

• 插入快

• 删除快

因为每次比较都能排除一半区域，思想类似二分查找。

时间复杂度分析

最优情况

如果树接近完全二叉树：

高度：log N

查找效率：O(log N)

最坏情况

如果插入数据有序：

1 2 3 4 5

BST 会退化成链表：

1 \ 2 \ 3 \ 4 \ 5

高度变成：N

时间复杂度退化：O(N)

所以普通 BST 并不稳定。

后面会引出：

• AVL树

• 红黑树

它们属于平衡二叉搜索树。

3.二叉搜索树的中序遍历

BST 有一个非常重要的性质：

中序遍历结果一定有序

中序遍历代码

void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }

4. 二叉搜索树 的插入

插入规则

从根开始：

• 比当前节点小 → 往左走

• 比当前节点大 → 往右走

• 找到空位置后插入

插入过程示例

插入：

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

形成：

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

Insert 实现

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; } } cur = new Node(key); if (parent->_key < key) parent->_right = cur; else parent->_left = cur; return true; }

这里二叉搜索树可以分为冗余树和非冗余的，冗余树就是允许数据可重复，我们可以默认相等的数据插入左边

测试用例

int main() { BSTree<int> t; int a[] = { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13}; for (auto e : a) { t.Insert(e); } t.InOrder(); t.Insert(16); t.Insert(3); t.InOrder(); return 0; }

5. 二叉搜索树的查找

查找思想

从根开始：

• key 大 → 右走

• key 小 → 左走

• 相等 → 找到

Find 实现

bool 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 true; } } return false; }

6. 二叉搜索树的删除

删除是 BST 最复杂的操作。

情况1：删除叶子节点

例如删除：

1

直接删除即可。

情况2：只有右孩子

3 \ 5

删除 3：

5

父亲直接指向右孩子。

情况3：只有左孩子

5 / 3

删除 5：

3

父亲直接指向左孩子。

情况4：左右孩子都存在

例如删除：

8 / \ 3 10

不能直接删。

因为左子树没地方放，右子树也没地方放

替换法删除

方法：

找到左子树最大值或者右子树最小值替换当前节点。

因为左子树最大值一定小于当前节点且大于左子树其他节点

右子树最小值一定大于当前节点且小于右子树其他节点

所以替换后 BST 仍成立。

删除代码

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 { // 0-1个孩⼦的情况 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; return true; } else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; return true; } else { // 2个孩⼦的情况 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; } } } return false; }

假设初始树长这样：

这里我们可以把删除叶子节点和只有一个孩子的节点归为一类，因为他们都是属于把父亲节点指向该节点的子树，这里删除只需要注意，被删除节点是父亲的左节点还是右节点，然后分类讨论一下即可

t.Erase(1); t.Erase(10); t.InOrder();

如果有2个孩子，找到右子树最小节点，然后交换2个节点的值后，删除该节点即可，因为这个右子树最小节点的左子树一定是空，所以删除它的逻辑跟前面一样，让它的父亲指向它的右子树即可

所以我们还得有父亲节点，在初始化是不要赋值为空，因为赋值为空，如果被删除节点的右节点刚好是最小节点，那么就不会进入循环给父亲节点重新赋值，就比如改图中8这个节点，它的右节点10刚好就是右子树的最小节点，这会引发空指针解引用问题，所以初始化赋值为cur即可

t.Erase(6); t.Erase(8); t.InOrder();

7.二叉搜索树类型

key 型 二叉搜索树

特点：只存 key：

BST<int>

本质：

set<int>

应用场景：

1. 车牌识别

判断车辆是否属于本小区。

2. 拼写检查

检查单词是否存在。

key/value 型 二叉搜索树

节点结构

template<class K, class V> struct BSTNode { K _key; V _value; BSTNode<K,V>* _left; BSTNode<K,V>* _right; };

特点：通过 key 查找 value。

类似：

map<string, int>

set和map底层都是红黑树

key/value 应用场景

1. 英汉词典

left -> 左边 right -> 右边

2. 停车场计费

车牌号 -> 入场时间

3. 统计单词次数

例如：

苹果 苹果 香蕉 苹果

统计：

苹果 -> 3 香蕉 -> 1

8. 二叉搜索树与二分查找的区别