【C++ 进阶】二叉搜索树（BST）全景拆解：从原理分析到模板源码实现

二叉搜索树

• 1. 二叉搜索树的概念与核心性质
• 2. 性能分析与二分查找对比
• 3. Key 模型与 Key-Value 模型应用场景
• • 3.1 Key 搜索场景（单关键码）
  • • 场景 1（小区无人值守车库）
    • 场景 2（英文文章拼写检查）
  • 3.2 Key-Value 搜索场景（键值对）
  • • 场景 1（简单中英互译字典）
    • 场景 2（商场停车计费）
    • 场景 3（单词词频统计）
• 4. 节点与类的 C++ 抽象定义
• 5. 查找算法（Find）剖析
• 6. 插入算法（Insert）分段拆解与答疑
• • 6.1 步骤 1：特判空树逻辑
  • 6.2 步骤 2：迭代寻找落脚点并记录父节点（Parent 追踪）
  • 6.3 步骤 3：开辟新节点与父节点物理挂接
  • 6.4 Insert 接口完整代码
• 7. 删除算法（Erase）三大场景深度拆解【重点/难点📌】
• • 7.1 场景 1：要删除节点 cur 的左孩子为空（托孤右孩子）
  • 7.2 场景 2：要删除节点 cur 的右孩子为空（托孤左孩子）
  • 7.3 场景 3：要删除节点 cur 的左右孩子都不为空（替换法）
  • 7.4 Erase 接口完整代码
• 8. 辅助成员函数与封装策略
• • 8.1 递归接口的私有封装策略
  • 8.2 深拷贝构造与后序析构
  • 8.3 现代写法赋值重载
• 9. 二叉搜索树完整 C++ 模板实现代码

1. 二叉搜索树的概念与核心性质

二叉搜索树（BST） 又称二叉排序树，它或者是造一棵空树；如果它不为空，则必须满足以下基本性质：

注：二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。 后续学习的 map/set 不支持插入相等值，而 multimap/multiset 则支持插入相等值。

⭐ 核心性质与行为机制： 对任何一棵二叉搜索树进行中序遍历（左 -> 根 -> 右），得到的输出序列一定是一个单调递增的有序序列！ 若想要达到递减的效果，只需反向中序遍历（右 -> 根 -> 左）即可

2. 性能分析与二分查找对比

二叉搜索树的增删查改效率高度依赖于树的物理形态：

• 最优情况：二叉搜索树为完全二叉树（或接近完全二叉树），其高度为

  log

  ⁡

  2

  N

  \\log_2 N

  log2​N，增删查改的时间复杂度为

  O

  (

  log

  ⁡

  2

  N

  )

  O(\\log_2 N)

  O(log2​N)。

• 最差情况：二叉搜索树退化为单支树（例如按有序数据升序/降序插入），其高度为

  N

  N

  N，时间复杂度退化为

  O

  (

  N

  )

  O(N)

  O(N)。

综合而言，普通二叉搜索树的增删查改时间复杂度为

O

(

N

)

O(N)

O(N)。 为了满足高并发、高性能场景下的需求，后续必须引入平衡二叉搜索树（AVL 树和红黑树）。

💡 对比：二分查找 vs 平衡二叉搜索树 二分查找同样能达到

O

(

log

⁡

2

N

)

O(\\log_2 N)

O(log2​N) 的查找效率，但存在两大致命缺陷：

这正是平衡二叉搜索树不可替代的价值所在。

3. Key 模型与 Key-Value 模型应用场景

在实际工程开发中，二叉搜索树主要分为两大应用场景：

3.1 Key 搜索场景（单关键码）

结构中仅存储 Key 作为关键码，用于判断某个数据是否存在：

场景 1（小区无人值守车库）

物业将已买车位的业主车牌号录入后台系统，车辆进场时扫描车牌在不在系统二叉树中，在则抬杆，不在则提示“非本小区车辆，无法进入”。

场景 2（英文文章拼写检查）

将词库中所有单词放入二叉搜索树，读取文章中的单词并在树中查找，不在则波浪线标红提示。

⭐ 总结：语法细节与行为机制 Key 模型的二叉搜索树支持增删查，但绝对不支持修改 Key！因为直接修改 Key 会破坏二叉搜索树“左小右大”的物理结构，引发检索失效。

3.2 Key-Value 搜索场景（键值对）

每一个关键码 Key 都对应一个 Value，查找时以 Key 为关键字进行比较，找到后可以快速获取或修改对应的 Value：

场景 1（简单中英互译字典）

节点存储 <Key: Value: 中文解释 英文单词,>。输入英文即可检索出对应中文。

void TestDictionary()
{
// 构建字典树，Key 为英文单词，Value 为中文解释
key_value::BSTree<string, string> dict;

// 插入英汉词条
dict.Insert("string", "字符串");
dict.Insert("tree", "树");
dict.Insert("left", "左边");
dict.Insert("right", "右边");

string word;
cout << "请输入要查询的英文单词 (输入 quit 退出):" << endl;
while (cin >> word && word != "quit")
{
// Find 查找节点，匹配成功返回 Node*，匹配失败返回 nullptr
auto ret = dict.Find(word);
if (ret)
{
cout << "->" "中文解释：" << ret->_value << endl;
}
else
{
cout << "->" "未找到该单词！" << endl;
}
}
}

场景 2（商场停车计费）

进场时记录 <Key: Value: 入场时间 车牌号,>；离场时根据车牌号查找入场时间，计算停车时长与费用。

void TestParkingSystem()
{
// 车库管理系统，Key 为车牌号，Value 为入场时间戳（整型代表分钟数）
key_value::BSTree<string, int> parkingLot;

// 1. 车辆陆续进入车库，记录入场时间（分钟）
parkingLot.Insert("粤B66666", 600); // 10:00 入场
parkingLot.Insert("粤B88888", 630); // 10:30 入场
parkingLot.Insert("粤A12345", 700); // 11:40 入场

// 2. 车辆准备离开车库，假设离场时间为 720（12:00），费率为 0.5元/分钟
string outCar = "粤B66666";
int leaveTime = 720;

auto carNode = parkingLot.Find(outCar);
if (carNode)
{
int duration = leaveTime – carNode->_value; // 计算停车时长
double fee = duration * 0.5; // 计算应缴费用
cout << "车牌号: " << outCar
<< " | 停车时长: " << duration << "分钟"
<< " | 应缴费用: " << fee << "元" << endl;

// 缴费结算后出库，从车库树中删除记录
parkingLot.Erase(outCar);
}
else
{
cout << "异常：未找到该车辆的入场记录！" << endl;
}
}

场景 3（单词词频统计）

读取单词，不存在则插入 <单词, 1>；存在则将节点中对应的次数 Value++。

void TestWordCount()
{
// 水果名称出现频次统计
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
key_value::BSTree<string, int> countTree;

for (const auto& str : arr)
{
auto node = countTree.Find(str);
if (node == nullptr)
{
// 第一次出现：插入节点，计数（Value）初始化为 1
countTree.Insert(str, 1);
}
else
{
// 已存在该节点：利用 Find 返回的节点指针，直接递增其 Value
node->_value++;
}
}

// 中序遍历打印最终词频统计结果
cout << "水果词频统计结果：" << endl;
countTree.InOrder();
}

⭐ 总结：语法细节与行为机制 Key-Value 模型支持修改 Value，但依然禁止修改 Key。修改 Value 不会改变节点在树中的排布位置，因此是完全安全的操作。

4. 节点与类的 C++ 抽象定义

namespace key_value
{
// 二叉搜索树节点结构体（Key-Value 模型）
template<class K, class V>
struct BSTNode
{
K _key; // 关键字 Key
V _value; // 映射值 Value
BSTNode<K, V>* _left; // 指向左孩子的指针
BSTNode<K, V>* _right; // 指向右孩子的指针

// 节点构造函数
BSTNode(const K& key, const V& value)
: _key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};

// 二叉搜索树类定义
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node; // 内部重命名，简化书写
public:
BSTree() = default; // C++11 显式生成默认构造函数

private:
Node* _root = nullptr; // 类内初始化，防止野指针
};
}

⭐ 语法细节与行为机制：

模板泛型设计：通过 template<class K, class V> 实现 Key 与 Value 的解耦，支持任意类型的比较与映射。

类内缺省值（C++11）：给 _root 赋予初始值 nullptr，避免无参构造函数忘记初始化而产生野指针危险。

5. 查找算法（Find）剖析

查找是二叉搜索树最基础的操作，核心思想是利用树的有序性进行二分路径排除。

Node* Find(const K& key)
{
Node* cur = _root; // 从根节点开始查找
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right; // 目标 key 大于当前节点，转向右子树
}
else if (cur->_key > key)
{
cur = cur->_left; // 目标 key 小于当前节点，转向左子树
}
else
{
return cur; // 匹配成功，返回节点指针
}
}
return nullptr; // 遍历结束未找到，返回空指针
}

⭐ 语法细节与行为机制： 二分排除机制：利用 BST “左小右大” 的性质，每次比较后都能直接排除整整半边子树，查找次数最多等于树的高度

H

H

H。

返回值设计：返回 Node* 指针而非布尔值，方便在 Key-Value 模型中查找到节点后，直接对 cur->_value 进行读写与修改（例如词频统计时的 ret->_value++）。

6. 插入算法（Insert）分段拆解与答疑

插入算法的目标是寻找合适的空位落脚，并建立父子节点的物理链接。我们将 Insert 函数拆解为 3 个步骤 逐一解析：

6.1 步骤 1：特判空树逻辑

// 1. 空树特判
if (_root == nullptr)
{
_root = new Node(key, value); // 直接开辟节点作为根节点
return true;
}

⭐ 语法细节与行为机制：

当树为空（_root == nullptr）时，没有父节点可供链接。此时直接开辟新节点赋值给 _root 即可完成插入。

6.2 步骤 2：迭代寻找落脚点并记录父节点（Parent 追踪）

Node* parent = nullptr; // 实时记录 cur 的父节点
Node* cur = _root; // 从根开始寻找落脚点

// 2. 迭代查找空落脚点
while (cur)
{
if (cur->_key < key)
{
parent = cur; // 往下走之前记录当前节点为 parent
cur = cur->_right; // 比当前节点大，向右寻找
}
else if (cur->_key > key)
{
parent = cur; // 往下走之前记录当前节点为 parent
cur = cur->_left; // 比当前节点小，向左寻找
}
else
{
return false; // 已存在相同的 key，不允许冗余，插入失败
}
}

⭐ 语法细节与行为机制：

👔 面试常考：为什么必须创造 parent 指针？ 当 while (cur) 循环结束时，cur 本身已经变成了 nullptr。在 C++ 中，空指针无法进行解引用去修改上级节点的 _left 或 _right 指针！因此必须在每次移动 cur 前用 parent 记录父节点地址，最后通过 parent 完成新节点的挂接。

去重校验： 向下寻找落脚点时，如果发现 cur->_key == key，说明树中已存在相同关键码，直接返回 false 终止插入，维护 Key 的唯一性。

6.3 步骤 3：开辟新节点与父节点物理挂接

// 3. cur 为 nullptr，开辟新节点并通过 parent 建立物理链接
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur; // 比 parent 大，挂在右孩子位置
}
else
{
parent->_left = cur; // 比 parent 小，挂在左孩子位置
}
return true;

⭐ 语法细节与行为机制：

经过 while 循环降落到空落脚点后，new 出新节点赋值给 cur。

将新节点的 key 与 parent->_key 比较大小：若较大则挂接在 parent->_right，若较小则挂接在 parent->_left，完成新节点向原树上的物理挂载。

6.4 Insert 接口完整代码

bool Insert(const K& key, const V& value)
{
// 1. 空树特判
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}

Node* parent = nullptr;
Node* cur = _root;

// 2. 迭代查找空落脚点
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false; // 不允许冗余，插入失败
}
}

// 3. 建立父子节点物理链接
cur = new Node(key, value);
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;

return true;
}

7. 删除算法（Erase）三大场景深度拆解【重点/难点📌】

删除节点是 BST 中最复杂的逻辑。当定位到待删除节点 cur 后，为了在释放 cur 后不破坏整棵树的有序结构，必须根据 cur 拥有的子节点情况分为 三大场景 处理：

7.1 场景 1：要删除节点 cur 的左孩子为空（托孤右孩子）

// 场景 1：cur 的左孩子为空
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right; // 特例：删除的是根节点
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right; // cur 是父节点的左孩子，把 cur 的右孩子托孤给 parent 的左边
else
parent->_right = cur->_right; // cur 是父节点的右孩子，把 cur 的右孩子托孤给 parent 的右边
}
delete cur; // 释放物理空间
return true;
}

⭐ 语法细节与行为机制：

托孤逻辑：当 cur 没有左孩子时（包含左右孩子均为空的叶子节点情况），cur 最多只有一个右孩子。此时直接将 cur->_right“托孤”给父节点 parent 链接即可。

根节点特例（parent == nullptr）：若删除的是根节点 _root，此时 parent 为初始值 nullptr，无法解引用。必须特判直接更新 _root = cur->_right。

例图：

7.2 场景 2：要删除节点 cur 的右孩子为空（托孤左孩子）

// 场景 2：cur 的右孩子为空
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left; // 特例：删除的是根节点
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left; // cur 是父节点的左孩子，把 cur 的左孩子托孤给 parent 的左边
else
parent->_right = cur->_left; // cur 是父节点的右孩子，把 cur 的左孩子托孤给 parent 的右边
}
delete cur; // 释放物理空间
return true;
}

⭐ 语法细节与行为机制：

处理方式与场景 1 完全对称。当 cur 没有右孩子时，直接将其左孩子“托孤”给 parent；若删除的是根节点，更新 _root = cur->_left。

例图：

7.3 场景 3：要删除节点 cur 的左右孩子都不为空（替换法）

当 cur 既有左孩子又有右孩子时无法直接“托孤”。此时采用 替换法（Substitution Method）：寻找一个替代节点覆盖 cur 的数据，转而销毁真正的替代节点。

// 场景 3：cur 的左右孩子均不为空（替换法）
else
{
// 1. 寻找右子树最左节点 rightMin（右子树最小值）
Node* rightMinP = cur; // 📌关键坑点：必须初始化为 cur，不能给 nullptr！
Node* rightMin = cur->_right;

while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left; // 迭代向左找最小值
}

// 2. 数据覆盖：用替代节点的值覆盖 cur 的值
cur->_key = rightMin->_key;
cur->_value = rightMin->_value;

// 3. 物理销毁替代节点 rightMin（托孤 rightMin 的右孩子）
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin; // 注意：内存中释放的是真实的替代节点 rightMin！
return true;
}

⭐ 语法细节与行为机制：

替换节点的选择：右子树的最左节点 rightMin 是整个右子树中的最小值，将其值覆盖到 cur 节点上，依然完全维持 BST“左小右大”的物理规则。

降维删除：由于 rightMin 是最左节点，它的左孩子必定为空（rightMin->_left == nullptr）。这使得对 rightMin 的删除完美降维转化成场景 1，只需托孤其右孩子 rightMin->_right 即可。

👔 面试常考避坑点：rightMinP 为什么必须初始化为 cur，而不能给 nullptr？

思考极端特例： 要删除根节点 8，其右孩子 10 刚好没有左孩子。 如图所示：

当代码执行 while (rightMin->_left) 时，因 10->_left == nullptr，循环一次都不进！

• 此时 rightMin 为 10。

• 如果将 rightMinP 初始化为 nullptr，循环不进导致 rightMinP 维持 nullptr。后续执行 rightMinP->_left 或 rightMinP->_right 时，会直接引发致命的空指针解引用崩溃（Segmentation Fault）！

• 将 rightMinP 初始化为 cur（8）：循环不进时 rightMinP 仍指向 8。代码走 else 分支：rightMinP->_right = rightMin->_right，正确把 8 的右指针挂接到了 14，逻辑完美闭环！

7.4 Erase 接口完整代码

bool Erase(const K& key)
{
Node* parent = nullptr; // 记录 cur 的父节点
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
{
// 匹配成功，按三大场景处理：

// 【场景 1】：cur 的左孩子为空
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;
}
// 【场景 2】：cur 的右孩子为空
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;
}
// 【场景 3】：cur 的左右孩子均不为空（替换法）
else
{
Node* rightMinP = cur; // 必须初始化为 cur，防止空指针解引用崩溃
Node* rightMin = cur->_right;

while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;
cur->_value = rightMin->_value;

if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin;
return true;
}
}
}
return false; // 未找到节点，删除失败
}

8. 辅助成员函数与封装策略

8.1 递归接口的私有封装策略

public:
// 公有无参外壳接口：解决外部对象无法获取私有 _root 指针的问题
void InOrder()
{
_InOrder(_root);
cout << endl;
}

private:
// 私有递归中序遍历辅助函数（左 -> 根 -> 右）
void _InOrder(Node* root)
{
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}

⭐ 语法细节与行为机制：

封装保护：_root 是类的私有成员，外部 main 函数无法获取 _root 指针。提供无参的公有 InOrder() 外壳，内部隐式传入私有 _root 调用递归辅助函数 _InOrder，极大地提升了类的封装性。

8.2 深拷贝构造与后序析构

public:
// 拷贝构造函数：调用前序深拷贝 Copy
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}

// 析构函数：调用后序销毁 Destroy
~BSTree()
{
Destroy(_root);
_root = nullptr;
}

private:
// 前序深拷贝：先开辟根节点，再递归复制左右子树
Node* Copy(Node* root)
{
if (root == nullptr) return nullptr;
Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}

// 后序销毁：先递归释放左右子树，最后释放根节点
void Destroy(Node* root)
{
if (root == nullptr) return;
Destroy(root->_left); // 先销毁左子树
Destroy(root->_right); // 再销毁右子树
delete root; // 最后释放根节点
}

⭐ 语法细节与行为机制：

前序深拷贝：按照“根 -> 左 -> 右”顺序，先开辟新根节点，再挂接深拷贝出的左右子树。

后序析构清理：按照“左 -> 右 -> 根”顺序，必须先递归释放子树资源，最后释放父节点，防止出现野指针与内存泄漏。

8.3 现代写法赋值重载

public:
// 现代写法赋值运算符重载
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}

⭐ 语法细节与行为机制：

传值触发自动拷贝：形参 t 采用按值传递（Pass-by-value），编译器会在传参时隐式调用拷贝构造函数，生成深拷贝的临时对象 t。

指针交换：通过 swap(_root, t._root) 交换当前对象的根指针与 t 的根指针，直接接管新树资源。

隐式自动释放旧资源：函数执行完毕退出作用域时，临时对象 t 自动调用析构函数，顺便清理掉当前对象交换过去的旧资源，具有强异常安全性。

9. 二叉搜索树完整 C++ 模板实现代码

以下是整合后的完整版代码（包含注释）：

#pragma once
#include <iostream>
#include <string>
using namespace std;

namespace key_value
{
// =========================================
// 1. 二叉搜索树节点结构体定义
// =========================================
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)
{}
};

// =========================================
// 2. 二叉搜索树类定义
// =========================================
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node; // 内部类型重命名，方便后续使用

public:
// C++11 显式指定生成默认构造函数
BSTree() = default;

// 拷贝构造函数：调用私有前序深拷贝函数 Copy 完成全树构建
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}

// 现代写法赋值运算符重载（Copy-and-Swap）
// 1. 传值形参 t 自动触发拷贝构造函数生成临时对象
// 2. 交换当前对象与 t 的 _root 根指针，直接接管新树资源
// 3. t 退出函数作用域时自动触发析构函数，清理掉当前对象原来的旧树节点
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this; // 返回当前对象的引用，支持连续赋值（a = b = c）
}

// 析构函数：调用私有后序递归销毁函数 Destroy 释放所有物理节点
~BSTree()
{
Destroy(_root); // 递归销毁全树节点
_root = nullptr; // 将根指针置为空，防止野指针解引用
}

// —————————————–
// 查找接口（Find）
// —————————————–
Node* Find(const K& key)
{
Node* cur = _root; // 定义遍历指针，默认指向根节点
while (cur)
{
if (cur->_key < key)
cur = cur->_right; // 目标 key 大于当前节点，向右子树搜索
else if (cur->_key > key)
cur = cur->_left; // 目标 key 小于当前节点，向左子树搜索
else
return cur; // 匹配成功，直接返回找到的节点指针
}
return nullptr; // 遍历遇到 nullptr 说明不存在，查找失败
}

// —————————————–
// 插入接口（Insert）
// —————————————–
bool Insert(const K& key, const V& value)
{
// 步骤 1：特判空树场景，新节点直接作为根节点
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}

Node* parent = nullptr; // 必须定义 parent 指针，用于实时追踪 cur 的上级节点
Node* cur = _root; // 查找落脚点的迭代指针

// 步骤 2：迭代寻找合适空落脚点，同时进行排重校验
while (cur)
{
if (cur->_key < key)
{
parent = cur; // 往下走之前记录当前节点为 parent
cur = cur->_right; // 比当前节点大，向右子树寻找
}
else if (cur->_key > key)
{
parent = cur; // 往下走之前记录当前节点为 parent
cur = cur->_left; // 比当前节点小，向左子树寻找
}
else
{
return false; // 树中已存在相同的 key，不允许冗余，插入失败
}
}

// 步骤 3：cur 此时到达 nullptr，new 出新节点并通过 parent 完成物理挂接
cur = new Node(key, value);
if (parent->_key < key)
parent->_right = cur; // 新 key 比 parent 大，挂在右孩子位置
else
parent->_left = cur; // 新 key 比 parent 小，挂在左孩子位置

return true; // 挂接成功，返回 true
}

// —————————————–
// 删除接口（Erase）
// —————————————–
bool Erase(const K& key)
{
Node* parent = nullptr; // 记录待删除节点 cur 的父节点
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
{
// 匹配到了待删除节点 cur，根据孩子数量分三大场景处理：

// 【场景 1】：cur 的左孩子为空（托孤右孩子）
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right; // 根节点特例：直接更新 _root 指向右孩子
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right; // cur 是左孩子，把 cur 的右孩子托孤给 parent 左侧
else
parent->_right = cur->_right; // cur 是右孩子，把 cur 的右孩子托孤给 parent 右侧
}
delete cur; // 释放 cur 节点的物理内存
return true;
}
// 【场景 2】：cur 的右孩子为空（托孤左孩子）
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left; // 根节点特例：直接更新 _root 指向左孩子
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left; // cur 是左孩子，把 cur 的左孩子托孤给 parent 左侧
else
parent->_right = cur->_left; // cur 是右孩子，把 cur 的左孩子托孤给 parent 右侧
}
delete cur; // 释放 cur 节点的物理内存
return true;
}
// 【场景 3】：cur 的左右孩子均不为空（替换法）
else
{
// 1. 寻找右子树最左节点 rightMin（即右子树最小值）
// 📌避坑要点：rightMinP 必须初始化为 cur！防范右孩子没有左孩子时（循环一次不进）导致的空指针解引用崩溃
Node* rightMinP = cur;
Node* rightMin = cur->_right;

while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left; // 迭代向左移动查找最小值
}

// 2. 数据覆盖：用替代节点的数据直接覆盖当前 cur 节点的数据
cur->_key = rightMin->_key;
cur->_value = rightMin->_value;

// 3. 物理销毁替代节点 rightMin（托孤其右孩子，因为 rightMin->_left 必为空）
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;

delete rightMin; // 内存中真实释放的是替换节点 rightMin
return true;
}
}
}
return false; // 未找到节点，删除失败
}

// —————————————–
// 中序遍历公有外壳接口（InOrder）
// —————————————–
void InOrder()
{
_InOrder(_root); // 隐式调用私有递归函数，自动传入私有 _root 指针
cout << endl;
}

private:
// 私有递归中序遍历辅助函数（左 -> 根 -> 右）
void _InOrder(Node* root)
{
if (root == nullptr) return;
_InOrder(root->_left); // 递归打印左子树
cout << root->_key << ":" << root->_value << endl; // 打印当前根节点
_InOrder(root->_right); // 递归打印右子树
}

// 私有递归后序销毁辅助函数（左 -> 右 -> 根）
void Destroy(Node* root)
{
if (root == nullptr) return;
Destroy(root->_left); // 先销毁左子树所有节点
Destroy(root->_right); // 再销毁右子树所有节点
delete root; // 最后释放当前根节点物理内存
}

// 私有递归前序深拷贝辅助函数（根 -> 左 -> 右）
Node* Copy(Node* root)
{
if (root == nullptr) return nullptr;
Node* newRoot = new Node(root->_key, root->_value); // 拷贝当前根节点
newRoot->_left = Copy(root->_left); // 递归深拷贝左子树并挂接
newRoot->_right = Copy(root->_right); // 递归深拷贝右子树并挂接
return newRoot; // 返回生成的新子树根指针
}

private:
Node* _root = nullptr; // 根节点指针，类内初始化赋初值 nullptr
};
}