C++ 二叉搜索树原理与实现

C++ 二叉搜索树原理与实现

概念与性能分析

二叉搜索树（Binary Search Tree, BST），又称二叉排序树。它要么是一棵空树，要么满足以下性质：

• 若左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
• 若右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
• 左右子树本身也必须是二叉搜索树。

关于相等值的处理，具体取决于使用场景。例如 std::map/std::set 不支持插入相等值，而 multimap/multiset 支持。这完全由底层实现定义。

性能表现

由于中序遍历的结果一定是升序序列，BST 非常适合用于查找和排序。其时间复杂度高度依赖于树的形态：

• 最优情况：树接近完全二叉树，高度为 $\log_2 N$，操作效率为 $O(\log N)$。
• 最差情况：树退化为单支树（类似链表），高度为 $N$，操作效率降为 $O(N)$。

这种不稳定性促使我们引入平衡二叉搜索树（如 AVL 树、红黑树）。虽然二分查找也能达到 $O(\log N)$，但它要求数据存储在支持随机访问的有序结构中，且插入删除需要大量移动数据。相比之下，平衡二叉搜索树在动态增删改查方面更具优势。

基本结构实现

节点定义

为了方便访问成员，通常使用 struct 定义节点，默认公有权限。

template<class K>
struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;

    BSTreeNode(const K& key)
        : _left(nullptr), _right(nullptr), _key(key) {}
};

类框架与生命周期管理

树的操作涉及资源的申请与释放，因此必须正确实现拷贝构造、赋值重载和析构函数。这里采用私有辅助函数配合公有接口的方式来实现递归逻辑。

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 默认构造
    BSTree() = default;

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

    // 赋值重载
    BSTree<K>& operator=(const BSTree<K> t) {
        swap(_root, t._root);
        return *this;
    }

    // 析构函数
    ~BSTree() {
        Destroy(_root);
    }

private:
    // 深拷贝辅助函数
    Node* Copy(Node* root) {
        if (root == nullptr) return nullptr;
        Node* copy = new Node(root->_key); // 注意：必须新开辟内存
        copy->_left = Copy(root->_left);
        copy->_right = Copy(root->_right);
        return copy;
    }

    // 销毁树
    void Destroy(Node* root) {
        if (root == nullptr) return;
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

private:
    Node* _root = nullptr;
};

核心操作实现

插入操作

插入逻辑遵循 BST 性质：比当前节点小往左走，大往右走，直到找到空位。如果树为空，直接设为根节点。

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

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

    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;
}

查找操作

从根节点开始比较，路径唯一，最多遍历树的高度次。

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;
}

删除操作

删除是 BST 中最复杂的操作，需分情况讨论：

1. 无孩子或仅一个孩子：直接将父节点的指针指向孩子的另一侧（或直接指向 null）。
2. 有两个孩子：不能直接删除，否则无法安置两个子树。通常用右子树的最小值（中序后继）或左子树的最大值替换当前节点的值，然后递归删除那个被替换的节点（此时该节点必为情况 1 或 2）。

这里采用交换键值的方法简化指针操作：

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 (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (cur == parent->_left) {
                        parent->_left = cur->_right;
                    } else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
            } else if (cur->_right == nullptr) {
                // 右孩子为空，处理左孩子
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (cur == parent->_left) {
                        parent->_left = cur->_left;
                    } else {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
            } else {
                // 两个孩子，找右子树最小值替代
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                // 交换键值
                std::swap(cur->_key, minRight->_key);
                // 删除 minRight 节点（此时它必然没有左孩子）
                if (pMinRight->_left == minRight) {
                    pMinRight->_left = minRight->_right;
                } else {
                    pMinRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

中序遍历

利用递归特性，先左后根再右，即可得到有序序列。

void InOrder() {
    _InOrder(_root);
    std::cout << std::endl;
}

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

Key-Value 结构变体

在实际应用中，往往需要存储键值对（Key-Value）。除了存储 key 外，还需增加 value 字段。增删查逻辑不变，依然以 key 为准，但允许修改 value。

namespace key_value {
template<class K, class V>
struct BSTreeNode {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;

    BSTreeNode(const K& key, const V& value)
        : _left(nullptr), _right(nullptr), _key(key), _value(value) {}
};

// 类定义逻辑同上，仅需调整构造函数及打印输出
// ... (省略部分重复代码，逻辑一致)
};

典型应用场景

Key 模式

• 车牌识别系统：录入业主车牌号，车辆进入时扫描比对，存在则放行。
• 拼写检查：将词库存入 BST，读取文章单词进行快速查找匹配。

Key-Value 模式

• 翻译字典：Key 为英文，Value 为中文，输入即查。
• 停车场计费：记录车牌与入场时间，出场时计算时长并扣费。
• 词频统计：Key 为单词，Value 为出现次数，遇到新单词初始化计数，已存在则累加。

---

以上便是二叉搜索树的核心原理与 C++ 实现细节。理解这些基础结构，对于后续学习更复杂的平衡树（如红黑树）至关重要。