数据结构：二叉搜索树 (BST)

什么是二叉搜索树？

二叉搜索树（BST）是一种特殊的二叉树，它具有以下性质：

• 每个节点的左子树中所有节点的值都小于该节点的值。
• 每个节点的右子树中所有节点的值都大于该节点的值。
• 左右子树也都是二叉搜索树。

这个性质使得在树中进行查找、插入和删除等操作非常高效。

基本操作

• 查找 (Search): 从根节点开始，如果目标值小于当前节点，则在左子树中继续查找；如果大于，则在右子树中查找。
• 插入 (Insert): 类似于查找，找到一个空位插入新节点，同时保持 BST 的性质。
• 删除 (Delete): 这是最复杂的操作，需要考虑三种情况：
  1. 要删除的节点是叶子节点。
  2. 要删除的节点只有一个子节点。
  3. 要删除的节点有两个子节点。

代码实现 (C++)

#include <iostream>

struct Node {
    int key;
    Node *left, *right;
    Node(int item) : key(item), left(nullptr), right(nullptr) {}
};

// 插入
Node* insert(Node* node, int key) {
    if (node == nullptr) return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    return node;
}

// 中序遍历 (会得到有序序列)
void inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

复杂度分析

对于一个平衡的 BST，所有基本操作的平均时间复杂度都是 O(log n)。但在最坏情况下（例如，当树退化成一个链表时），时间复杂度会变成 O(n)。为了解决这个问题，出现了像 AVL 树和红黑树这样的自平衡二叉搜索树。