二叉搜索树定义

引言

在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和修改。其中一种重要的数据结构便是二叉搜索树（Binary Search Tree, BST），它具有独特且高效的搜索特性，在许多算法设计与实现中发挥着重要作用。

什么是二叉搜索树？

二叉搜索树是一种特殊的二叉树，其每个节点都包含一个关键值，并满足以下性质：

有序性：对于任意的节点，其左子树中的所有节点的关键值均小于该节点的关键值；右子树中所有节点的关键值均大于该节点的关键值。
唯一性：节点不包含重复的关键值。

二叉搜索树的基本结构

二叉搜索树的基本构建块是二叉树的节点。每个节点存储一个关键值以及指向其左右子节点的指针（或引用）。具体而言，定义如下：

struct TreeNode {
    int key;
    TreeNode *left, *right;
};

这里 key 代表节点存储的关键值，而 left 和 right 指向该节点的左子树和右子树。

插入操作

二叉搜索树的核心优势在于其高效的插入、删除与查找操作。以插入为例，在插入一个新关键值时，从根节点开始，按照上述有序性要求逐层比较并移动，直到找到合适的位置将新节点插入进去：

TreeNode* insert(TreeNode* root, int key) {
    if (root == nullptr) return new TreeNode(key);
    
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    
    // 不需要处理等于的情况，因为不允许重复值
    return root;
}

搜索操作

搜索目标节点的过程非常直观：从根节点开始，根据当前节点的值与目标值之间的关系向左或向右递归地移动。如果找到了匹配的目标值，则返回对应的节点；否则，当无法继续向下搜索时说明未找到该目标。

TreeNode* search(TreeNode* root, int key) {
    if (root == nullptr || root->key == key)
        return root;
    
    if (key < root->key)
        return search(root->left, key);
    else
        return search(root->right, key);
}

删除操作

删除节点的过程相对复杂，需要确保在删除后二叉搜索树的性质仍然保持不变。主要包括以下几种情况：

叶子节点：直接移除。
仅有一个子节点：用其子节点替换该位置。
有两个子节点：找到左子树的最大值（或右子树的最小值）作为替代，然后删除这个临时节点。

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return nullptr;

    // 根据key与当前节点的大小关系决定向哪边递归查找
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        // 节点为叶子节点或只有一个子节点的情况
        if (!root->left) return root->right;
        if (!root->right) return root->left;

        // 有两个子节点，找到右子树的最小值作为替代
        TreeNode* temp = minNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    
    return root;
}

总结

二叉搜索树作为一种经典的数据结构，凭借其高效的基本操作在许多实际应用场景中得到了广泛的应用。通过有序性保证了节点间关键值的有效排序，并支持高效地插入、删除与查找等操作。