二叉排序树（BST）详解

1. 定义

二叉排序树（Binary Search Tree，简称BST）是一种二叉树，其中每个节点包含一个关键字，并满足以下性质：

• 对于每个节点，其左子树中所有节点的关键字都小于该节点的关键字。
• 对于每个节点，其右子树中所有节点的关键字都大于该节点的关键字。
• 左子树和右子树都是二叉排序树。

2. 各种操作

插入操作

将一个新的关键字插入到BST中。插入时，通过比较关键字大小，决定插入位置。具体步骤如下：

1. 从根节点开始，比较新插入关键字和当前节点关键字的大小。
2. 如果新关键字小于当前节点关键字，则移至左子树；反之，则移至右子树。
3. 重复上述步骤，直到找到一个空位置，将新关键字插入该位置。

插入操作的代码实现如下：

// 插入节点
Node* insert(Node* node, int key) {
    if (node == NULL) return createNode(key);

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    }

    return node;
}

搜索操作

在BST中查找一个关键字，步骤如下：

1. 从根节点开始，比较目标关键字和当前节点关键字的大小。
2. 如果目标关键字等于当前节点关键字，则查找成功。
3. 如果目标关键字小于当前节点关键字，则移至左子树；反之，则移至右子树。
4. 重复上述步骤，直到找到目标关键字或遇到空节点（查找失败）。

搜索操作的代码实现如下：

// 搜索节点
Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }

    if (key < root->key) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

删除操作

删除BST中的一个节点，分三种情况：

1. 叶子节点：直接删除该节点。
2. 仅有一个子节点：用其唯一的子节点替代该节点。
3. 有两个子节点：找到该节点的后继（右子树中最小的节点），用后继节点替代该节点，然后删除后继节点。

删除操作的代码实现如下：

// 找到最小值节点
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 删除节点
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

    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 == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

3. 创建BST

创建BST的过程即依次插入多个关键字到BST中。

4. 性能分析

BST的性能主要取决于其高度：

• 最好情况下（完全平衡）：高度为 $O(\log n)$。
• 最坏情况下（退化为链表）：高度为 $O(n)$。

5. 时间复杂度和空间复杂度分析

插入操作

• 时间复杂度：在平均情况下，插入操作的时间复杂度为 $O(\log n)$，因为树的高度在平均情况下为 $\log n$。在最坏情况下（树退化为链表），时间复杂度为 $O(n)$。
• 空间复杂度：插入操作主要占用的空间是用于递归调用的栈空间，在最坏情况下为 $O(n)$，平均情况下为 $O(\log n)$。

搜索操作

• 时间复杂度：在平均情况下，搜索操作的时间复杂度为 $O(\log n)$。在最坏情况下（树退化为链表），时间复杂度为 $O(n)$。
• 空间复杂度：搜索操作主要占用的空间是用于递归调用的栈空间，在最坏情况下为 $O(n)$，平均情况下为 $O(\log n)$。

删除操作

• 时间复杂度：在平均情况下，删除操作的时间复杂度为 $O(\log n)$。在最坏情况下（树退化为链表），时间复杂度为 $O(n)$。
• 空间复杂度：删除操作主要占用的空间是用于递归调用的栈空间，在最坏情况下为 $O(n)$，平均情况下为 $O(\log n)$。

6. 示例代码（C语言实现）

以下是BST的C语言实现，包括插入、搜索和删除操作：

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// 创建新节点
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点
Node* insert(Node* node, int key) {
    if (node == NULL) return createNode(key);

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    }

    return node;
}

// 搜索节点
Node* search(Node* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }

    if (key < root->key) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

// 找到最小值节点
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 删除节点
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

    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 == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

// 中序遍历
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->key);
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal: ");
    inorderTraversal(root);

    Node* foundNode = search(root, 60);
    if (foundNode != NULL) {
        printf("\nFound key 60\n");
    } else {
        printf("\nKey 60 not found\n");
    }

    return 0;
}

7. 参考文献

1. 《算法导论》 - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
2. **《数据结构与算法分析：C语言描述》