【C++】带你手搓二叉搜索树(2w字详解)

Ne0inhk

— 33 min read
【C++】带你手搓二叉搜索树(2w字详解)

二叉搜索树

二叉搜索树

github地址

有梦想的电信狗

0. 前言

​ 在学习 C++ 的过程中，STL 容器 是我们最常用的工具之一，而这些容器的底层实现，往往依赖于 二叉搜索树（BST）及其变种。理解二叉搜索树不仅能帮助我们掌握 STL 的设计思想，还能加深对数据结构本质的理解与代码实现能力。

本文将带你从零开始，手搓一个 STL 风格的二叉搜索树，并逐步分析实现背后的逻辑与原理。

文章内容结构如下：

  • 基础定义 —— 了解二叉搜索树的性质与特点
  • 整体架构 —— 节点设计与树类的组织方式
  • 核心操作 —— 构造、析构、拷贝与赋值
  • 查找与插入 —— 迭代与递归两种实现思路
  • 遍历与删除 —— 中序遍历获取有序序列，复杂的删除逻辑拆解
  • 性能分析 —— 不同情况下的时间复杂度与效率瓶颈

通过本篇文章，你不仅可以 亲手实现一棵可用的二叉搜索树，还将为后续学习 AVL 树、红黑树等平衡二叉树 打下扎实的基础。

1. 二叉搜索树的定义

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

  • 若它的左子树不为空，则左子树上所有节点的值都小于其根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
  • ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义.
    • 后续学习的 map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中 map/set 不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2. 整体架构设计

结点设计

// 二叉搜索树template<classK>structBSTreeNode{BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key;};
  • 二叉搜索树常用于存储键值，方便查找关键字。因此我们的模板参数使用K来表示，结点内存放的数据为_key
  • 结点中的成员变量：
    • BSTreeNode* _left：指向左孩子的指针
    • BSTreeNode* _right：指向右孩子的指针
    • K _key：存储相应的的键值
  • 默认构造函数：
    • 将三个指针初始化为nullptr
    • 初始化数据_key为传入的值key
  • 结点采用struct设计，默认权限为public，方便下文的BSTree类访问成员

树结构设计

template<typenameK>classBSTree{typedef BSTreeNode<K> Node;public:// ...（以下为类的成员函数）private: Node* _root;};
  • BSTreeNode<K> 是模板节点，包含左右指针和键 _key。
  • BSTree<K> 以 _root 指向树根。类内 typedef BSTreeNode<K> Node; 简化后续代码书写。
  • 设计上采用裸指针管理节点（非智能指针），因此必须显式实现拷贝与析构，避免内存泄露。
  • 架构图如下：
在这里插入图片描述

3. 相关操作实现

1. 构造与析构

构造

public:BSTree():_root(nullptr){}
  • BSTree()：默认构造，构造一颗空树，只需将根节点指针 _root 置空即可

析构

public:~BSTree(){Destroy(_root);}private:// Destroy（后序删除）voidDestroy(Node*& root){if(root ==nullptr)return;// 二叉树的析构，走后序遍历删除Destroy(root->_left);Destroy(root->_right);delete root; root =nullptr;}
  • 由于析构函数无参数无返回值，而我们释放节点需要操作_root结点及其子节点管理的内存资源，因此无法通过传统传参递归的方式释放节点。
  • 我们设计了一个子函数，子函数完成结点的清理释放工作，析构函数直接调用子函数即可
  • 子函数void Destroy(Node*& root) ：后序遍历删除实现
    • 必须先释放左右子节点再释放父节点，因此我们采用后序遍历删除，依次递归释放左子树，右子树，最后释放根节点，这里和普通二叉树的释放结点操作相同
    • Node*& root 引用形式，函数栈帧中的形参root成为了每个节点的地址的别名。Node*& root 引用形式允许在删除左右子树后把父指针设为 nullptr，避免悬空指针。
    • 析构 ~BSTree()：调用 Destroy(_root) 做后序销毁，释放所有节点。

2. 拷贝构造与赋值

拷贝构造

public:BSTree(const BSTree<K>& tree):_root(nullptr){ _root =Copy(tree._root);}private: Node*Copy(Node* root){if(root ==nullptr)returnnullptr;else{ Node* newRoot =newNode(root->_key);// 分别递归拷贝 左右子树，拷贝完后，递归回去连接 newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}}
  • 这里和析构函数类似，利用子函数实现树的拷贝。
    • 原因是：拷贝构造函数的参数必须为const BSTree&类型，而我们拷贝树需要依次拷贝每个节点，递归拷贝节点时需要传入根节点作为参数。
  • 拷贝构造 BSTree(const BSTree<K>&)：先把 _root 初始化为 nullptr，再调用私有 Copy做深拷贝，_root接收返回的新树的根。这样可以保证两个树互不干扰。
  • Copy()函数的逻辑，整体逻辑采用递归实现：
    • 遇到非空结点，对该结点进行拷贝，新结点的指针保存在函数栈帧中
    • 再分别递归拷贝左子树、右子树
    • 遇到nullptr空结点时，向上级栈帧中返回结点的指针，完成结点的链接关系
  • 总结：
    • 递去时不断建立栈帧，拷贝结点
    • 归来，return时，向上级栈帧中返回所拷贝结点的指针

左子树的递归展开图如下：

在这里插入图片描述

operator=赋值

operator=的现代写法：

// t2 = t1public: BSTree<K>&operator=(BSTree<K> tmp){ std::swap(_root, tmp._root);return*this;}

赋值运算符 operator=(BSTree<K> tmp)重载：采用**拷贝-并-交换（copy-and-swap）**技巧：t2 = t1

  • 形参 tmp为值传递， 会调用拷贝构造生成一个局部副本（或借助移动语义），该副本 tmp 也为一个BSTree对象，和t1的内容完全一致，且有各自独立的数据空间。
  • std::swap(_root, tmp._root) 交换资源，更改管理资源的指针的指向，这样 tmp 的析构会自动释放旧资源。
  • 这种写法简洁且有异常安全性（strong exception guarantee）。
  • 以上写法可以类比之前vector中operator=的实现，只需要把_start指针换成这里的_root指针即可
在这里插入图片描述

3. 插入

迭代版插入

  • 默认插入的元素不能重复
// 插入时，需要先找到空位置boolinsert(const K& key){// 插入时为空树if(_root ==nullptr){ _root =newNode(key);returntrue;}// 不是空树时 Node* parent =nullptr; Node* curNode = _root;while(curNode !=nullptr){if(key > curNode->_key){ parent = curNode; curNode = curNode->_right;}elseif(key < curNode->_key){ parent = curNode; curNode = curNode->_left;}else{returnfalse;}}// 走完循环curNode 找到了可以插入的位置// 但要插入结点，必须修改父节点的指针，父节点并不知道key是比自己大还是自己小，只知道有一个结点需要插入// 因此要再比较一次 curNode =newNode(key);if(key > parent->_key) parent->_right = curNode;else parent->_left = curNode;returntrue;}

详细讲解（迭代插入逻辑）：

  • 插入时，需要先找到空位置，默认插入的元素不能重复
  1. 空树特判：若 _root == nullptr，直接把根设为新节点（new Node(key)）。
  2. 否则从 _root 向下查找插入位置：
    • 使用 curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。
    • 如果 key > curNode->_key，curNode沿右子树移动；key < curNode->_key时，curNode沿左子树移动。
    • 如果 key == curNode->_key，返回 false（二叉搜索树默认不允许重复键）。
  3. 当 curNode 走到 nullptr（找到空位）后，代表curNode已找到合适的可以插入的位置。
  4. new Node(key) 建节点
    • 要插入新结点，必须修改curNode的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置
    • 因此要根据 key 与 parent->_key 的比较把它接为左/右子节点。
      • 如果 key > parent->_key → 插到右边 (parent->_right = newNode)
      • 如果 key < parent->_key → 插到左边 (parent->_left = newNode)
  • 总结：✔️ 循环结束时，位置已经找到了，就是 curNode == nullptr 的地方。
    ✔️ 但是插入操作不能直接修改 curNode，必须通过 parent 去改指针。
    ✔️ 而 parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。

关键点与陷阱：

  • curNode 用来遍历，parent 跟随；这是常见的迭代插入模式。
  • 新节点分配后必须从父节点parent链入整棵树
  • 不允许重复键

递归插入

public:boolinsert_R(const K& key){return_insert_R(_root, key);}private:bool_insert_R(Node*& root,const K& key){// 走到空的地方，可以开始插入了// 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用if(root ==nullptr){ root =newNode(key);returntrue;}if(key < root->_key)return_insert_R(root->_left, key);elseif(key > root->_key)return_insert_R(root->_right, key);elsereturnfalse;}

要点：

  • _insert_R 的参数是 Node*& root（对指针的引用），这使得当 root 为 nullptr 时可以直接写 root = new Node(key); 来修改父节点的指针，而不需要再记录父节点再通过父节点的比较完成结点的插入，简化了父指针的管理。
  • 按照二叉搜索树的规则，递归插入：
    • key < root->_key时，return _insert_R(root->_left, key)递归去左子树中插入
    • key > root->_key时，return _insert_R(root->_right, key)递归去右子树中插入
    • ==时返回false，键不允许重复

递归与迭代的复杂度比较（两种方式相同）：

  • 时间复杂度：
    • 平均为 O(h)，其中 h 为树的高度；
    • 若树退化为链表（完全不平衡），退化到 O(n)。
  • 空间复杂度：
    • （递归版）额外为递归栈深度 O(h)，其中 h 为树的高度；

4. 查找

迭代查找：

boolfind(const K& key)const{ Node* curNode = _root;while(curNode){if(key == curNode->_key)returntrue;elseif(key > curNode->_key) curNode = curNode->_right;else curNode = curNode->_left;}// 循环结束时，循环内没有返回，代表没有找到，返回falsereturnfalse;}
  • 标准 BST 查找：从根出发比较，curNode = _root，curNode从根节点出发开始找，按照二叉搜索树的性质查找即可
  • curNode 表示当前结点，curNode的移动结合了二叉搜树的性质：
    • key == curNode->_key时，成功，返回true
    • key > curNode->_key时，curNode去右子树查找
    • key < curNode->_key时，curNode去左子树查找
  • 循环结束时，若循环内没有返回，代表没有找到，则循环外返回false

递归查找：

public:boolfind_R(const K& key)const{return_find_R(_root, key);}private:bool_find_R(const Node* root,const K& key)const{if(root ==nullptr)returnfalse;if(key < root->_key)return_find_R(root->_left, key);elseif(key > root->_key)return_find_R(root->_right, key);// 不大于，不小于 表明查找成功elsereturntrue;}
  • 递归版本自然表达了 BST 的定义：
    • 若查找到为空结点，表明查找失败
  • key > 当前节点的_key时，递归去右子树查找
  • key < 当前节点的_key时，递归去左子树查找
  • 不大于，不小于时，表明查找成功，返回true
  • 参数 const Node* 保证不会修改树。

5. 中序遍历

由二叉搜索树的性质可得，对二叉搜索树进行中序遍历，可以得到升序序列

中序遍历可以用于升序打印 BST 中的键。代码如下：

public:voidInorder()const{_Inorder(_root);printf("\n");}private:void_Inorder(Node* root = _root)const{if(root ==nullptr){return;}_Inorder(root->_left); cout << root->_key <<" ";_Inorder(root->_right);}

要点：

  • 利用子函数实现中序遍历即可
  • _Inorder 是典型的递归中序：左 - 根 - 右。
  • 对 BST 做中序遍历会得到有序（从小到大）序列，这也是 BST 在排序/输出上的常见用途。
  • 注意：_Inorder 写成 void _Inorder(Node* root = _root) const，默认参数指向成员 _root，调用Inorder()默认从根节点开始遍历

6. 删除

迭代删除

  • 删除时，需要先走查找的逻辑，找到要被删除的节点：
boolerase(const K& key){ Node* parent =nullptr; Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while(curNode){// 先找要被删除的节点if(key > curNode->_key){ parent = curNode; curNode = curNode->_right;}elseif(key < curNode->_key){ parent = curNode; curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else{// ... 删除的逻辑}}// 没找到 return falsereturnfalse;}
在这里插入图片描述
在这里插入图片描述
情况一
在这里插入图片描述
// 找到后的删除逻辑else{// 情况一// curNode 的左为空if(curNode->_left ==nullptr){// 特殊情况，左为空且curNode 为_rootif(curNode == _root) _root = curNode->_right;// 托孤，需要知道孤儿 应该成为 父节点的左子树还是右子树, 需要先找孤儿在左右那个子树// 孤儿在左子树elseif(curNode == parent->_left){ parent->_left = curNode->_right;}// 孤儿在右子树else{ parent->_right = curNode->_right;}delete curNode;returntrue;}// 情况二 ...// 情况三 ... returntrue;}
  • 左子树为空（curNode->_left == nullptr）：
    • 如果该节点是根：_root = curNode->_right;
    • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点curNode->_right（托孤），再 delete curNode。
    • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。
情况二
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
// 找到后的删除逻辑else{// 情况一 ...// 情况二 ...// curNode 的右为空elseif(curNode->_right ==nullptr){if(curNode == _root) _root = curNode->_left;// 托孤// 当前结点是父的左节点elseif(curNode == parent->_left){ parent->_left = curNode->_left;}// 当前结点是父的右节点else{ parent->_right = curNode->_left;}delete curNode;returntrue;}// 情况三 ... returntrue;}
  • 右子树为空（curNode->_right == nullptr）：
    • 与左子树为空时对称：
    • 如果该节点是根：_root = curNode->_left;
    • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_left（托孤），再 delete curNode。
    • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。
情况三
在这里插入图片描述
  • 情况三的删除逻辑，替换法
在这里插入图片描述
  • 需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点
    • 二叉搜索树中：
      • 子树的最大结点，是树中最右边的结点
      • 子树的最小结点，是树中最左边的结点
  • 这里找左子树中最大的结点
// 找到后的删除逻辑else{// 情况一 ... // 情况二 ... // 情况三 ...// curNode的左右都不为空，需要在树中找一个结点替换curNodeelse{// 找左子树中最大的结点 Node* maxNode = curNode->_left; Node* maxParent = curNode;// 有可能进不去while循环，对应于删除时的 else 条件// 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合while(maxNode->_right !=nullptr){ maxParent = maxNode; maxNode = maxNode->_right;}// 循环结束后，maxNode为左子树中最大的结点 curNode->_key = maxNode->_key;// 替换值// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if(maxNode == maxParent->_right){ maxParent->_right = maxNode->_left;}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else{// maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;}delete maxNode;}returntrue;}
  • 左右子树皆非空：
    • 用左子树中的最大节点或右子树中的最小节点替换当前节点的值，然后删除左子树中的最大节点或右子树中的最小节点
    • 本代码选择用左子树的最大节点 maxNode替换curNode（即向左一次再一路向右走到最右）。
    • 找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key替换curNode中的值，然后把 maxNode 从树上摘除：
      • maxNode是左子树的最大值，因此maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParent
      • 且maxNode既可能是maxParent的左节点，也可能是maxParent的右节点，如下图所示(假设删除3)，两图中最大值都为2，分别是maxParent的右孩子和左孩子
    • 托孤的代码：
    • 托孤需要确认孤儿结点是在parent的左子树还是右子树，正确托孤后释放结点
// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if(maxNode == maxParent->_right){ maxParent->_right = maxNode->_left;// 托孤}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else{// maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;// 托孤}delete maxNode;
在这里插入图片描述
完整代码与逐步说明
boolerase(const K& key){ Node* parent =nullptr; Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while(curNode){// 先找要被删除的节点if(key > curNode->_key){ parent = curNode; curNode = curNode->_right;}elseif(key < curNode->_key){ parent = curNode; curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else{// curNode 的左为空if(curNode->_left ==nullptr){// 特殊情况，左为空且curNode 为_rootif(curNode == _root) _root = curNode->_right;// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树// 需要先找孤儿在左右那个子树// 孤儿在左子树elseif(curNode == parent->_left){ parent->_left = curNode->_right;}// 孤儿在左子树else{ parent->_right = curNode->_right;}delete curNode;returntrue;}// curNode 的右为空elseif(curNode->_right ==nullptr){if(curNode == _root) _root = curNode->_left;// 托孤// 当前结点是父的左节点elseif(curNode == parent->_left){ parent->_left = curNode->_left;}// 当前结点是父的右节点else{ parent->_right = curNode->_left;}delete curNode;returntrue;}// curNode的左右都不为空，需要在树中找一个结点替换curNodeelse{// 需要找左子树中最大的、或右子树中最小的替换当前结点// 二叉搜索树中，子树的最大结点，是树中最右边的结点// 子树的最小结点，是树中最左边的结点// 这里找左子树中最大的结点 Node* maxNode = curNode->_left; Node* maxParent = curNode;// 有可能进不去while循环，对应于删除时的 else 条件// 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合while(maxNode->_right !=nullptr){ maxParent = maxNode; maxNode = maxNode->_right;}// 循环结束后，maxNode为左子树中最大的结点 curNode->_key = maxNode->_key;// 替换值// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if(maxNode == maxParent->_right){ maxParent->_right = maxNode->_left;}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else{// maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;}delete maxNode;}returntrue;}}returnfalse;}
  • 左子树为空（curNode->_left == nullptr）：
    • 如果该节点是根：_root = curNode->_right;
    • 否则根据 curNode 是父节点的左/右孩子，把父指针指向 curNode->_right（托孤），再 delete curNode。
    • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。
  • 右子树为空（curNode->_right == nullptr）：
    • 与左子树为空时对称：
    • 如果该节点是根：_root = curNode->_left;
    • 否则根据 curNode 是父节点的左/右孩子，把父指针指向 curNode->_left（托孤），再 delete curNode。
    • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）
  • 左右子树皆非空：
    • 需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点
      • 二叉搜索树中：
        • 子树的最大结点，是树中最右边的结点
        • 子树的最小结点，是树中最左边的结点
    • 这里找左子树中最大的结点
    • 用左子树中的最大节点或右子树中的最小节点替换当前节点的值，然后删除左子树中的最大节点或右子树中的最小节点
    • 本代码选择用左子树的最大节点 maxNode替换curNode（即向左一次再一路向右走到最右）。
    • 找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key替换curNode中的值，然后把 maxNode 从树上摘除：
      • maxNode是左子树的最大值，因此maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParent
      • 且maxNode既可能是maxParent的左节点，也可能是maxParent的右节点
    • 托孤的代码：
    • 托孤需要确认孤儿结点是在parent的左子树还是右子树，正确托孤后释放结点
  • while循环结束后，代表三种情况中都未完成删除，返回false
// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if(maxNode == maxParent->_right){ maxParent->_right = maxNode->_left;// 托孤}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else{// maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;// 托孤}delete maxNode;

递归删除

完整代码：

public:boolerase_R(const K& key){return_erase_R(_root, key);}private:bool_erase_R(Node*& root,const K& key){if(root ==nullptr)returnfalse;if(key > root->_key)return_erase_R(root->_right, key);elseif(key < root->_key)return_erase_R(root->_left, key);// 相等时要删除else{ Node* delNode = root;// 1. curNode 左为空if(root->_left ==nullptr){ root = root->_right;}// 2. curNode 右为空elseif(root->_right ==nullptr){ root = root->_left;}// 3. curNode 左右都不为空else{// 找左子树中最大的结点 Node* maxNode = root->_left;while(maxNode->_right){ maxNode = maxNode->_right;} std::swap(maxNode->_key, root->_key);// 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空// 再去左子树中删除一遍return_erase_R(root->_left, key);}delete delNode;returntrue;}}

代码中查找的逻辑依然需要：

  • root == nullptr时，返回false
  • key > root->_key时，递归去右子树中查找
  • key < root->_key时，递归去左子树中查找
  • else代表相等，查找到了要被删除的结点
bool_erase_R(Node*& root,const K& key){if(root ==nullptr)returnfalse;if(key > root->_key)return_erase_R(root->_right, key);elseif(key < root->_key)return_erase_R(root->_left, key);// 相等时要删除else{// ...}}

else中的删除代码：

// 相等时要删除else{ Node* delNode = root;// 这里 写成 curNode 是为了和迭代删除法的形式匹配// 1. curNode 左为空if(root->_left ==nullptr){ root = root->_right;}// 2. curNode 右为空elseif(root->_right ==nullptr){ root = root->_left;}// 3. curNode 左右都不为空else{// 找左子树中最大的结点 Node* maxNode = root->_left;while(maxNode->_right){ maxNode = maxNode->_right;} std::swap(maxNode->_key, root->_key);// 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空// 再去左子树中删除一遍return_erase_R(root->_left, key);}delete delNode;returntrue;}
  • 参数 Node*& root 是==对结点指针的直接引用==，使得当我们把 root 指向 root->_right（或 _left）时，父节点相应的指针会被更新（递归中直接修改）。
  • 删除时前两种情况的思路依然是托孤，第三种采用替换法：
    • Node*& root 是==对结点指针的直接引用==，托孤时无需记录parent指针，可以直接对其修改
      • 若其左子树为空，将 root 指向 root->_right（托孤），再 delete delNode。
      • 若其右子树为空，类似处理。
      • 若左右都不为空：找到左子树最大节点 maxNode，交换值（swap），然后在左子树递归删除原来持有该值的那个节点。
    • 递归的本质：
      1. 交换 key
        • root 是要被删除的结点，但它有左右孩子，不能直接删。
        • 于是我们找到左子树中最大的结点 maxNode，把 root->_key 和 maxNode->_key 交换。
        • 这样 逻辑上相当于“把删除任务转移到了 maxNode”。
      2. 为什么 maxNode 一定能删除？
        • maxNode 是左子树中最大的结点，所以它 不可能有右子树（因为再往右就超过它了）。
        • 它可能有左孩子，也可能没有。
        • 这就转化成了 情况1 或 情况2（更简单的删除）。
      3. 递归删除
        • 因为 root->_key 已经被换成了 maxNode->_key，那么树里相当于有两个相同的 key。
        • 所以我们递归到 root->_left 去 继续删除 key。
        • 最终会定位到 maxNode，并用情况1或2把它删掉。
  • 递归删除写法短小且清晰，利用引用参数避免手工维护父节点 parent。
  • 👉 总结一句话：
    第三种情况的递归逻辑就是：把当前结点和左子树最大结点交换，让删除目标转移到最大结点，然后递归在左子树中删除这个目标。最终会简化成情况1或2。

4. 性能分析

  • 查找 / 插入 / 删除（平均）时间复杂度：O(h)，h 为树高。
  • 空间：迭代版本额外 O(1)；递归版本额外 O(h) 递归栈。
  • 拷贝构造/Copy: O(n) 时间与 O(h) 递归栈。
在这里插入图片描述

结点数为N的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。

  • 最优情况下：⼆叉搜索树为完全⼆叉树(或者接近完全二叉树)，其高度为： log2 N
  • 最差情况下：⼆叉搜索树（退化为单链表），其高度为： N

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

那么这样的效率显然是⽆法满⾜我们需求的，后续会学习⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据高性能需求。

⼆分查找也可以实现 O(log2 N) 级别的查找效率，但是⼆分查找有两⼤缺陷：

  • 需要存储在⽀持下标随机访问的结构中，并且有序。
  • 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

5. 完整实现代码

// 二叉搜索树template<classK>structBSTreeNode{//typedef BSTreeNode<K> Node;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key;};template<typenameK>classBSTree{typedef BSTreeNode<K> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& tree):_root(nullptr){ _root =Copy(tree._root);}// 现在写法的赋值// t2 = t1 BSTree<K>&operator=(BSTree<K> tmp){ std::swap(_root, tmp._root);return*this;}~BSTree(){Destroy(_root);}// 插入时，找到一个空位置插入即可 默认插入的元素不能重复boolinsert(const K& key){// 插入时为空树if(_root ==nullptr){ _root =newNode(key);returntrue;}// 不是空树时 Node* parent =nullptr; Node* curNode = _root;while(curNode !=nullptr){if(key > curNode->_key){ parent = curNode; curNode = curNode->_right;}elseif(key < curNode->_key){ parent = curNode; curNode = curNode->_left;}else{returnfalse;}}// 走到这里，意味着curNode已经找到了位置,此时curNode为nullptr// parent 为curNode的父节点// curNode 为 结点指针的拷贝，修改curNode不能修改结点指针的指向//走完循环curNode 找到了可以插入的位置// 但要插入结点，必须修改父节点的指针，父节点并不知道key是比自己大还是自己小，只知道下面可以插// 因此要再比较一次 curNode =newNode(key);if(key > parent->_key){ parent->_right = curNode;}else parent->_left = curNode;returntrue;// key不可能等于parent->_key 否则上面的循环就是错误的/*else { return false; }*/}voidInorder()const{_Inorder(_root);printf("\n");}boolfind(const K& key)const{ Node* curNode = _root;while(curNode){if(key == curNode->_key)returntrue;elseif(key > curNode->_key) curNode = curNode->_right;else curNode = curNode->_left;}returnfalse;}// 这里不能用引用代替指针，因为指针可以改变指向，引用一旦绑定，指向不可修改boolerase(const K& key){ Node* parent =nullptr; Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while(curNode){// 先找要被删除的节点if(key > curNode->_key){ parent = curNode; curNode = curNode->_right;}elseif(key < curNode->_key){ parent = curNode; curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else{// curNode 的左为空if(curNode->_left ==nullptr){// 特殊情况，左为空且curNode 为_rootif(curNode == _root) _root = curNode->_right;// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树// 需要先找孤儿在左右那个子树// 孤儿在左子树elseif(curNode == parent->_left){ parent->_left = curNode->_right;}// 孤儿在左子树else{ parent->_right = curNode->_right;}delete curNode;returntrue;}// curNode 的右为空elseif(curNode->_right ==nullptr){if(curNode == _root) _root = curNode->_left;// 托孤// 当前结点是父的左节点elseif(curNode == parent->_left){ parent->_left = curNode->_left;}// 当前结点是父的右节点else{ parent->_right = curNode->_left;}delete curNode;returntrue;}// curNode的左右都不为空，需要在树中找一个结点替换curNodeelse{// 需要找左子树中最大的、或右子树中最小的替换当前结点// 二叉搜索树中，子树的最大结点，是树中最右边的结点// 子树的最小结点，是树中最左边的结点// 这里找左子树中最大的结点 Node* maxNode = curNode->_left; Node* maxParent = curNode;// 有可能进不去while循环，对应于删除时的 else 条件// 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合while(maxNode->_right !=nullptr){ maxParent = maxNode; maxNode = maxNode->_right;}// 循环结束后，maxNode为左子树中最大的结点 curNode->_key = maxNode->_key;// 替换值// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if(maxNode == maxParent->_right){ maxParent->_right = maxNode->_left;}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else{// maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;}delete maxNode;//Node* maxNode = curNode->_left;//Node* maxParent = curNode;//while (maxNode->_right != nullptr) {// maxParent = maxNode;// maxNode = maxNode->_right;//}// 循环结束后，maxNode为左子树中最大的结点//std::swap(maxNode->_key, curNode->_key);//delete maxNode;//maxParent->_right = nullptr; // 错误逻辑}returntrue;}}returnfalse;}// find函数的递归版本// 写了一个子函数，因为递归需要用到Private成员_root，来控制递归子树的分支// 如果不写子函数，需要对外提供一个getRoot供调用者使用boolfind_R(const K& key)const{return_find_R(_root, key);}boolinsert_R(const K& key){return_insert_R(_root, key);}boolerase_R(const K& key){return_erase_R(_root, key);}private: Node*Copy(Node* root){if(root ==nullptr)returnnullptr;else{ Node* newRoot =newNode(root->_key);// 分别递归拷贝 左右子树，拷贝完后，递归回去连接 newRoot->_left =Copy(root->_left); newRoot->_right =Copy(root->_right);return newRoot;}}voidDestroy(Node*& root){if(root ==nullptr)return;// 二叉树的析构，走后序遍历删除Destroy(root->_left);Destroy(root->_right);delete root; root =nullptr;}void_Inorder(Node* root = _root)const{if(root ==nullptr){return;}_Inorder(root->_left); cout << root->_key <<" ";_Inorder(root->_right);}bool_find_R(const Node* root,const K& key)const{if(root ==nullptr)returnfalse;if(key < root->_key)return_find_R(root->_left, key);elseif(key > root->_key)return_find_R(root->_right, key);// 不 < 不 > 表明查找成功elsereturntrue;}// 这里参数root加引用，修改指针bool_insert_R(Node*& root,const K& key){// 走到空的地方，可以开始插入了// 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用if(root ==nullptr){ root =newNode(key);returntrue;}if(key < root->_key)return_insert_R(root->_left, key);elseif(key > root->_key)return_insert_R(root->_right, key);elsereturnfalse;}bool_erase_R(Node*& root,const K& key){if(root ==nullptr)returnfalse;if(key > root->_key)return_erase_R(root->_right, key);elseif(key < root->_key)return_erase_R(root->_left, key);// 相等时要删除else{ Node* delNode = root;// 这里的 root 等价于 curNode，写成curNode是为了和迭代删除法的形式匹配// 1. curNode 左为空if(root->_left ==nullptr){ root = root->_right;}// 2. curNode 右为空elseif(root->_right ==nullptr){ root = root->_left;}// 3. curNode 左右都不为空else{// 找左子树中最大的结点 Node* maxNode = root->_left;while(maxNode->_right){ maxNode = maxNode->_right;} std::swap(maxNode->_key, root->_key);// 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空// 再去左子树中删除一遍return_erase_R(root->_left, key);//return _erase_R(maxNode, key); // 不能这么写}delete delNode;returntrue;}}private: Node* _root;};

6. 结语

通过本文的实现，我们完整梳理了二叉搜索树的设计与核心操作：

  • 从结点与树的架构设计入手，逐步实现了 构造/析构、拷贝与赋值；
  • 结合 迭代与递归 两种思路，详细探讨了 插入、查找、中序遍历、删除 的实现细节与关键陷阱；
  • 最后分析了二叉搜索树在不同情况下的性能表现，并指出了其在退化时的效率瓶颈。

二叉搜索树作为最基础的树形数据结构，是理解 AVL 树、红黑树等平衡二叉树 的起点。掌握 BST 的实现，不仅能加深对 STL 底层的理解，也能为后续学习更复杂的数据结构打下坚实的基础。

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀

Read more

几小时完成生鲜配送系统！飞算JavaAI专业版：智能引导+两大工具承包开发全流程

作为一名Java开发者，我曾无数次被「需求拆解难、后期调试烦」的问题困住，最近面对一个生鲜配送系统的开发需求，光梳理业务逻辑、设计表结构就要耗上大半天，后续还要花时间处理代码规范、依赖冲突，往往一周才能拿出可运行的项目。直到试用了飞算JavaAI专业版，才发现AI辅助开发能如此高效：借助它的智能引导系统和两大核心AI工具，我从需求输入到项目初步完成仅需几小时，大大节省了我的时间。 智能引导五步法：让模糊需求快速落地 做生鲜配送系统前，我的需求很简单：「支持用户下单、订单跟踪、配送员调度、库存管理」，但具体怎么拆分模块、设计接口完全没头绪。放在以前，至少要花1天时间和产品经理对接需求文档，而飞算JavaAI的智能引导系统，直接帮我把模糊需求变成了标准化的开发方案。 第一步「理解需求」就超出预期。我在输入框写下核心诉求后，系统10秒内就拆解出几个关键点，还补充了我没考虑到很多功能——比如当生鲜商品临近保鲜期时，系统会自动触发库存预警，异常订单（如地址不明确、支付超时）会自动分流处理，简直像有个资深行业顾问在补位。 第二步「设计接口」根据我的需求创建了繁多的接口供我选择，并且可

By Ne0inhk
【Java 开发日记】阻塞队列有哪些？拒绝策略有哪些？

【Java 开发日记】阻塞队列有哪些？拒绝策略有哪些？

目录 阻塞队列有哪些？ 拒绝策略有哪些？ 面试回答 阻塞队列有哪些？ 在Java的java.util.concurrent包里面，阻塞队列的实现挺多的，我们可以根据它的功能和结构来记，主要分这么几类： 1. 按容量划分： * 有界队列： 就是队列有固定的容量。 * ArrayBlockingQueue： 最经典的一个，底层是数组，创建时必须指定大小。它的生产和消费用同一把锁，性能相对稳定。 * LinkedBlockingQueue： 底层是链表，它既可以是有界的（构造时指定容量），也可以默认是无界的（默认是Integer.MAX_VALUE，几乎相当于无界）。它的生产和消费用了两把锁，在高并发场景下吞吐量通常比ArrayBlockingQueue更高。 * 无界队列： 理论上是无限的，只要内存够就能一直放。 * PriorityBlockingQueue： 一个支持优先级排序的无界队列。元素必须实现Comparable接口，或者构造时传入Comparator。它出队的顺序是按优先级来的，不是先进先出 * DelayQueue： 一个很特殊的队

By Ne0inhk
Java 大视界 -- 基于 Java+Storm 构建实时日志分析平台：从日志采集到告警可视化（440）

Java 大视界 -- 基于 Java+Storm 构建实时日志分析平台：从日志采集到告警可视化（440）

Java 大视界 -- 基于 Java+Storm 构建实时日志分析平台：从日志采集到告警可视化（440） * 引言： * 正文： * 一、实时日志分析平台的核心架构设计 * 1.1 架构分层与核心组件 * 1.2 组件选型的实战思考（10 余年经验沉淀，数据真实有出处） * 二、日志采集层：Flume 的高可用配置（生产级优化） * 2.1 Flume 的核心配置（抗住十万级 / 秒流量，注释完整） * 2.2 Flume 的高可用部署（避免单点故障，实战步骤清晰） * 2.2.1 多 Agent 冗余部署 * 2.2.2 Nginx

By Ne0inhk
若依（RuoYi）框架升级适配 JDK 21 和 SpringBoot 3.5.10

若依（RuoYi）框架升级适配 JDK 21 和 SpringBoot 3.5.10

技术迭代新高度，若依框架焕新升级 作为国内开发者广泛使用的开源快速开发框架，若依（RuoYi）始终紧跟技术前沿，为企业级应用开发提供高效、稳定的底层支撑。近日，若依框架完成核心技术栈的重磅升级 —— 全面适配 JDK 21 长期支持版本（LTS）与 SpringBoot 3.5.10 稳定版，为开发者带来更高效、更安全、更适配未来的开发体验。 一、核心升级：适配 JDK 21 + SpringBoot 3.5.10，解锁技术新能力 1. JDK 21 LTS 适配：性能与安全双重提升 JDK 21 作为 Java 官方长期支持版本，带来了虚拟线程、字符串模板、密封类等重磅特性，相比传统 JDK

By Ne0inhk