二叉查找树(BST)

Published on:
Tags: 数据结构 查找

定义#

一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点；

二叉查找树又称为二叉搜索树，简称 BST

二叉查找树
图1 二叉查找树
非二叉查找树
图2 非二叉查找树

根据 BST 的性质，中序遍历图1，可得到一个有序的序列 1 2 3 4 5 6 7。

创建BST#

通过关键字序列来创建 BST 。

当二叉树为空时，把第一个节点当作根节点。
当二叉树不为空时，插入的值与根节点的值比较：

  1. 若等于根节点的值，则丢弃该插入值；
  2. 若大于根节点的值，则插入以右子节点为根节点的二叉树中；
  3. 若小于根节点的值，则插入以左子节点为根节点的二叉树中；

直到（左 或 右）子节点为空时，把插入值当作（左 或 右）子节点插入到二叉树中。

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
//由有n个元素的数组A，创建一个二叉排序树
BSTNode *CreateBST(KeyType A[],int n)  
{
    BSTNode *bt=NULL;                  
    for(int i=0;i<n;i++)
    {
        if(bt == NULL)
            bt = GenerateNode(A[i]);
        else 
            InsertBST(bt,A[i]);
    }
    return bt;                
}

BSTNode *GenerateNode(KeyType k)
{
    BSTNode *tmp=(BSTNode *)malloc(sizeof(BSTNode));
    tmp->key=k;
    tmp->lchild=tmp->rchild=NULL;
    return tmp;
}

//在p所指向的二叉排序树中，插入值为k的节点
int InsertBST(BSTNode *p,KeyType k)
{
    if (k == p->key)                 //树中存在相同关键字的结点,返回0
        return 0;
    else if (k < p->key)            //插入到p的左子树中
    {
        if(p->lchild != NULL)
            return InsertBST(p->lchild,k);  
        else
        {
            p->lchild = GenerateNode(k);
            return 1;
        }
    }
    else                                //插入到p的右子树中
    {
        if(p->rchild != NULL)
            return InsertBST(p->rchild,k); 
        else
        {
            p->rchild = GenerateNode(k);
            return 1;
        }
    }
}

查找节点#

查找节点是创建 BST 的目的，查找的过程与创建的过程类似。

从根节点开始比较节点的关键字与目标值 $k$ （例如 $k=5$ ）的大小，若比较结果相等则查找完成；
若不相等，再根据 $k$ 与该根节点关键字的比较大小确定下一步查找哪个子树。
递归进行下去，直到找到满足条件的节点或者该二叉树中没有这样的节点。

1
2
3
4
5
6
7
8
9
10
//在bt指向的节点为根的排序二叉树中，查找值为k的节点。找不到返回NULL
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{
    if (bt == NULL || bt->key==k)         //递归终结条件
        return bt;
    if (k < bt->key)
        return SearchBST(bt->lchild,k);  //在左子树中递归查找
    else
        return SearchBST(bt->rchild,k);  //在右子树中递归查找
}

删除节点#

删除节点的前提是二叉树有这个节点，所以在执行删除节点方法前，需用查找节点方法判定一下。

通过关键值对比，找到了目标节点。

  1. 若目标节点没有右子节点，则可能含有左子节点，则把目标节点的左子节点赋值给它自己；
  2. 若目标节点没有左子节点，则可能含有右子节点，则把目标节点的右子节点赋值给它自己；
  3. 若目标节点是双分支节点，则先找到左子节点 tmpchild ，此时分两种情况：
    • 若 tmpchild 没有右子节点，则 tmpchild 的值域为左子树中的最大值，把 tmpchild 的值域赋值给目标节点，然后释放 tmpchild 节点内存即可；
    • 若 tmpchild 有右子节点，则找到 tmpchild 最大深度的右子节点，该节点的值域为左子树中的最大值，赋值给目标节点，释放内存即可。
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
//删除二叉搜索树中的一个节点
int DeleteBST(BSTNode *bt, KeyType k)  //在bt中删除关键字为k的结点
{   
    BSTNode *tmpchild,*p;
    if(bt == NULL)
        return 0;
    else
    {
        while (bt->key != k)
        {
            p = bt;                             //  记录目标节点的父节点
            if(k < bt->key)                     //  往左找
                bt = bt->lchild;
            else if(k > bt->key)               //  往右找
                bt = bt->rchild;
        }
        
        if(bt->rchild == NULL)                  //  目标节点无右孩子节点，则目标节点可能有左节点（左节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->lchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->lchild;
            free(bt);
        }
        else if(bt->lchild == NULL)             //  目标节点无左孩子节点，则目标节点可能有右节点（右节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->rchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->rchild;
            free(bt);
        }
        else                                    //  目标节点有左右孩子节点，找到左子树的最大的右孩子节点
        {
            tmpchild = bt->lchild;              //  左子树节点
            if(tmpchild->rchild == NULL)        //  当左子树没有右孩子节点，则左子树节点就是 用来替换目标节点的 最大节点，
            {
                bt->key = tmpchild->key;
                bt->lchild = tmpchild->lchild;   //  删除左子树节点，此时左子树节点没有右孩子节点，可能有左孩子节点
                free(tmpchild);
            }
            else                                //  左子树节点有右孩子节点
            {
                while (tmpchild->rchild != NULL)    //  找到最大深度的右孩子节点，就是值最大的节点，并且记录它的父节点
                {   
                    p = tmpchild;
                    tmpchild = tmpchild->rchild;
                }
                bt->key = tmpchild->key;            //  替换目标节点的值
                p->rchild = tmpchild->lchild;       //  此时的 tmpchild 一定没有右子节点，但可能有左子节点
                free(tmpchild);
            }
        }
        return 1;
    }
}

性能评价#

当二叉搜索树上的节点均匀分布的时候（例如图1），二叉搜索树处于一个平衡的状态，此时的查找效率最高，时间复杂度为 $O(log_2n)$ 。
但是一般情况遇到的更多像图3这样的，甚至有像图4这样的最坏情况，时间复杂度达到 $O(n)$ ，像顺序查找一样。
所以 BST 的时间复杂度为[ $O(log_2n)$ , $O(n)$ ]。

一般情况二叉查找树
图3 一般情况二叉查找树
最坏情况二叉查找树
图4 最坏情况二叉查找树

完整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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct node                 //记录类型
{
    KeyType key;                    //关键字项
    InfoType data;                  //其他数据域
    struct node *lchild,*rchild;    //左右孩子指针
} BSTNode;

BSTNode *CreateBST(KeyType A[],int n);
int InsertBST(BSTNode *p,KeyType k);
void DispBST(BSTNode *bt);
BSTNode *SearchBST(BSTNode *bt,KeyType k);
BSTNode *SearchBST_unr(BSTNode *bt,KeyType k);
int DeleteBST(BSTNode *bt, KeyType k);
BSTNode *GenerateNode(KeyType k);

//  二叉查找树
int main()
{
    BSTNode *bt;
    int del_num;
    int n=12,x=46;
    KeyType a[]= {25,18,46,2,53,39,32,4,74,67,60,11};
    bt=CreateBST(a,n);
    printf("BST:");
    DispBST(bt);
    printf("\n");
    printf("删除%d结点\n",x);
    if (SearchBST(bt,x) != NULL)
    {   //  结果 ！= NULL 表示找到值域为x的节点
        del_num = DeleteBST(bt,x);
        if(del_num)
            printf("成功删除结点 %d\n",x);
        printf("BST:");
        DispBST(bt);
        printf("\n");
    }
    return 0;

}


//由有n个元素的数组A，创建一个二叉排序树
BSTNode *CreateBST(KeyType A[],int n)  
{
    BSTNode *bt=NULL;                  
    for(int i=0;i<n;i++)
    {
        if(bt == NULL)
            bt = GenerateNode(A[i]);
        else 
            InsertBST(bt,A[i]);
    }
    return bt;                
}

BSTNode *GenerateNode(KeyType k)
{
    BSTNode *tmp=(BSTNode *)malloc(sizeof(BSTNode));
    tmp->key=k;
    tmp->lchild=tmp->rchild=NULL;
    return tmp;
}

//在p所指向的二叉排序树中，插入值为k的节点
int InsertBST(BSTNode *p,KeyType k)
{
    if (k == p->key)                 //树中存在相同关键字的结点,返回0
        return 0;
    else if (k < p->key)            //插入到p的左子树中
    {
        if(p->lchild != NULL)
            return InsertBST(p->lchild,k);  
        else
        {
            p->lchild = GenerateNode(k);
            return 1;
        }
    }
    else                                //插入到p的右子树中
    {
        if(p->rchild != NULL)
            return InsertBST(p->rchild,k); 
        else
        {
            p->rchild = GenerateNode(k);
            return 1;
        }
    }
}

//括号表示法输出一棵排序二叉树
void DispBST(BSTNode *bt)
{ 
    if (bt != NULL)
    {
        printf("%d",bt->key);
        if (bt->lchild != NULL || bt->rchild != NULL)
        {
            printf("(");                        //有孩子结点时才输出(
            DispBST(bt->lchild);                //递归处理左子树
            if (bt->rchild != NULL) printf(",");  //有右孩子结点时才输出,
            DispBST(bt->rchild);                //递归处理右子树
            printf(")");                        //有孩子结点时才输出)
        }
    }
}

//在bt指向的节点为根的排序二叉树中，查找值为k的节点。找不到返回NULL
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{
    if (bt == NULL || bt->key==k)         //递归终结条件
        return bt;
    if (k < bt->key)
        return SearchBST(bt->lchild,k);  //在左子树中递归查找
    else
        return SearchBST(bt->rchild,k);  //在右子树中递归查找
}

//二叉排序树中查找的非递归算法
BSTNode *SearchBST_unr(BSTNode *bt,KeyType k)
{
    while (bt != NULL)
    {
        if (k==bt->key)
            return bt;
        else if (k<bt->key)
            bt=bt->lchild;
        else
            bt=bt->rchild;
    }
    return NULL;
}

//删除二叉搜索树中的一个节点
int DeleteBST(BSTNode *bt, KeyType k)  //在bt中删除关键字为k的结点
{   
    BSTNode *tmpchild,*p;
    if(bt == NULL)
        return 0;
    else
    {
        while (bt->key != k)
        {
            p = bt;                             //  记录目标节点的父节点
            if(k < bt->key)                     //  往左找
                bt = bt->lchild;
            else if(k > bt->key)               //  往右找
                bt = bt->rchild;
        }
        
        if(bt->rchild == NULL)                  //  目标节点无右孩子节点，则目标节点可能有左节点（左节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->lchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->lchild;
            free(bt);
        }
        else if(bt->lchild == NULL)             //  目标节点无左孩子节点，则目标节点可能有右节点（右节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->rchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->rchild;
            free(bt);
        }
        else                                    //  目标节点有左右孩子节点，找到左子树的最大的右孩子节点
        {
            tmpchild = bt->lchild;              //  左子树节点
            if(tmpchild->rchild == NULL)        //  当左子树没有右孩子节点，则左子树节点就是 用来替换目标节点的 最大节点，
            {
                bt->key = tmpchild->key;
                bt->lchild = tmpchild->lchild;   //  删除左子树节点，此时左子树节点没有右孩子节点，可能有左孩子节点
                free(tmpchild);
            }
            else                                //  左子树节点有右孩子节点
            {
                while (tmpchild->rchild != NULL)    //  找到最大深度的右孩子节点，就是值最大的节点，并且记录它的父节点
                {   
                    p = tmpchild;
                    tmpchild = tmpchild->rchild;
                }
                bt->key = tmpchild->key;            //  替换目标节点的值
                p->rchild = tmpchild->lchild;       //  此时的 tmpchild 一定没有右子节点，但可能有左子节点
                free(tmpchild);
            }
        }
        return 1;
    }
    
}