目录
1.什么是二叉搜索树？
二叉搜索树（Binary Search Tree, BST）是一种二叉树数据结构，其中每个节点的值都大于其左子树中所有节点的值，且小于其右子树中所有节点的值。这一性质递归地适用于所有子树，使得中序遍历BST会得到一个严格升序的序列。
如下图：这就是一个简单的二叉搜索树
2. 二叉搜索树的特点
●有序性：
对于树中的每个节点：
其左子树中的所有节点的值都小于该节点的值
其右子树中的所有节点的值都大于该节点的值
●递归结构：
左子树和右子树也必须是二叉搜索树（即上述性质递归地适用于所有子树）
●节点值唯一性（通常情况）：
一般情况下假设树中不存在值相同的节点（有些实现允许重复值，通常放在右子树）
3. 二叉搜索树的代码实现
BST支持高效的查找、插入和删除操作（平均时间复杂度O(log n)），但若不平衡（如退化成链表），最坏时间复杂度会降至O(n)。
3.1 设置节点
//设置二叉搜索树节点
template<class K>
struct BST_Node
{
K _key;
BST_Node<K>* _left;
BST_Node<K>* _right;
BST_Node(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};3.2 insert
插入节点过程：
bool insert(const K& k)
{
//判断树是否为空
if (_root == nullptr)
{
_root = new Node(k);
return true;
}
//记录插入位置的父节点
Node* parent = nullptr;
//记录插入位置
Node* cur = _root;
//寻找插入位置
while (cur)
{
//若k值大，往右树查找
if (cur->_key < k)
{
parent = cur;
cur = cur->_right;
}
//若k值小，往左树查找
else if (cur->_key > k)
{
parent = cur;
cur = cur->_left;
}
//不考虑有重复值的出现
else
return false;
}
//插入
cur = new Node(k);
if (parent->_key > k)
parent->_left = cur;
else
parent->_right = cur;
return true;
}3.3 find
寻找对应二叉搜索树中是否存在某节点：
bool find(const K& k)
{
//记录当前位置
Node* cur = _root;
while (cur)
{
//若需查找的节点存储的值小，往左节点查询
if (cur->_key > k)
{
cur = cur->_left;
}
//若需查找的节点存储的值大，往右节点查询
else if (cur->_key < k)
{
cur = cur->_right;
}
//若相等，则表示查到了
else
return true;
}
return false;
}3.4 erase
删除指定节点：
bool erase(const K& k)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//先找到指定节点
if (cur->_key > k)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < k)
{
parent = cur;
cur = cur->_right;
}
//找到要删除的节点
else
{
//先考虑两种特殊情况（左树或者右树为空——其中包含了叶子节点的情况）
//如果该节点左节点为空（左树为空）
if (cur->_left == nullptr)
{
//根节点情况
if (cur == _root)
_root = cur->_right;
//中间节点或叶子结点——用右树根节点（可能为空）替换
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
}
//如果该节点右节点为空（右树为空）
else if (cur->_right == nullptr)
{
if (cur == _root)
_root = cur->_left;
else
{
//中间节点或叶子结点——用左树根节点（可能为空）替换
if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
}
else
{
//用左子树最大节点或者右子树最小节点替代
//此处我用的是左子树最大节点
Node* rParent = cur;
Node* rCur = cur->_left;
while (rCur->_right)
{
rParent = rCur;
rCur = rCur->_right;
}
swap(cur->_key, rCur->_key);
if (rParent->_right == rCur)
rParent->_right = rCur->_right;
else
rParent->_left = rCur->_right;
delete rCur;
}
return true;
}
}
return false;
}3.5 print
按中序遍历顺序打印节点key值
//递归打印
void _print(Node* root)
{
if (root == nullptr)
return;
//先打印左值
_print(root->_left);
cout << root->_key << " ";
//再打印右值
_print(root->_right);
}
void print()
{
_print(_root);
cout << endl;
}
3.6 测试
4.二叉搜索树的推广
二叉搜索树（BST）不仅是一种基础数据结构，还在许多领域有广泛应用，并通过改进和推广衍生出更高效的变种。
由于普通BST在极端情况下（如插入有序数据）会退化成链表（O(n)时间复杂度），有人研究出了多种平衡BST变种：
AVL树：严格平衡，适合查询密集型场景
红黑树（如C++ STL、Java HashMap冲突处理）——近似平衡，插入/删除更高效
Treap（树堆）——结合BST和堆的特性，概率平衡
B树/B+树——优化磁盘I/O，广泛用于数据库和文件系统