跳到主要内容
C++ 二叉搜索树：概念、性能分析、增删查及实现 | 极客日志
C++ 算法
C++ 二叉搜索树：概念、性能分析、增删查及实现 二叉搜索树（BST）是一种特殊的二叉树，左子节点值小于等于根，右子节点值大于等于根。其查找、插入、删除平均时间复杂度为 O(log N)，最坏为 O(N)。本文详细讲解了 BST 的概念、性能分析、增删查操作原理及 C++ 代码实现，并区分了仅 Key 和 Key/Value 两种应用场景，如车牌识别、单词统计等。
LinuxPan 发布于 2026/2/21 更新于 2026/4/23 C++ 二叉搜索树详解
一、二叉搜索树的概念
二叉搜索树又称二叉排序树 ，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
二、二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N
最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
那么这样的效率显然是无法满足我们需求的，我们后续需要继续讲解二叉搜索树的变形，平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
需要存储在支持下标随机访问的结构中，并且有序。
插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。
三、二叉搜索树的插入
插入的具体过程如下：
树为空，则直接新增结点，赋值给 root 指针
树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
SearchBinaryTree.h
#pragma once
#include <iostream>
using namespace std;
template <class K >
struct
BSTNode
BSTNode
const
nullptr
nullptr
template
class
K
class
BSTree
typedef
public
bool Insert (const K& key)
if
nullptr
new
Node
return
true
nullptr
while
if
else
if
else
return
false
new
Node
if
else
return
true
void InOrder ()
private
void
if
nullptr
return
" "
nullptr
test.cpp #include "SearchBinaryTree.h"
#include <vector>
int main () int > a = { 0 , 3 , 1 , 10 , 1 , 6 , 4 , 7 , 14 , 13 };
BSTree<int > t;
for (auto e : a) {
t.Insert (e);
}
t.InOrder ();
return 0 ;
}
四、二叉搜索树的查找
从根开始比较，查找 x，x 比根的值大则往右边查找，x 比根值小则往左边查找。
最多查找高度次，走到空，还没找到，这个值不存在。
如果不支持插入相等的值，找到 x 即可返回
如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
【只有一个 3】 bool Find (const K& key) while (cur) {
if (key > cur->_key) {
cur = cur->_right;
} else if (key < cur->_key) {
cur = cur->_left;
} else {
return true ;
}
}
return false ;
}
【有多个 3】 查找 3，要求查找中序的第一个 3。具体后面会讲。
五、二叉搜索树的删除 首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）
要删除结点 N 左右孩子均为空
要删除的结点 N 左孩子为空，右孩子结点不为空
要删除的结点 N 右孩子为空，左孩子结点不为空
要删除的结点 N 左右孩子结点均不为空
把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 处理，效果是一样的）
把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点
把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点
无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 R(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。
下面代码的实现思路：分为 3 种情况（将上面的情况 1 归为情况 2 或者是情况 3），分为情况 2，情况 3，情况 4 来进行删除结点。
bool Erase (const K& key) nullptr ;
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else {
if (cur->_left == nullptr ) {
if (cur == _root) {
_root = cur->_right;
} else {
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr ) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
}
else {
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left) {
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight) {
minRightParent->_left = minRight->_right;
} else {
minRightParent->_right = minRight->_right;
}
delete minRight;
}
return true ;
}
}
return false ;
}
六、二叉搜索树的完整实现代码
SearchBinaryTree.h #pragma once
#include <iostream>
using namespace std;
template <class K >
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode (const K& key) :_key(key), _left(nullptr ), _right(nullptr ) { }
};
template <class K >
class BSTree {
typedef BSTNode<K> Node;
public :
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 ;
}
bool Find (const K& key) while (cur) {
if (key > cur->_key) {
cur = cur->_right;
} else if (key < cur->_key) {
cur = cur->_left;
} else {
return true ;
}
}
return false ;
}
bool Erase (const K& key) nullptr ;
Node* cur = _root;
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
} else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
} else {
if (cur->_left == nullptr ) {
if (cur == _root) {
_root = cur->_right;
} else {
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
} else if (cur->_right == nullptr ) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
} else {
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left) {
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight) {
minRightParent->_left = minRight->_right;
} else {
minRightParent->_right = minRight->_right;
}
delete minRight;
}
return true ;
}
}
return false ;
}
void InOrder () private :
void _InOrder(Node * root) {
if (root == nullptr ) {
return ;
}
_InOrder(root->_left);
cout << root->_key << " " ;
_InOrder(root->_right);
}
Node* _root = nullptr ;
};
test.cpp #include "SearchBinaryTree.h"
#include <vector>
int main () int > a = { 0 , 3 , 1 , 10 , 1 , 6 , 4 , 7 , 14 , 13 };
BSTree<int > t;
for (auto e : a) {
t.Insert (e);
}
t.InOrder ();
t.Erase (8 );
t.InOrder ();
t.Erase (14 );
t.InOrder ();
t.Erase (1 );
t.InOrder ();
for (auto e : a) {
t.Erase (e);
t.InOrder ();
}
return 0 ;
}
七、二叉搜索树 key 和 key/value 使用场景
7.1 key 搜索场景 只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了 。
场景 1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景 2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。
7.2 key/value 搜索场景 每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速找到 key 对应的 value。key/value 的搜索场景实现的二叉树搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value 。
场景 1：简单中英互译字典，树的结构中 (结点) 存储 key(英文) 和 vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数。
7.3 key/value 二叉搜索树代码实现
.h template <class K , class V >
class BSTree {
typedef BSTNode<K, V> Node;
public :
bool 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) {
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, value);
if (parent->_key < key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true ;
}
Node* 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 cur;
}
}
return nullptr ;
}
bool Erase (const K& key) 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 {
if (cur->_left == nullptr ) {
if (cur == _root) {
_root = cur->_right;
} else {
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
} else if (cur->_right == nullptr ) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
} else {
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left) {
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight) {
minRightParent->_left = minRight->_right;
} else {
minRightParent->_right = minRight->_right;
}
delete minRight;
}
return true ;
}
}
return false ;
}
void InOrder () private :
void _InOrder(Node* root) {
if (root == nullptr ) {
return ;
}
_InOrder(root->_left);
cout << root->_key << " " << root->_value << endl;
_InOrder(root->_right);
}
Node* _root = nullptr ;
};
.cpp int main () "苹果" ,"香蕉" ,"香蕉" ,"西瓜" , "苹果" , "西瓜" , "苹果" , "苹果" , "西瓜" , "苹果" , "香蕉" , "苹果" , "香蕉" ,"香蕉" ,"香蕉" };
key_value::BSTree<string, int > countTree;
for (auto & e : arr) {
auto ret = countTree.Find (e);
if (ret == nullptr ) {
countTree.Insert (e, 1 );
} else {
ret->_value++;
}
}
countTree.InOrder ();
return 0 ;
}
相关免费在线工具 加密/解密文本 使用加密算法（如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
