二叉搜索树（BST）是左子树节点值小于等于根节点、右子树节点值大于等于根节点的二叉树。其平均时间复杂度为 O(logN)，最坏情况退化为 O(N)。文章解析了 BST 的概念、性能分析及增删查改操作，重点说明了两孩子节点删除时的替换策略。区分了仅存 key 与 key/value 两种应用场景，分别对应 set 与 map 模型。提供了基于 C++ 模板的完整代码实现，包含插入、查找、删除、遍历及内存管理功能，适用于理解 STL 容器底层原理。
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N。 最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N。 所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。
因此单纯的二叉搜索树的效率不能满足我们的要求，后续二叉搜索树的变形比如平衡搜索二叉树即 AVLTree，红黑树 RBTree，他们由于一些特殊的设计使得二叉搜索树的效率接近 log2N。
二分查找的缺陷: 需要存储在支持下标随机访问的结构中，并且有序。比如有序数组。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
正是二分查找的缺陷体现了二叉搜索树的价值。
插入的过程：
示例数据：int a[]={8,3,1,10,6,4,7,14,13};
从根开始比较，查找 x，x 比根的值大则往右边行走查找，x 比根值小则往左边行走查找最多查找高度次，走到到空，还没找到，这个值不存在。 如果不支持插入相等的值，找到 x 即可返回。 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
遍历方式：
过程： 首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。 如果查找元素存在则分以下四种情况分别处理（假设要删除的结点为 N）：
其实在代码实现上可以划分为两种情况：
以下是具体的解决方案：
只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。
简单举例：
总之 key 的搜索二叉树一般用于快速查询数据是否存在。
每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中 (结点) 除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value。
简单举例：
这里的 set 不是完全 set 的底层封装，本代码只是二叉搜索树 key 模型的实现代码。
#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
// 去重版 set
namespace twg {
//set -> ket 模型
//搜索二叉树节点
template<class K>
struct BSTnode {
//数据 K _key;
//根值 BSTnode* left;
//左孩子 BSTnode* right;
//右孩子
//构造
BSTnode(const K& key = K()) { _key = key; left = nullptr; right = nullptr; }
K _key;
BSTnode* left;
BSTnode* right;
};
//单参数的去重搜索二叉树容器 - > set
template<class K>
class set {
typedef BSTnode<K> Node;
public:
//增删查
//set and unoredered_set 不支持改（会破坏结构）
//增 ---- stl 中的 set 参数是 pair 但本文件只是简单实现
bool Insert(const K& key) {
//在二叉搜索树的规则下 查询 新加入的节点的位置
//能循环 尽量不 递归 这里采用双指针循环的方法
//判断是否为空树
if (_root == nullptr) {
_root = (key);
}
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
;
}
}
cur = (key);
(parent->right == ) {
parent->right = cur;
}
{
parent->left = cur;
}
;
}
{
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
(cur->left == ) {
(parent == ) {
_root = cur->right;
}
(parent->left == cur) {
parent->left = cur->right;
}
{
parent->right = cur->right;
}
cur;
cur = ;
;
}
{
Node* rightMinf = cur;
Node* rightMin = cur->left;
(rightMin->left) {
rightMinf = rightMin;
rightMin = rightMin->left;
}
(parent->left == cur) {
parent->left = rightMin;
}
{
parent->right = rightMin;
}
rightMinf->left = rightMin->right;
rightMin->left = cur->left;
rightMin->right = cur->right;
cur;
cur = ;
;
}
}
}
cout << << endl;
;
}
{
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
;
}
}
;
}
{
(_root);
(_root);
}
:
{
(root == )
;
(root->left);
cout << root->_key << endl;
(root->right);
}
Node* _root = ;
};
}
二叉搜索树 key/val 模型代码实现
#pragma once
//key/val 模型的实现
#include <iostream>
using namespace std;
namespace twg {
//key/val 节点
template<class K, class V>
struct BSTnode //其实就是 pair
{
//数据 K _key;
//V _val;
//BSTnode* left;
//左孩子 BSTnode* right;
//右孩子
//构造函数
BSTnode(const K& key, const V& val):_key(key),_val(val),left(nullptr),right(nullptr){}
K _key;
V _val;
BSTnode* left;
BSTnode* right;
};
// 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 = (a._root);
}
~() {
(_root);
}
map<K, V>& =(map<K, V> a) {
std::(_root, a._root);
*;
}
{
(_root == ) {
_root = (key, val);
;
}
Node* cur = _root;
Node* parent = ;
(cur) {
(key <= cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
}
cur = (key, val);
(cur->_key <= parent->_key) {
parent->left = cur;
}
{
parent->right = cur;
}
;
}
{
_inorder(_root);
cout << endl;
}
{
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
;
}
}
;
}
{
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
(cur->right != ) {
(parent == ) {
_root = cur->right;
}
{
(parent->left == cur) {
parent->left = cur->right;
}
{
parent->right = cur->right;
}
}
cur;
cur = ;
;
}
Node* leftMax = cur->right;
Node* leftMaxf = cur;
(leftMax->right) {
leftMaxf = leftMax;
leftMax = leftMax->right;
}
cur->_val = leftMax->_val;
cur->_key = leftMax->_key;
leftMaxf->right = leftMax->left;
leftMax;
leftMax = ;
;
}
}
cout << << endl;
;
}
V& []( K& key) {
Node* cur = _root;
Node* parent = ;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->left;
}
(key > cur->_key) {
parent = cur;
cur = cur->right;
}
{
cur->_val;
}
}
cur = (key, ());
(parent == ) {
_root = cur;
}
{
(key < parent->_key)
parent->left = cur;
parent->right = cur;
}
cur->_val;
}
:
{
(root == )
;
Node* newNode = (root->_key, root->_val);
newNode->left = (root->left);
newNode->right = (root->right);
newNode;
}
{
(root == )
;
(root->left);
(root->right);
root;
}
_inorder( Node* root) {
(root == )
;
_inorder(root->left);
cout << root->_key << << root->_val << endl;
_inorder(root->right);
}
Node* _root = ;
};
}
二叉搜索树的'左小右大'特性的背后，是高效数据查询的核心逻辑 —— 它既弥补了二分查找的插入删除短板，也为后续平衡树（AVL、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单数据存储需求。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online