二叉搜索树简介
二叉搜索树（BST） 是一种具有特殊排序性质的二叉树，能够高效地执行数据检索、插入和删除操作。BST 的主要特性是，对于每个节点，其左子树中所有节点的值都小于或等于该节点的值，而右子树中所有节点的值都大于该节点的值。这一特性使得 BST 成为一种非常重要的数据结构，适用于搜索和排序任务，因为它提供了一种逻辑清晰且直接的方式来存储和检索有序数据。
二叉搜索树的定义与性质
二叉搜索树要么是一棵空树，要么是具有以下性质的二叉树：
如果左子树不为空，则左子树中的所有节点值都 小于或等于 根节点的值。
如果右子树不为空，则右子树中的所有节点值都 大于 根节点的值。
左右子树本身也必须是二叉搜索树。
这种排序特性使得搜索操作非常高效，因为每次决定向左还是向右走都将可能的位置数量减半，这类似于二分查找算法。
二叉搜索树的性能分析
BST 的性能直接受到树结构的影响。理想情况下，我们希望树是平衡的，以最小化高度，从而确保良好的性能。
最佳情况（平衡树）：在最佳情况下，BST 是完全二叉树或接近完全二叉树，高度为 ，其中 是节点的数量。
最差情况（退化树）：在最差情况下，树会退化为链表，树的高度为 。这通常发生在节点按顺序插入的情况下。
因此，插入、删除和搜索等操作的时间复杂度在 最佳情况下 为 ，而在 最差情况下 为 。
为了解决最差情况下可能出现的低效问题，引入了平衡二叉搜索树，如 AVL 树和红黑树。它们在插入和删除操作时会自动调整自身，以确保其高度保持在对数级别。
二叉搜索树与二分查找的局限性
BST 提供了与二分查找相似的搜索效率（），但有一些附加的灵活性：
二分查找 需要将数据存储在连续的结构（如数组）中，并且保持有序，这使得 插入 和 删除 的代价很高（）。
BST 可以将数据存储在动态扩展的结构中，无需连续内存，允许高效的插入和删除。
BST 的核心操作
1. 二叉搜索树中的插入操作
在 BST 中插入元素需要遵循树的排序性质：
如果树为空，新节点就成为根节点。
如果新值小于当前节点的值，则进入左子树。
如果新值大于当前节点的值，则进入右子树。
重复这一过程，直到找到合适的叶子位置。
以下是 C++ 中实现 BST 插入操作的示例代码：
#include <iostream>// 定义二叉搜索树节点模板
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;}private:Node* _root = nullptr; // 根节点指针，初始化为空
};在上面的代码中，我们定义了一个二叉搜索树的节点结构 BSTNode，以及一个二叉搜索树类 BSTree。Insert 方法实现了插入操作，从根节点开始遍历树，直到找到适合插入的位置。
2. 二叉搜索树中的查找操作
查找操作的实现与插入类似，根据键值的大小关系不断向左或向右移动，直到找到目标节点或到达叶子节点。
// 查找节点是否存在于二叉搜索树中
bool 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 true; // 找到目标值}}return false; // 未找到目标值
}在 Find 方法中，我们从根节点开始，根据键值大小关系不断移动，直到找到目标值或者树中不存在该值。
3. 二叉搜索树中的删除操作（重点）
删除操作较为复杂，因为需要处理多种情况：
叶子节点：直接删除该节点。
只有一个子节点的节点：让其父节点指向该子节点。
有两个子节点的节点：使用替换法，用右子树中的最小节点或左子树中的最大节点替换要删除的节点。
以下是删除操作的代码示例：
// 删除节点
bool Erase(const K& key) {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 {// 找到了需要删除的节点if (cur->_left == nullptr) { // 只有右子节点或无子节点的情况if (parent == nullptr) {_root = cur->_right; // 如果是根节点，则更新根节点} else {if (parent->_left == cur) {parent->_left = cur->_right;} else {parent->_right = cur->_right;}}delete cur;return true;} else if (cur->_right == nullptr) { // 只有左子节点的情况if (parent == nullptr) {_root = cur->_left; // 如果是根节点，则更新根节点} else {if (parent->_left == cur) {parent->_left = cur->_left;} else {parent->_right = cur->_left;}}delete cur;return true;} else { // 有两个子节点的情况Node* rightMinP = cur; // 记录右子树中最小节点的父节点Node* rightMin = cur->_right; // 找右子树中的最小节点while (rightMin->_left) {rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key; // 用右子树中最小节点的值替换当前节点的值if (rightMinP->_left == rightMin) {rightMinP->_left = rightMin->_right;} else {rightMinP->_right = rightMin->_right;}delete rightMin; // 删除右子树中的最小节点return true;}}}return false; // 未找到要删除的节点
}在 Erase 方法中，删除操作分为三种情况进行处理：叶子节点、只有一个子节点、以及有两个子节点的情况。在有两个子节点时，我们使用右子树中的最小节点来替换要删除的节点，以保持 BST 的性质。
二叉搜索树的使用场景
1. 仅使用 Key 作为搜索目标
在一些场景中，我们只需要查找某个值是否存在，此时只需要存储键（key）。例如：
小区无人值守车库：物业将业主车牌号录入系统，车辆进场时扫描车牌，如果在系统中则自动抬杆放行。
英文单词拼写检查：将所有正确的单词放入 BST 中，检查文档中的单词是否存在，不存在则标记为拼写错误。
2. 使用 Key-Value 结构
在有些情况下，每个键都有一个对应的值，树节点需要存储键值对。例如：
中英翻译字典：树节点中存储英文单词和对应的中文翻译，查找时输入英文即可获取对应的中文。
停车场计费系统：记录车辆的车牌和入场时间，离场时计算停车费用。
统计单词出现次数：读取文章中的每个单词并存入 BST，如果单词已经存在则增加其出现次数。
以下是一个简单的 Key-Value 二叉搜索树的实现：
template<class K, class V>
struct BSTNode {K _key; // 节点的键V _value; // 节点的值BSTNode<K, V>* _left; // 左子节点指针BSTNode<K, V>* _right; // 右子节点指针// 构造函数，初始化键值对和左右子节点为空BSTNode(const K& key, const V& value): _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};// Key-Value 型二叉搜索树
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; // 未找到目标节点}private:Node* _root = nullptr; // 根节点指针，初始化为空
};在 BSTree 类中，我们实现了一个带有键值对的二叉搜索树。插入操作和查找操作均遵循 BST 的基本规则，从根节点开始遍历，找到合适的位置或节点。
结论
二叉搜索树是一种强大而灵活的数据结构，适用于需要快速查找、插入和删除的场景。通过平衡的结构，BST 可以实现近似于对数级别的高效操作。然而，在某些极端情况下，BST 可能会退化为链表，因此更高级的平衡树如 AVL 树和红黑树在实际应用中更为常用。通过理解 BST 的基本操作和性能特点，我们可以更好地选择合适的数据结构来满足不同的应用需求。