C++ 二叉搜索树 (BST) 详解：原理、核心操作与实战实现

C++ 二叉搜索树 (BST) 详解：原理、核心操作与实战实现

在数据结构中，二叉搜索树 (Binary Search Tree，简称 BST) 是一种兼具'有序性'与'高效操作'的树形结构。它通过特定的节点值排列规则，让增删查操作的时间复杂度在理想情况下可达到 O(log₂N)，但最坏情况仍可能退化为 O(N)。本文将拆解其核心概念，结合实战代码，逐步讲解插入、查找、删除三大操作的实现细节。

一、二叉搜索树的核心概念

二叉搜索树又称二叉排序树。它要么是空树，要么满足以下分布规则：

• 若左子树不为空，则左子树中所有节点的值 ≤ 根节点的值；
• 若右子树不为空，则右子树中所有节点的值 ≥ 根节点的值；
• 左、右子树也分别是二叉搜索树（递归定义）。

关键特性：中序遍历为有序序列

二叉搜索树的核心价值在于'中序遍历结果是升序序列'。这也是其被称为'排序树'的原因。

关于'相等值'的约定： BST 对相等值的处理可灵活定义，具体取决于场景：

1. 不支持相等值插入（如 std::map/std::set 底层）：插入时若值已存在，直接返回失败。
2. 支持相等值插入（如 std::multimap/std::multiset 底层）：相等值需统一插入左子树或右子树。

本文实现的 BST 默认不支持相等值插入。

二、性能分析：理想与最差情况

BST 的操作效率直接取决于树的'高度'，而高度由节点插入顺序决定。

场景	树的形态	高度	时间复杂度	典型插入顺序
理想情况	完全二叉树（接近平衡）	log₂N	O(log₂N)	随机插入
最差情况	单支树（退化为链表）	N	O(N)	有序插入

虽然二分查找也能实现 O(log₂N) 的查找效率，但它依赖支持随机访问的结构（如数组），且插入/删除需挪动大量数据。而 BST 无需提前排序，且插入/删除仅需修改指针，避免了数据移动，在动态数据场景中更具优势。

三、BST 的实战实现

我们采用 C++ 模板实现，支持泛型 K（内置类型或自定义类型）。核心包含节点结构定义与三大操作（插入、查找、删除），并提供中序遍历接口验证有序性。

1. 节点结构定义

BST 的节点需存储'值'与'左右子树指针'。模板化设计使其可适配多种类型：

// BinarySearch.h
#include <iostream>
using namespace std;

template<class K>
class BSTNode {
public:
    // 构造函数：初始化列表指针为空，键值为传入值
    BSTNode(const K& key = 0) : _key(key), _left(nullptr), _right(nullptr) {}

    K _key;             // 节点键值
    BSTNode<K>* _left;  // 左子树指针
    BSTNode<K>* _right; // 右子树指针
};

2. 核心操作：Insert、Find、Erase

BST 类封装了树的根节点 _root，并通过辅助函数实现中序遍历。以下是三大核心操作的详细实现与解析。

2.1 插入操作 (Insert)

插入的核心逻辑是'按 BST 规则找到空位置，创建新节点并链接'。

1. 若树为空 (_root == nullptr)，直接新增结点赋值给 _root。
2. 树非空时，用 cur 指针遍历树找到符合要求的空位置：
   • 若 cur->_key < 插入值：向右子树移动。
   • 若 cur->_key > 插入值：向左子树移动。
   • 若值相等：返回 false（本实现不支持重复值）。

找到空位置后，通过 father 指针（记录 cur 的父亲节点）将新节点链接到树中。注意这里需要根据大小关系判断挂接到父节点的左边还是右边，而不是比较指针地址。

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;

    // 二叉搜索树的插入
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }

        Node* cur = _root;
        Node* father = nullptr;
        while (cur) {
            if (cur->_key > key) {
                father = cur;
                cur = cur->_left;
            } else if (cur->_key < key) {
                father = cur;
                cur = cur->_right;
            } else {
                // 相同则不符合插入规则，返回 false
                return false;
            }
        }

        // 循环结束说明找到了插入位置
        cur = new Node(key);
        
        // 根据 key 与 father->_key 的大小关系确定挂接方向
        if (key < father->_key) {
            father->_left = cur;
        } else {
            father->_right = cur;
        }
        return true;
    }

    // 中序遍历
    void Print() {
        _Print(_root);
        cout << endl;
    }

private:
    void _Print(const Node* root) {
        if (root == nullptr) return;
        _Print(root->_left);
        cout << root->_key << " ";
        _Print(root->_right);
    }

private:
    Node* _root = nullptr;
};

测试代码：

void Test1() {
    int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree<int> bst1;
    for (auto e : arr) {
        bst1.Insert(e);
    }
    bst1.Print(); // 输出应为有序序列
}

2.2 查找操作 (Find)

查找逻辑与插入类似，按 BST 规则遍历树即可。

bool Find(const K& x) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key > x) {
            cur = cur->_left;
        } else if (cur->_key < x) {
            cur = cur->_right;
        } else {
            return true;
        }
    }
    return false;
}

2.3 删除操作 (Erase)

删除是最复杂的核心操作。难点在于'删除节点后，需保持 BST 的规则不变'。根据删除节点 (cur) 的子节点数量，分为几种情况：

1. 叶子节点（左右均为空）：直接删除，将父节点指向该孩子的指针置空。
2. 单侧子树（左空右不空，或反之）：将父节点指向 cur 的指针，修改为指向 cur 的非空孩子。
3. 双侧子树均非空：使用替换法。找 cur 右子树的'最小节点'（最左节点）或左子树的'最大节点'（最右节点），将其值赋给 cur，然后删除那个替换节点（此时替换节点必为前两种情况之一）。

关键点：选择'右子树最小节点'作为替换节点，是因为该节点的值是 cur 右子树中最小的，替换后仍满足 BST 规则（左子树 ≤ 根 ≤ 右子树）。

bool Erase(const K& x) {
    Node* cur = _root;
    Node* father = nullptr;

    // 先查找目标结点
    while (cur) {
        if (cur->_key > x) {
            father = cur;
            cur = cur->_left;
        } else if (cur->_key < x) {
            father = cur;
            cur = cur->_right;
        } else {
            // 找到待删除节点 cur
            // 情况 1 & 2: 左子树为空
            if (cur->_left == nullptr) {
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (father->_left == cur) {
                        father->_left = cur->_right;
                    } else {
                        father->_right = cur->_right;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 3: 右子树为空
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (father->_left == cur) {
                        father->_left = cur->_left;
                    } else {
                        father->_right = cur->_left;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 4: 左右都不为空，替换法
            else {
                Node* min_right_father = nullptr;
                Node* min_right = cur->_right;
                // 找右子树最小节点
                while (min_right->_left) {
                    min_right_father = min_right;
                    min_right = min_right->_left;
                }
                
                // 交换键值
                cur->_key = min_right->_key;
                
                // 删除替换节点 (min_right)
                // 此时 min_right 必然没有左孩子，属于情况 1 或 2
                if (min_right_father == nullptr) {
                    // 最小节点就是 cur 的右孩子
                    cur->_right = min_right->_right;
                } else {
                    // 最小节点是某节点的左孩子
                    min_right_father->_left = min_right->_right;
                }
                delete min_right;
                return true;
            }
        }
    }
    return false;
}

四、BST 的扩展：Key/Value 模型

上述实现是'Key 模型'（仅存储键值，用于判断存在性）。但在实际场景中，'Key-Value 模型'（键值对应数据，如字典、统计次数）更加有用。我们可以将模板扩展为 template<class K, class V>。

1. Key-Value 模型实现要点

由于功能逻辑相似，主要区别在于节点多存一个 value，且部分函数需考虑 value 的存放。此外，由于 BST 是动态开辟内存，必须手动实现析构函数以防止内存泄漏。同时，实现了析构函数后，编译器生成的默认拷贝构造会导致浅拷贝问题（析构时重复释放），因此需要手动实现深拷贝的拷贝构造函数。

namespace key_value {
    template<class K, class V>
    class BSTNode {
    public:
        BSTNode(const K& key = 0, const V& value = 0)
            : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
        K _key;
        V _value;
        BSTNode<K, V>* _left;
        BSTNode<K, V>* _right;
    };

    template<class K, class V>
    class BSTree {
    public:
        typedef BSTNode<K, V> Node;

        ~BSTree() {
            Destroy(_root);
            _root = nullptr;
        }

        // 深拷贝构造
        BSTree(const BSTree<K, V>& bst) {
            _root = Copy(bst._root);
        }

        BSTree() = default;

        // 插入
        bool Insert(const K& key, const V& value) {
            if (_root == nullptr) {
                _root = new Node(key, value);
                return true;
            }
            Node* cur = _root;
            Node* father = nullptr;
            while (cur) {
                if (cur->_key > key) {
                    father = cur;
                    cur = cur->_left;
                } else if (cur->_key < key) {
                    father = cur;
                    cur = cur->_right;
                } else {
                    return false;
                }
            }
            cur = new Node(key, value);
            if (key < father->_key) {
                father->_left = cur;
            } else {
                father->_right = cur;
            }
            return true;
        }

        // 查找 (返回节点指针以便修改 value)
        Node* Find(const K& x) {
            Node* cur = _root;
            while (cur) {
                if (cur->_key > x) {
                    cur = cur->_left;
                } else if (cur->_key < x) {
                    cur = cur->_right;
                } else {
                    return cur;
                }
            }
            return nullptr;
        }

        // 删除逻辑同 Key 模型，此处省略重复代码，逻辑一致
        bool Erase(const K& x) {
            // ... (参考上文 Erase 逻辑，增加 value 同步更新)
            // 简化示意：找到后 cur->_key = min_right->_key; cur->_value = min_right->_value;
            // 实际实现需完整复制上文 Erase 逻辑并处理 value
            return false; 
        }

    private:
        void _Print(const Node* root) {
            if (root == nullptr) return;
            _Print(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _Print(root->_right);
        }

        void Destroy(const 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;
    };
}

2. 实战场景

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

树结构中存储 key (英文) 和 value (中文)，搜索时输入英文，直接获取对应的中文。

void Test2() {
    key_value::BSTree<string, string> dict;
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("insert", "输入");
    
    string str;
    while (cin >> str) {
        auto ret = dict.Find(str);
        if (ret) {
            cout << "->" << ret->_value << endl;
        } else {
            cout << "无此单词" << endl;
        }
    }
}

场景 2：单词统计

读取文本，查找单词是否存在。不存在则插入 <单词，1>，存在则 ++ 次数。

void Test3() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "香蕉" };
    key_value::BSTree<string, int> countTree;

    for (const auto& str : arr) {
        auto ret = countTree.Find(str);
        if (ret == nullptr) {
            countTree.Insert(str, 1);
        } else {
            ret->_value++; // 找到节点后直接修改 value
        }
    }
    countTree.Print();
}

到此，二叉搜索树的基础概念和功能实现就讲解完了。虽然中序遍历的有序性与指针操作的灵活性是其核心优势，但其性能受插入顺序影响大，导致出现单支树退化问题。后续学习平衡树（AVL、红黑树）时，我们将重点解决这一退化问题。作为基础树形结构，BST 是理解复杂数据结构设计逻辑的重要基石。