二叉排序树(BST)详解
1. 定义
二叉排序树(Binary Search Tree,简称BST)是一种二叉树,其中每个节点包含一个关键字,并满足以下性质:
- 对于每个节点,其左子树中所有节点的关键字都小于该节点的关键字。
- 对于每个节点,其右子树中所有节点的关键字都大于该节点的关键字。
- 左子树和右子树都是二叉排序树。
2. 各种操作
插入操作
将一个新的关键字插入到BST中。插入时,通过比较关键字大小,决定插入位置。具体步骤如下:
- 从根节点开始,比较新插入关键字和当前节点关键字的大小。
- 如果新关键字小于当前节点关键字,则移至左子树;反之,则移至右子树。
- 重复上述步骤,直到找到一个空位置,将新关键字插入该位置。
插入操作的代码实现如下:
// 插入节点
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中查找一个关键字,步骤如下:
- 从根节点开始,比较目标关键字和当前节点关键字的大小。
- 如果目标关键字等于当前节点关键字,则查找成功。
- 如果目标关键字小于当前节点关键字,则移至左子树;反之,则移至右子树。
- 重复上述步骤,直到找到目标关键字或遇到空节点(查找失败)。
搜索操作的代码实现如下:
// 搜索节点
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中的一个节点,分三种情况:
- 叶子节点:直接删除该节点。
- 仅有一个子节点:用其唯一的子节点替代该节点。
- 有两个子节点:找到该节点的后继(右子树中最小的节点),用后继节点替代该节点,然后删除后继节点。
删除操作的代码实现如下:
// 找到最小值节点
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的性能主要取决于其高度:
- 最好情况下(完全平衡):高度为 。
- 最坏情况下(退化为链表):高度为 。
5. 时间复杂度和空间复杂度分析
插入操作
- 时间复杂度:在平均情况下,插入操作的时间复杂度为 ,因为树的高度在平均情况下为 。在最坏情况下(树退化为链表),时间复杂度为 。
- 空间复杂度:插入操作主要占用的空间是用于递归调用的栈空间,在最坏情况下为 ,平均情况下为 。
搜索操作
- 时间复杂度:在平均情况下,搜索操作的时间复杂度为 。在最坏情况下(树退化为链表),时间复杂度为 。
- 空间复杂度:搜索操作主要占用的空间是用于递归调用的栈空间,在最坏情况下为 ,平均情况下为 。
删除操作
- 时间复杂度:在平均情况下,删除操作的时间复杂度为 。在最坏情况下(树退化为链表),时间复杂度为 。
- 空间复杂度:删除操作主要占用的空间是用于递归调用的栈空间,在最坏情况下为 ,平均情况下为 。
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. 参考文献
- 《算法导论》 - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- **《数据结构与算法分析:C语言描述》