跳到主要内容C++ 二叉搜索树原理与增删查实现 | 极客日志C++算法
C++ 二叉搜索树原理与增删查实现
本文介绍 C++ 中二叉搜索树的定义、性质及核心操作。内容包括查找、插入和删除节点的原理与代码实现，区分了 K 模型与 KV 模型的应用场景。文章分析了时间复杂度 O(logn)，并指出有序数据会导致性能退化至 O(n)，引出平衡二叉搜索树的重要性。
1. 二叉搜索树相关概念
如下图所示，二叉搜索树 (binary search tree) 满足下列条件：
- 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
- 任意节点的左、右子树也是二叉搜索树，同样满足条件 1
而下图就不是二叉搜索树：
2. 二叉搜索树的操作
我们将二叉搜索树封装为一个类 BSTree，并声明一个 _root 变量，指向树的根节点。
template<class K>
struct BSTNode {
BSTNode<K>* _left;
BSTNode<K>* _right;
K _key;
BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}
};
template<class K>
class BSTree {
public:
typedef BSTNode<K> Node;
private:
Node* _root;
};
2.1. 查找节点
给定目标 val，可以声明一个节点 cur，从二叉搜索树的根节点 _root 出发，循环比较 cur->_key 和 val 之间的大小关系：
- 若
val < cur->_key，说明目标节点在 cur 的左子树，执行 cur = cur->_left
- 若
val > cur->_key，说明目标节点在 cur 的右子树，执行 cur = cur->_right
- 若
val == cur->_key，说明找到目标节点，跳出循环并返回该节点
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度，O(log n)。
Node* find(const K& val) {
Node* cur = _root;
while(cur) {
if(val < cur->_key) cur = cur->_left;
else if(val > cur->_key) cur = cur->_right;
else break;
}
return cur;
}
2.2. 插入节点
给定一个待插入元素 val，为了保持左子树 < 根节点 < 右子树的性质，插入流程如下：
- 查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和
val 的大小关系循环向下搜索，直到越过叶子节点（遍历到 nullptr）跳出循环
- 在该位置插入节点：
new 一个新节点，将新节点置于 nullptr 的位置
- 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
- 为了实现插入节点，我们需要借助节点
pre 保存上一轮循环的节点。这样在遍历至 nullptr 时，我们可以获取到其父节点，从而完成节点插入操作。
bool insert(const K& val) {
if(_root == nullptr) {
Node* newNode = new Node(val);
_root = newNode;
return true;
}
Node* cur = _root;
Node* curPre = nullptr;
while(cur) {
if(val == cur->_key) return false;
else if(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} else {
curPre = cur;
cur = cur->_right;
}
}
Node* newNode = new Node(val);
if(curPre->_left == cur) curPre->_left = newNode;
else curPre->_right = newNode;
return true;
}
2.3. 删除节点
先在二叉树中查找到目标节点，再将其删除。与插入节点一样，我们需要保证在删除操作完成后，保证二叉搜索树的'左子树 < 根节点 < 右子树'的性质不变。
根据待删除节点的孩子数量，分 0、1 和 2 三种情况：
- 待删除结点是叶子节点，直接删除
- 待删除节点有一个孩子，将待删除节点的子节点和其替换即可
- 待删除节点 2 个孩子，不能直接删除，需要用一个节点替换该节点，保持'左子树 < 根节点 < 右子树'的性质不变，可以选择右子树最小节点或左子树最大节点
- 找到待删除节点
cur 的右子树最小节点 rightMin
- 用
rightMin 的值覆盖 cur，并删除 rightMin
cur 有两个孩子；rightMin 在更下方；rightMin 只有右孩子（B1）
触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right != nullptr
操作：cur->_key = rightMin->_key；令 rightMinPre->_left = rightMin->_right；删除 rightMin。
cur 有两个孩子；rightMin 在更下方；rightMin 无右孩子（B0）
触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right == nullptr
操作：cur->_key = rightMin->_key；令 rightMinPre->_left = nullptr；删除 rightMin。
cur 有两个孩子；rightMin 就是 cur->_right；rightMin 只有右孩子（A1）
触发：cur->_right没有左孩子，且 cur->_right->_right != nullptr
操作：cur->_key = rightMin->_key；令 cur->_right = rightMin->_right；删除 rightMin。
cur 有两个孩子；右子树最小节点 rightMin 就是 cur->_right；rightMin 无右孩子（A0）
触发：cur->_right没有左孩子，且 cur->_right->_right == nullptr
操作：cur->_key = rightMin->_key；令 cur->_right = nullptr；删除 rightMin。
bool erase(const K& val) {
if(_root == nullptr) return false;
Node* cur = _root;
Node* curPre = nullptr;
while(cur) {
if(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} else if(val > cur->_key) {
curPre = cur;
cur = cur->_right;
} else break;
}
if(cur == nullptr) return false;
if(cur->_left == nullptr || cur->_right == nullptr) {
Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;
if(cur != _root) {
if(curPre->_left == cur) curPre->_left = curNext;
else curPre->_right = curNext;
} else {
_root = curNext;
}
delete cur;
} else {
Node* rightMin = cur->_right;
Node* rightMinPre = cur;
while(rightMin->_left) {
rightMinPre = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
Node* rightMinNext = rightMin->_right;
if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
else rightMinPre->_right = rightMinNext;
delete rightMin;
}
return true;
}
- 用
cur 定位待删，curPre 记录父。
- 终止条件：命中或走到空。
- 注意：若支持自定义比较器，等价判断应为'!(val<key) && !(key<val)'。
curNext = (cur->_left ? cur->_left : cur->_right)。- 若
cur != _root：把 curPre 的相应孩子指向 curNext。
- 若
cur == _root：_root = curNext。
delete cur。- 要点：这是必须对'根'特判的地方（根没有父指针可改）。
2 个孩子：值覆盖 + 删后继（不移动 cur 本体）
- 覆盖键值：
cur->_key = rightMin->_key;（若有 value，一并拷/搬移）。
- 要点：这里不需要根特判，因为根节点对象没被删除，只是'值被改写'。
Node* rightMinNext = rightMin->_right;
if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
else rightMinPre->_right = rightMinNext;
delete rightMin;
Node* rightMin = cur->_right;
Node* rightMinPre = cur;
while (rightMin->_left) {
rightMinPre = rightMin;
rightMin = rightMin->_left;
}
3. 二叉搜索树的实现
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace BSTKey {
template<class K>
struct BSTNode {
BSTNode<K>* _left;
BSTNode<K>* _right;
K _key;
BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}
};
template<class K>
class BSTree {
public:
typedef BSTNode<K> Node;
BSTree()=default;
~BSTree(){destroy(_root); _root =nullptr;}
Node* find(const K& val) {
Node* cur = _root;
while(cur) {
if(val < cur->_key) cur = cur->_left;
else if(val > cur->_key) cur = cur->_right;
else break;
}
return cur;
}
bool insert(const K& val) {
if(_root == nullptr) {
Node* newNode = new Node(val);
_root = newNode;
return true;
}
Node* cur = _root;
Node* curPre = nullptr;
while(cur) {
if(val == cur->_key) return false;
else if(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} else {
curPre = cur;
cur = cur->_right;
}
}
Node* newNode = new Node(val);
if(curPre->_left == cur) curPre->_left = newNode;
else curPre->_right = newNode;
return true;
}
bool erase(const K& val) {
if(_root == nullptr) return false;
Node* cur = _root;
Node* curPre = nullptr;
while(cur) {
if(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} else if(val > cur->_key) {
curPre = cur;
cur = cur->_right;
} else break;
}
if(cur == nullptr) return false;
if(cur->_left == nullptr || cur->_right == nullptr) {
Node* curNext = cur->_left == nullptr ? cur->_right : cur->_left;
if(cur != _root) {
if(curPre->_left == cur) curPre->_left = curNext;
else curPre->_right = curNext;
} else {
_root = curNext;
}
delete cur;
} else {
Node* rightMin = cur->_right;
Node* rightMinPre = cur;
while(rightMin->_left) {
rightMinPre = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
Node* rightMinNext = rightMin->_right;
if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
else rightMinPre->_right = rightMinNext;
delete rightMin;
}
return true;
}
void inOrder() {
_inOrder(_root);
cout << endl;
}
private:
Node* _root;
void destroy(Node* root) {
if(root == nullptr) return;
destroy(root->_left);
destroy(root->_right);
delete root;
}
void _inOrder(Node* root) {
if(root == nullptr) return;
_inOrder(root->_left);
cout << root->_key << " ";
_inOrder(root->_right);
}
};
void testBST() {
BSTree<int> bst;
vector<int> arr ={8,3,10,1,6,14,5,7,13};
cout <<"=== 1. 创建二叉搜索树 ===\n";
cout <<"初始数据：-> ";
for(const auto& e : arr) cout << e << " ";
cout <<"\n创建完成数据：-> ";
for(const auto& e : arr) bst.insert(e);
bst.inOrder();
cout <<"=== 2. 查找数据 ===\n";
cout <<"查找不存在数据：28 查找结果："<< bst.find(28)<< endl;
cout <<"查找存在数据：14 查找结果："<< bst.find(14)<< endl;
cout <<"\n=== 3. 删除数据 ===\n";
cout <<"删除前的序列：->";
bst.inOrder();
cout <<"删除节点 6 后的序列：->";
bst.erase(6);
bst.inOrder();
cout <<"删除不存在的节点 86 后的序列：->";
bst.erase(86);
bst.inOrder();
cout <<"\n销毁二叉树：->";
bst.~BSTree();
bst.inOrder();
}
}
4. 二叉搜索树的应用
4.1. K 模型
只有 key 作为关键码（需要搜索到的值），结构中只存储 key 即可
- 以词库中所有单词集合中的每个单词作为
key，构建一颗二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
4.2. KV 模型
每个关键码 key，都有与之对应的值 value，即<key，value>的键值对，例如：
- 简单英汉词典中英文和中文是相互对应的关系，通过英文可快速找到其对应的中文，例如：<book,书>就是一种键值对
- 车库收费系统，一个键值记录车牌号，另一个键值记录停留时间，随后交给收费系统处理缴费事宜
- 统计单词出现次数，统计成功之后，给定单词就可快速找到其出现的次数，单词与其出现的次数就是<word,count>一种键值对
template<class K,class V>
struct BSTNode {
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& k,const V& v):_key(k),_value(v),_left(nullptr),_right(nullptr){}
};
template<class K,class V>
class BSTree {
public:
typedef BSTNode<K, V> Node;
private:
Node* _root =nullptr;
};
void dictionary() {
BSTree<string, string> dict;
dict.insert("书包","bag");
dict.insert("水果","fruit");
dict.insert("钢笔","pen");
dict.insert("书","book");
dict.insert("树","tree");
string str;
while(cin >> str) {
auto ret = dict.find(str);
if(ret == nullptr) cout <<"输入错误或词库中未包含该词"<< str << endl;
else cout << str <<"英文单词：->"<< ret->_value << endl;
}
}
void count() {
string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};
BSTree<string,int> cntTree;
for(const auto& s : arr) {
auto ret = cntTree.find(s);
if(ret == nullptr) cntTree.insert(s,1);
else ret->_value++;
}
cntTree.inOrder();
}
二叉搜索树的核心价值，在于用'左子树 < 根节点 < 右子树'的简单规则，换来了查找、插入、删除操作的高效性 —— 平衡状态下 O(log n) 的时间复杂度，让它成为处理动态数据查找场景的基础选择。无论是仅需判断'存在性'的 K 模型，还是需键值关联的 KV 模型，都能通过其核心操作快速适配，覆盖词典查询、计数统计等常见需求。
但需注意，二叉搜索树的性能依赖结构平衡：若插入数据有序，会退化为单链表，此时操作复杂度飙升至 O(n)。这也催生了 AVL 树、红黑树等平衡二叉搜索树 —— 它们通过自平衡机制维持树的高度，兼顾了二叉搜索树的简洁性与稳定高效的性能，是后续深入学习的重要方向。
