C++ 二叉搜索树详解：增删查改与 key/value 场景实现

二叉搜索树是一种左子树节点值小于等于根节点、右子树节点值大于等于根节点的树结构。详细解析了二叉搜索树的概念、性能分析（最优 O(logN)，最差 O(N)）、插入查找删除的具体逻辑及代码实现。重点区分了仅存储 key 的场景（如 set）和 key/value 存储场景（如 map），并提供了完整的 C++ 代码示例，涵盖去重与允许重复两种模型，为理解 STL 容器底层及平衡树打下基础。

CloudNative发布于 2026/2/8更新于 2026/4/18337 浏览

正文：

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。

2. 二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N 最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N

所以综合而言二叉搜索树增删查改时间复杂度为：O(N)

因此单纯的二叉搜索树的效率不能满足我们的要求，后续二叉搜索树的变形比如平衡搜索二叉树即 AVLTree，红黑树 RBTree，他们由于一些特殊的设计使得二叉搜索树的效率接近 log2N。

我们都知道有一个二分查找的算法可以快速帮我查询数据，其时间复杂度为 logN。那么大家是否有一个疑问为什么有了该算法后又要设计出搜索二叉树这种数据结构呢？

二分查找的缺陷:

需要存储在支持下标随机访问的结构中，并且有序。比如有序数组 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

正是二分查找的缺陷体现了二叉搜索树的价值。

3. 二叉搜索树的插入

插入的过程：

树为空，则直接新增结点，赋值给 root 指针树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）,具体设计自己决定

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

此时再插入 16，此时再插入 13。

4. 二叉搜索树的查找

从根开始比较，查找 x，x 比根的值大则往右边查找，x 比根值小则往左边查找最多查找高度次，走到到空，还没找到，这个值不存在。如果不支持插入相等的值，找到 x 即可返回。如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

如下图，查找 3，要找到 1 的右孩子的那个 3。

前序：根左右中序：左根右后序：左右根

5. 二叉搜索树的删除

过程： 首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

要删除结点 N 左右孩子均为空要删除的结点 N 左孩子位空，右孩子结点不为空要删除的结点 N 右孩子位空，左孩子结点不为空要删除的结点 N 左右孩子结点均不为空

但其实在代码实现上可以划分为两种情况：

没有孩子和只有一个孩子视为一种情况，因为可以将没有孩子视作只有一个孩子，只不过这个孩子是 nullptr 罢了有两个孩子

相关免费在线工具

加密/解密文本

使用加密算法（如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

#pragma once #include <assert.h> #include <iostream> using namespace std; // 去重版 set namespace twg { // set -> key 模型 // 搜索二叉树节点 template<class K> struct BSTnode { // 数据 K _key; K _key; // 根值 BSTnode* left; BSTnode* left; // 左孩子 BSTnode* right; BSTnode* right; // 右孩子 // 构造 BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {} }; // 单参数的去重搜索二叉树容器 -> set template<class K> class set { typedef BSTnode<K> Node; public: // 增删查 // set and unordered_set 不支持改（会破坏结构） // 增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现 bool Insert(const K& key) { // 在二叉搜索树的规则下查询新加入的节点的位置 // 能循环尽量不递归这里采用双指针循环的方法 // 判断是否为空树 if (_root == nullptr) { // 新加入的节点为根节点 _root = new Node(key); } // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点直接跳过 return true; } } // 当 cur 为空时即新节点的位置找到了 cur = new Node(key); // 链接 // 判断子相对父的位置 if (parent->right == nullptr) { // 链接 parent->right = cur; } else { parent->left = cur; } return true; } // 删 bool Erase(const K& key) { // 查询当前数据在哪个地方 // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点找到该位置 // 删除 // 根据删除节点的孩子个数执行不同的删除逻辑 // 0~1 个孩子的代码实现可以合并 // 即可以把 0 个孩子看成 1 个空孩子 // 假设只有右孩子 if (cur->left == nullptr) { // 删除根节点 if (parent == nullptr) { _root = cur->right; } // 删除局部节点 // 将 cur 的右孩子链接成为 parent 的孩子 if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } delete cur; // 删除节点 cur = nullptr; return true; } else { // 有两个孩子 // 替代法 // 这里以右子树的最小孩子替代 cur 为例 Node* rightMinf = cur; Node* rightMin = cur->left; // 最小孩子一定在右子树的最左节点处（不一定为叶子节点） while (rightMin->left) { rightMinf = rightMin; rightMin = rightMin->left; } // 调整链接关系 // 调整 parent 的链接关系 if (parent->left == cur) { parent->left = rightMin; } else { parent->right = rightMin; } // 调整 rightMinp 的链接关系 rightMinf->left = rightMin->right; // rightMin 不一定为叶子节点 // 调整替换节点的父子链接关系 rightMin->left = cur->left; rightMin->right = cur->right; // 删除节点 delete cur; cur = nullptr; return true; } } } cout << "没有该节点" << endl; return false; } // 查 bool Find(const K& key) { // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点直接跳过 return true; } } // 没找到 return false; } void Inorder() { assert(_root); inorder(_root); } private: // 中序遍历 void inorder(const Node* root) { // 递归出口 if (root == nullptr) return; // 左根右 inorder(root->left); // 左子树 cout << root->_key << endl; inorder(root->right); } Node* _root = nullptr; // 根节点 }; } // 模拟 unordered_set 即不去重版 namespace Twg { // set -> key 模型 // 搜索二叉树节点 template<class K> struct BSTnode { // 数据 K _key; K _key; // 根值 BSTnode* left; BSTnode* left; // 左孩子 BSTnode* right; BSTnode* right; // 右孩子 // 构造 BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {} }; // 单参数的去重搜索二叉树容器 -> set template<class K> class set { typedef BSTnode<K> Node; public: // 增删查 // set and unordered_set 不支持改（会破坏结构） // 增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现 bool Insert(const K& key) { // 在二叉搜索树的规则下查询新加入的节点的位置 // 能循环尽量不递归这里采用双指针循环的方法 // 判断是否为空树 if (_root == nullptr) { // 新加入的节点为根节点 _root = new Node(key); return true; } // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key <= cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } } // 当 cur 为空时即新节点的位置找到了 cur = new Node(key); // 链接 // 判断子相对父的位置 if (parent->right == nullptr) { // 链接 parent->right = cur; } else { parent->left = cur; } return true; } // 删 bool Erase(const K& key) { // 查询当前数据在哪个地方 // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点找到该位置 // 删除 // 根据删除节点的孩子个数执行不同的删除逻辑 // 0~1 个孩子的代码实现可以合并 // 即可以把 0 个孩子看成 1 个空孩子 // 假设只有右孩子 if (cur->left == nullptr) { // 删除根节点 if (parent == nullptr) { _root = cur->right; } // 删除局部节点 // 将 cur 的右孩子链接成为 parent 的孩子 if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } delete cur; // 删除节点 cur = nullptr; return true; } else { // 有两个孩子 // 替代法 // 这里以右子树的最小孩子替代 cur 为例 Node* rightMinf = cur; Node* rightMin = cur->left; // 最小孩子一定在右子树的最左节点处（不一定为叶子节点） while (rightMin->left) { rightMinf = rightMin; rightMin = rightMin->left; } // 调整链接关系 // 调整 parent 的链接关系 if (parent->left == cur) { parent->left = rightMin; } else { parent->right = rightMin; } // 调整 rightMinp 的链接关系 rightMinf->left = rightMin->right; // rightMin 不一定为叶子节点 // 调整替换节点的父子链接关系 rightMin->left = cur->left; rightMin->right = cur->right; // 删除节点 delete cur; cur = nullptr; return true; } } } cout << "没有该节点" << endl; return false; } // 查 bool Find(const K& key) { // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点直接跳过 return true; } } // 没找到 return false; } void Inorder() { assert(_root); inorder(_root); } private: // 中序遍历 void inorder(const Node* root) { // 递归出口 if (root == nullptr) return; // 左根右 inorder(root->left); // 左子树 cout << root->_key << endl; inorder(root->right); } Node* _root = nullptr; // 根节点 }; }

#pragma once // key/val 模型的实现 #include <iostream> using namespace std; namespace twg { // key/val 节点 template<class K, class V> struct BSTnode // 其实就是 pair { // 数据 K _key; K _key; V _val; // BSTnode* left;//左孩子 BSTnode* left; // BSTnode* right;//右孩子 BSTnode* right; // 构造函数 BSTnode(const K& key, const V& val) : _key(key), _val(val), left(nullptr), right(nullptr) {} }; // key/val 模型容器 map template<class K, class V> class map { typedef BSTnode<K, V> Node; public: // 默认成员函数 // 显示默认构造 map() = default; // C++11 引用告诉编译器帮我生成一个默认构造函数 /*map() { _root = nullptr; }*/ // 拷贝构造 map(const map<K, V>& a) { // 递归式深拷贝 _root = Copy(a._root); } // 析构函数 ~map() { Destory(_root); } // 赋值 map<K, V>& operator=(map<K, V> a) { std::swap(_root, a._root); // 现代式写法 a 是临时拷贝对象出了函数会自动析构 return *this; } // 增删查改 // 增 bool Insert(const K& key, const V& val) { // 先寻找位置 // 判断是否为空树 if (_root == nullptr) { // 新节点为根节点 _root = new Node(key, val); return true; } // 双指针循环 Node* cur = _root; Node* parent = nullptr; while (cur) { // 根据 key 找 if (key <= cur->_key) { // 新节点的位置在左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 新节点的位置在右子树处 parent = cur; cur = cur->right; } } // 找到了新节点的位置 cur = new Node(key, val); // 链接父子 if (cur->_key <= parent->_key) { // 新节点为 parent 的左孩子 parent->left = cur; } else { // 新节点为 parent 的右孩子 parent->right = cur; } return true; } // 遍历 void Inorder() { _inorder(_root); cout << endl; } // 查根据 key bool Find(const K& key) { // 双指针从根节点出发寻找合适位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { // 该节点在 cur 的左子树处 parent = cur; cur = cur->left; } else if (key > cur->_key) { // 该节点在 cur 的右子树处 parent = cur; cur = cur->right; } else { // key == cur->_key 即相同节点直接跳过 return true; } } // 没找到 return false; } // 删除 bool Erase(const K& key) { // 先找 Node* cur = _root; Node* parent = nullptr; while (cur) { // 根据 key 找 if (key < cur->_key) { parent = cur; cur = cur->left; } else if (key > cur->_key) { parent = cur; cur = cur->right; } else { // 找到了 // 根据孩子的个数执行不同的删除逻辑 // 0~1 个孩子代码实现上相同可将叶子节点视作只有一个空孩子 // 假设只有右孩子 if (cur->right != nullptr) { // 判断该节点是否为根节点 if (parent == nullptr) { // 该节点为根节点 // 右子树成为新的根节点 _root = cur->right; } // 删除的是子树上的节点 else { if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } } // 删除节点 delete cur; cur = nullptr; return true; } // 有两个孩子 // 替换法 // 以左子树的最大孩子为替代不一定为叶子节点 Node* leftMax = cur->right; Node* leftMaxf = cur; while (leftMax->right) { leftMaxf = leftMax; leftMax = leftMax->right; } // 找到了替换节点 // 调整链接 cur->_val = leftMax->_val; cur->_key = leftMax->_key; leftMaxf->right = leftMax->left; // 删除节点 delete leftMax; leftMax = nullptr; return true; } } // 删除失败 cout << "没有该节点，删除失败" << endl; return false; } // 改 V& operator[](const K& key) { // 1. 查找键，若存在则返回对应值的引用 Node* cur = _root; Node* parent = nullptr; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->left; } else if (key > cur->_key) { parent = cur; cur = cur->right; } else { // 找到键，返回值的引用 return cur->_val; } } // 2. 键不存在，插入新节点（值用默认构造） cur = new Node(key, V()); // 插入默认值（如 int 默认 0） if (parent == nullptr) { // 空树，新节点作为根 _root = cur; } else { // 链接到父节点的左/右子树 if (key < parent->_key) parent->left = cur; else parent->right = cur; } // 3. 返回新插入节点的值的引用 return cur->_val; } private: // 函数 Node* Copy(const Node* root) { // 递归出口 if (root == nullptr) return nullptr; Node* newNode = new Node(root->_key, root->_val); newNode->left = Copy(root->left); // 拷贝左子树 newNode->right = Copy(root->right); // 拷贝右子树 return newNode; } void Destory(Node* root) { // 递归出口 if (root == nullptr) return; // 递归式析构 // 先析构左右子树 Destory(root->left); Destory(root->right); // 析构根 delete root; // 核心 root = nullptr; } // 遍历 void _inorder(const Node* root) { // 递归出口 if (root == nullptr) return; // 中序遍历 _inorder(root->left); // 左子树 cout << root->_key << ": " << root->_val << endl; // 根值 _inorder(root->right); // 右子树 } // 数据 Node* _root = nullptr; // 根节点 }; }

C++ 二叉搜索树详解：增删查改与 key/value 场景实现

正文：

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3. 二叉搜索树的插入

4. 二叉搜索树的查找

5. 二叉搜索树的删除

更多推荐文章

相关免费在线工具

6. 二叉搜索树 key 和 key/value 使用场景

6.1 key 搜索场景：

6.2 key/val 搜索场景

7. 二叉搜索树的实现代码

7.1 key 模型代码实现

7.2 key/val 代码实现

结语

C++ 二叉搜索树详解：增删查改与 key/value 场景实现

正文：

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3. 二叉搜索树的插入

4. 二叉搜索树的查找

5. 二叉搜索树的删除

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

6. 二叉搜索树 key 和 key/value 使用场景

6.1 key 搜索场景：

6.2 key/val 搜索场景

7. 二叉搜索树的实现代码

7.1 key 模型代码实现

7.2 key/val 代码实现

结语