C++ 二叉搜索树设计与实现详解

3. 相关操作实现

1. 构造与析构

构造

public:
BSTree() : _root(nullptr) {}

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

析构

public:
~BSTree() { Destroy(_root); }
private:
// Destroy（后序删除）
void Destroy(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) return nullptr;
    else {
        Node* newRoot = new Node(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 空结点时，向上级栈帧中返回结点的指针，完成结点的链接关系

operator=赋值

operator= 的现代写法：

// t2 = t1
public: 
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. 插入

迭代版插入

• 默认插入的元素不能重复

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

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

• 插入时，需要先找到空位置，默认插入的元素不能重复

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:
bool insert_R(const K& key) {
    return _insert_R(_root, key);
}
private:
bool _insert_R(Node*& root, const K& key) {
    // 走到空的地方，可以开始插入了
    // 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用
    if (root == nullptr) {
        root = new Node(key);
        return true;
    }
    if (key < root->_key)
        return _insert_R(root->_left, key);
    else if (key > root->_key)
        return _insert_R(root->_right, key);
    else
        return false;
}

要点：

• _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. 查找

迭代查找：

bool find(const K& key) const {
    Node* curNode = _root;
    while (curNode) {
        if (key == curNode->_key)
            return true;
        else if (key > curNode->_key)
            curNode = curNode->_right;
        else
            curNode = curNode->_left;
    }
    // 循环结束时，循环内没有返回，代表没有找到，返回 false
    return false;
}

• 标准 BST 查找：从根出发比较，curNode = _root，curNode从根节点出发开始找，按照二叉搜索树的性质查找即可
• curNode 表示当前结点，curNode 的移动结合了二叉搜树的性质：
  • key == curNode->_key 时，成功，返回 true
  • key > curNode->_key 时，curNode 去右子树查找
  • key < curNode->_key 时，curNode 去左子树查找
• 循环结束时，若循环内没有返回，代表没有找到，则循环外返回 false

递归查找：

public:
bool find_R(const K& key) const {
    return _find_R(_root, key);
}
private:
bool _find_R(const Node* root, const K& key) const {
    if (root == nullptr)
        return false;
    if (key < root->_key)
        return _find_R(root->_left, key);
    else if (key > root->_key)
        return _find_R(root->_right, key);
    // 不大于，不小于 表明查找成功
    else
        return true;
}

• 递归版本自然表达了 BST 的定义：
  • 若查找到为空结点，表明查找失败
• key > 当前节点的_key 时，递归去右子树查找
• key < 当前节点的_key 时，递归去左子树查找
• 不大于，不小于时，表明查找成功，返回 true
• 参数 const Node* 保证不会修改树。

5. 中序遍历

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

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

public:
void Inorder() 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. 删除

迭代删除

• 删除时，需要先走查找的逻辑，找到要被删除的节点：

bool erase(const K& key) {
    Node* parent = nullptr;
    Node* curNode = _root;
    // _root 为空时，进不去 while 循环，会直接 return false
    while (curNode) {
        // 先找要被删除的节点
        if (key > curNode->_key) {
            parent = curNode;
            curNode = curNode->_right;
        } else if (key < curNode->_key) {
            parent = curNode;
            curNode = curNode->_left;
        }
        // 找到了，找到了，删除分为三种情况
        else {
            // ... 删除的逻辑
        }
    }
    // 没找到
    return false;
}

情况一：左子树为空

// 找到后的删除逻辑
else {
    // 情况一
    // curNode 的左为空
    if (curNode->_left == nullptr) {
        // 特殊情况，左为空且 curNode 为_root
        if (curNode == _root)
            _root = curNode->_right;
        // 托孤，需要知道孤儿 应该成为 父节点的左子树还是右子树，需要先找孤儿在左右那个子树
        // 孤儿在左子树
        else if (curNode == parent->_left)
            parent->_left = curNode->_right;
        // 孤儿在右子树
        else
            parent->_right = curNode->_right;
        delete curNode;
        return true;
    }
    // 情况二 ...
    // 情况三 ...
    return true;
}

• 左子树为空（curNode->_left == nullptr）：
  • 如果该节点是根：_root = curNode->_right;
  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_right（托孤），再 delete curNode。
  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。

情况二：右子树为空

// 找到后的删除逻辑
else {
    // 情况一 ...
    // 情况二 ...
    // curNode 的右为空
    else if (curNode->_right == nullptr) {
        if (curNode == _root)
            _root = curNode->_left;
        // 托孤
        // 当前结点是父的左节点
        else if (curNode == parent->_left)
            parent->_left = curNode->_left;
        // 当前结点是父的右节点
        else
            parent->_right = curNode->_left;
        delete curNode;
        return true;
    }
    // 情况三 ...
    return true;
}

• 右子树为空（curNode->_right == nullptr）：
  • 与左子树为空时对称：
  • 如果该节点是根：_root = curNode->_left;
  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_left（托孤），再 delete curNode。
  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。

情况三：左右子树皆非空

• 情况三的删除逻辑，替换法

• 需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点

  • 二叉搜索树中：
    • 子树的最大结点，是树中最右边的结点
    • 子树的最小结点，是树中最左边的结点

• 这里找左子树中最大的结点

// 找到后的删除逻辑
else {
    // 情况一 ... 
    // 情况二 ... 
    // 情况三 ...
    // curNode 的左右都不为空，需要在树中找一个结点替换 curNode
    else {
        // 找左子树中最大的结点
        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;
    }
    return true;
}

• 左右子树皆非空：
  • 用左子树中的最大节点或右子树中的最小节点替换当前节点的值，然后删除左子树中的最大节点或右子树中的最小节点
  • 本代码选择用左子树的最大节点 maxNode 替换 curNode（即向左一次再一路向右走到最右）。
  • 找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key 替换 curNode 中的值，然后把 maxNode 从树上摘除：
    • maxNode 是左子树的最大值，因此 maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParent
    • 且 maxNode 既可能是 maxParent 的左节点，也可能是 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;

完整代码与逐步说明

bool erase(const K& key) {
    Node* parent = nullptr;
    Node* curNode = _root;
    // _root 为空时，进不去 while 循环，会直接 return false
    while (curNode) {
        // 先找要被删除的节点
        if (key > curNode->_key) {
            parent = curNode;
            curNode = curNode->_right;
        } else if (key < curNode->_key) {
            parent = curNode;
            curNode = curNode->_left;
        }
        // 找到了，找到了，删除分为三种情况
        else {
            // curNode 的左为空
            if (curNode->_left == nullptr) {
                // 特殊情况，左为空且 curNode 为_root
                if (curNode == _root)
                    _root = curNode->_right;
                // 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树
                // 需要先找孤儿在左右那个子树
                // 孤儿在左子树
                else if (curNode == parent->_left)
                    parent->_left = curNode->_right;
                // 孤儿在左子树
                else
                    parent->_right = curNode->_right;
                delete curNode;
                return true;
            }
            // curNode 的右为空
            else if (curNode->_right == nullptr) {
                if (curNode == _root)
                    _root = curNode->_left;
                // 托孤
                // 当前结点是父的左节点
                else if (curNode == parent->_left)
                    parent->_left = curNode->_left;
                // 当前结点是父的右节点
                else
                    parent->_right = curNode->_left;
                delete curNode;
                return true;
            }
            // curNode 的左右都不为空，需要在树中找一个结点替换 curNode
            else {
                // 需要找左子树中最大的、或右子树中最小的替换当前结点
                // 二叉搜索树中，子树的最大结点，是树中最右边的结点
                // 子树的最小结点，是树中最左边的结点
                // 这里找左子树中最大的结点
                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;
            }
            return true;
        }
    }
    return false;
}

• 左子树为空（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:
bool erase_R(const K& key) {
    return _erase_R(_root, key);
}
private:
bool _erase_R(Node*& root, const K& key) {
    if (root == nullptr)
        return false;
    if (key > root->_key)
        return _erase_R(root->_right, key);
    else if (key < root->_key)
        return _erase_R(root->_left, key);
    // 相等时要删除
    else {
        Node* delNode = root;
        // 1. curNode 左为空
        if (root->_left == nullptr) {
            root = root->_right;
        }
        // 2. curNode 右为空
        else if (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;
        return true;
    }
}

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

• root == nullptr 时，返回 false
• key > root->_key 时，递归去右子树中查找
• key < root->_key 时，递归去左子树中查找
• else 代表相等，查找到了要被删除的结点

bool _erase_R(Node*& root, const K& key) {
    if (root == nullptr)
        return false;
    if (key > root->_key)
        return _erase_R(root->_right, key);
    else if (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 右为空
    else if (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;
    return true;
}

• 参数 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<class K>
struct BSTreeNode {
    // typedef BSTreeNode<K> Node;
    BSTreeNode(const K& key) : _left(nullptr), _right(nullptr), _key(key) {}
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
};

template<typename K>
class BSTree {
    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); }

    // 插入时，找到一个空位置插入即可 默认插入的元素不能重复
    bool insert(const K& key) {
        // 插入时为空树
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        // 不是空树时
        Node* parent = nullptr;
        Node* curNode = _root;
        while (curNode != nullptr) {
            if (key > curNode->_key) {
                parent = curNode;
                curNode = curNode->_right;
            } else if (key < curNode->_key) {
                parent = curNode;
                curNode = curNode->_left;
            } else {
                return false;
            }
        }
        // 走到这里，意味着 curNode 已经找到了位置，此时 curNode 为 nullptr
        // parent 为 curNode 的父节点
        // curNode 为 结点指针的拷贝，修改 curNode 不能修改结点指针的指向
        // 走完循环 curNode 找到了可以插入的位置
        // 但要插入结点，必须修改父节点的指针，父节点并不知道 key 是比自己大还是自己小，只知道下面可以插
        // 因此要再比较一次
        curNode = new Node(key);
        if (key > parent->_key) {
            parent->_right = curNode;
        } else
            parent->_left = curNode;
        return true;
        // key 不可能等于 parent->_key 否则上面的循环就是错误的
        /*else { return false; }*/
    }

    void Inorder() const {
        _Inorder(_root);
        printf("\n");
    }

    bool find(const K& key) const {
        Node* curNode = _root;
        while (curNode) {
            if (key == curNode->_key)
                return true;
            else if (key > curNode->_key)
                curNode = curNode->_right;
            else
                curNode = curNode->_left;
        }
        return false;
    }

    // 这里不能用引用代替指针，因为指针可以改变指向，引用一旦绑定，指向不可修改
    bool erase(const K& key) {
        Node* parent = nullptr;
        Node* curNode = _root;
        // _root 为空时，进不去 while 循环，会直接 return false
        while (curNode) {
            // 先找要被删除的节点
            if (key > curNode->_key) {
                parent = curNode;
                curNode = curNode->_right;
            } else if (key < curNode->_key) {
                parent = curNode;
                curNode = curNode->_left;
            }
            // 找到了，找到了，删除分为三种情况
            else {
                // curNode 的左为空
                if (curNode->_left == nullptr) {
                    // 特殊情况，左为空且 curNode 为_root
                    if (curNode == _root)
                        _root = curNode->_right;
                    // 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树
                    // 需要先找孤儿在左右那个子树
                    // 孤儿在左子树
                    else if (curNode == parent->_left)
                        parent->_left = curNode->_right;
                    // 孤儿在左子树
                    else
                        parent->_right = curNode->_right;
                    delete curNode;
                    return true;
                }
                // curNode 的右为空
                else if (curNode->_right == nullptr) {
                    if (curNode == _root)
                        _root = curNode->_left;
                    // 托孤
                    // 当前结点是父的左节点
                    else if (curNode == parent->_left)
                        parent->_left = curNode->_left;
                    // 当前结点是父的右节点
                    else
                        parent->_right = curNode->_left;
                    delete curNode;
                    return true;
                }
                // curNode 的左右都不为空，需要在树中找一个结点替换 curNode
                else {
                    // 需要找左子树中最大的、或右子树中最小的替换当前结点
                    // 二叉搜索树中，子树的最大结点，是树中最右边的结点
                    // 子树的最小结点，是树中最左边的结点
                    // 这里找左子树中最大的结点
                    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; // 错误逻辑
                }
                return true;
            }
        }
        return false;
    }

    // find 函数的递归版本
    // 写了一个子函数，因为递归需要用到 Private 成员_root，来控制递归子树的分支
    // 如果不写子函数，需要对外提供一个 getRoot 供调用者使用
    bool find_R(const K& key) const {
        return _find_R(_root, key);
    }
    bool insert_R(const K& key) {
        return _insert_R(_root, key);
    }
    bool erase_R(const K& key) {
        return _erase_R(_root, key);
    }

private:
    Node* Copy(Node* root) {
        if (root == nullptr)
            return nullptr;
        else {
            Node* newRoot = new Node(root->_key);
            // 分别递归拷贝 左右子树，拷贝完后，递归回去连接
            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;
        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)
            return false;
        if (key < root->_key)
            return _find_R(root->_left, key);
        else if (key > root->_key)
            return _find_R(root->_right, key);
        // 不 < 不 > 表明查找成功
        else
            return true;
    }

    // 这里参数 root 加引用，修改指针
    bool _insert_R(Node*& root, const K& key) {
        // 走到空的地方，可以开始插入了
        // 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用
        if (root == nullptr) {
            root = new Node(key);
            return true;
        }
        if (key < root->_key)
            return _insert_R(root->_left, key);
        else if (key > root->_key)
            return _insert_R(root->_right, key);
        else
            return false;
    }

    bool _erase_R(Node*& root, const K& key) {
        if (root == nullptr)
            return false;
        if (key > root->_key)
            return _erase_R(root->_right, key);
        else if (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 右为空
            else if (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;
            return true;
        }
    }

private:
    Node* _root;
};

6. 结语

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

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

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