概述

查找问题是计算机中非常重要的基础问题，在查找时，还经常需要支持插入和删除，通常这一问题的方法有：

数据结构 查找 插入 删除
无序数组 O(n) O(n) O(n)
有序数组 O(logn) O(n) O(n)

尽管使用有序数组可以将查找操作优化到O(logn)，但是在插入和删除时仍然为O(n)。

使用二叉搜索树可以将三种操作均优化到O(logn)。
一颗二叉搜索树（Binary Search Tree）满足以下性质：

  • 他是一颗二叉树
  • 左子树上所有节点的值都小于其根节点的值
  • 右子树上所有节点的值都大于其根节点的值

须要注意的是，二叉搜索树中不允许出现重复值。
此外，根据其性质，容易知道二叉搜索树的子树也是二叉搜索树。例如，下面这棵树就是一个二叉搜索树：
image.png|380
而这棵树则不是二叉搜索树：
image.png|388

复杂度分析

二叉搜索树在平均情况下，即树保持相对平衡（其左右子树的高度接近）的情况下，插入、删除、操作均为O(logn)，因为此时的树高度接近log(n)，向下搜索的深度不会超过树的高度。

但是，二叉搜索树在极端情况下，会退化为链表，这种情况发生在顺序插入的数据已经有序的情况下，此时的树是一棵左斜树/右斜树，即只有左子树/右子树：
image.png|475
此时的BSTree高度为n，三种操作均退化为O(n)。

因此在实际应用中，使用平衡树来优化会有更好的效果。

三种操作

查找操作

很简单，从根节点开始向下迭代寻找key值，有四种情况：

  • 如果当前节点值大于key，则继续搜索左子树
  • 如果当前节点值小于key，则继续搜搜右子树
  • 如果当前节点值等于key，则找到该值，查找成功
  • 如果当前节点为空（NULL），则该值不存在，查找失败

插入操作

同样需要查找，从根节点开始向下根据key值进行迭代，有四种情况：

  • 如果当前节点值大于key，则继续迭代左子树
  • 如果当前节点值小于key，则继续迭代右子树
  • 如果当前节点值等于key，则该值已存在，插入失败
  • 如果当前节点为空（NULL），则该值不存在，并找到了空位，在此处创建新节点插入key，插入成功

删除操作

删除稍复杂些，因为删除节点后必须保证树不断开，并且保持二叉搜索树的性质。
同样需要查找，从根节点开始向下根据key值进行迭代，有四种情况：

  • 如果当前节点值大于key，则继续迭代左子树
  • 如果当前节点值小于key，则继续迭代右子树
  • 如果当前节点值等于key，则找到该值，此时进行删除，删除成功
  • 如果当前节点为空（NULL），则该值不存在，删除失败

删除结点N的方法：

  1. 如果N为叶子节点，则直接将其删除即可
  2. 如果N只有一个子节点（无论左右），则将该子节点直接替换掉N即可
  3. 如果N有两个子节点，那么此时有2种方法，选择其一即可：
    1. 找到N的右子树中的最小节点N2，替换掉N节点；然后，删除该最小节点
    2. 找到N的左子树中的最大节点N2，替换掉N节点；然后，删除该最大节点

代码实现

C语言实现

该代码使用链表来存储二叉树。
BSTree.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//  
// Created by WAHAHA on 2023/10/18.  
//  
  
#ifndef ADT_BSTREE_H  
#define ADT_BSTREE_H  
  
#define bool int  
#define true 1  
#define false 0  
  
typedef int TreeElementType;  
typedef struct TreeNode {  
    TreeElementType value;  
    struct TreeNode *left;  
    struct TreeNode *right;  
} TreeNode;  
  
typedef struct {  
    TreeNode *root;  
    int size;  
} BSTree_t, *BSTree;  
  
// create and destroy  
BSTree newBSTree(void);  
static void destroyTreeRun(TreeNode *node);  
void destroyBSTree(BSTree T);  
  
// check status  
bool isEmptyTree(BSTree T);  
int treeSize(BSTree T);  
TreeElementType findMin(BSTree T);  
TreeElementType findMax(BSTree T);  
  
// operations  
bool find(BSTree T, TreeElementType key);  
bool insert(BSTree T, TreeElementType value);  
bool delete(BSTree T, TreeElementType value);  
  
#endif //ADT_BSTREE_H

BSTree.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <stdio.h>  
#include <stdlib.h>  
#include "BSTree.h"  
  
  
// create and destroy  
BSTree newBSTree(void) {  
    BSTree T = (BSTree) malloc(sizeof(BSTree_t));  
    if (T == NULL) {  
        printf("Error: create tree failed.\n");  
        return NULL;  
    }  
    T->root = NULL;  
    T->size = 0;  
    return T;  
}  
  
static void destroyTreeRun(TreeNode *node) {  
    if (node == NULL) {  
        return;  
    }  
    destroyTreeRun(node->left);  
    destroyTreeRun(node->right);  
    free(node);  
}  
  
void destroyBSTree(BSTree T) {  
    destroyTreeRun(T->root);  
    free(T);  
}  
  
// check status  
bool isEmptyTree(BSTree T) {  
    return T->size == 0;  
}  
  
int treeSize(BSTree T) {  
    return T->size;  
}  
  
TreeElementType findMin(BSTree T) {  
    TreeNode *p = T->root;  
    while (p->left != NULL) {  
        p = p->left;  
    }  
    return p->value;  
}  
  
TreeElementType findMax(BSTree T) {  
    TreeNode *p = T->root;  
    while (p->right != NULL) {  
        p = p->right;  
    }  
    return p->value;  
}  
  
// operations  
bool insert(BSTree T, TreeElementType value) {  
    TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));  
    if (node == NULL) {  
        printf("Error: create node failed.\n");  
        return false;  
    }  
    node->value = value;  
    node->left = NULL;  
    node->right = NULL;  
  
    if (T->root == NULL) {  
        T->root = node;  
        T->size++;  
        return true;  
    }  
  
    TreeNode *p = T->root;  
    while (p != NULL) {  
        if (value < p->value) {  
            if (p->left == NULL) {  
                p->left = node;  
                T->size++;  
                return true;  
            }  
            p = p->left;  
        } else if (value > p->value) {  
            if (p->right == NULL) {  
                p->right = node;  
                T->size++;  
                return true;  
            }  
            p = p->right;  
        } else {  
            printf("Error: value %d already exists.\n", value);  
            return false;  
        }  
    }  
    return false;  
}  
  
bool delete(BSTree T, TreeElementType value) {  
    TreeNode *p = T->root;  
    TreeNode *parent = NULL;  
    // find the node to delete  
    while (p != NULL) {  
        if (value < p->value) {  
            parent = p;  
            p = p->left;  
        } else if (value > p->value) {  
            parent = p;  
            p = p->right;  
        } else {  
            break;  
        }  
    }  
    // if not found  
    if (p == NULL) {  
        printf("Error: value %d not found.\n", value);  
        return false;  
    }  
  
    /* case 1: p is a leaf node */  
    if (p->left == NULL && p->right == NULL) {  
        if (parent == NULL) {  
            T->root = NULL; // the tree becomes empty  
        } else if (parent->left == p) {  
            parent->left = NULL;  
        } else {  
            parent->right = NULL;  
        }  
        free(p);  
        T->size--;  
        return true;  
    }  
  
    /* case 2: p has only one child */  
    if (p->left == NULL || p->right == NULL) {  
        TreeNode *child = p->left != NULL ? p->left : p->right;  
        if (parent == NULL) {  
            T->root = child; // the tree becomes a single node  
        } else if (parent->left == p) {  
            parent->left = child;  
        } else {  
            parent->right = child;  
        }  
        free(p);  
        T->size--;  
        return true;  
    }  
  
    /* case 3: p has two children */  
    TreeNode *q = p->right;  
    TreeNode *q_parent = p;  
    // find the smallest node in the right subtree of p  
    while (q->left != NULL) {  
        q_parent = q;  
        q = q->left;  
    }  
    // replace p with q  
    p->value = q->value;  
    // delete q,q is a leaf node or has only one child---its right child  
    // In effect, the question is shifted to deleting a node with no left child    // It doesn't really matter here q->right is NULL or not    if (q_parent->left == q) {  
        q_parent->left = q->right;  
    } else {  
        q_parent->right = q->right;  
    }  
    free(q);  
    T->size--;  
    return true;  
}  
  
bool find(BSTree T, TreeElementType key) {  
    TreeNode *p = T->root;  
    while (p != NULL) {  
        if (key < p->value) {  
            p = p->left;  
        } else if (key > p->value) {  
            p = p->right;  
        } else {  
            return true;  
        }  
    }  
    return false;  
}

测试main.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include "BSTree.h"  
  
int main() {  
    int nums[] = {5, 3, 6, 2, 4, 0, 8, 1, 7, 9};  
    BSTree T = newBSTree();  
  
    // test insert()  
    printf("insert 10 numbers into BSTree\n");  
    for (int i = 0; i < 10; ++i) {  
        insert(T, nums[i]);  
    }  
    printf("size: %d\n", treeSize(T));  
  
    // test findMin() and findMax()  
    printf("min: %d\n", findMin(T));  
    printf("max: %d\n", findMax(T));  
  
    // test find()  
    int key = 10;  
    if (find(T, key)) {  
        printf("find %d\n", key);  
    } else {  
        printf("not find %d\n", key);  
    }  
    key = 5;  
    if (find(T, key)) {  
        printf("find %d\n", key);  
    } else {  
        printf("not find %d\n", key);  
    }  
  
    // test isEmptyTree()  
    printf("size: %d\n", treeSize(T));  
    while (!isEmptyTree(T)) {  
        printf("%d ", findMin(T));  
        delete(T, findMin(T));  
    }  
    printf("\nsize: %d\n", treeSize(T));  
  
    // test destroyBSTree()  
    destroyBSTree(T);  
    return 0;  
}

运行结果:

1
2
3
4
5
6
7
8
9
10
11
$ ./ADT_BinaryTree.exe
insert 10 numbers into BSTree
size: 10
min: 0
max: 9
not find 10
find 5
size: 10
0 1 2 3 4 5 6 7 8 9 
size: 0