二叉查找树(BST)

二叉查找树(Binary Search Tree)又叫二叉排序树(Binary Sort Tree),它是一种数据结构,支持多种动态集合操作,如 Search、Insert、Delete、Minimum 和 Maximum 等。

二叉查找树要么是一棵空树,要么是一棵具有如下性质的非空二叉树:

  1. 若左子树非空,则左子树上的所有结点的关键字值均小于根结点的关键字值。

  2. 若右子树非空,则右子树上的所有结点的关键字值均大于根结点的关键字值。

  3. 左、右子树本身也分别是一棵二叉查找树(二叉排序树)。

可以看出,二叉查找树是一个递归的数据结构,且对二叉查找树进行中序遍历,可以得到一个递增的有序序列。

首先,我们来定义一下 BST 的结点结构体,结点中除了 key 域,还包含域 left, right 和 parent,它们分别指向结点的左儿子、右儿子和父节点:

1
2
3
4
5
6
7
typedef struct Node 
{
int key;
Node* left;
Node* right;
Node* parent;
} *BSTree;

一、BST的插入与构造

二叉查找树作为一种动态结构,其特点是树的结构通常不是一次生成的,而是在查找过程中,当树中不存在结点的关键字等于给定值时再进行插入。

由于二叉查找树是递归定义的,插入结点的过程是:若原二叉查找树为空,则直接插入;否则,若关键字 k 小于根结点关键字,则插入到左子树中,若关键字 k 大于根结点关键字,则插入到右子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 插入:将关键字k插入到二叉查找树
*/

int BST_Insert(BSTree &T, int k, Node* parent=NULL)
{

if(T == NULL)
{
T = (BSTree)malloc(sizeof(Node));
T->key = k;
T->left = NULL;
T->right = NULL;
T->parent = parent;
return 1; // 返回1表示成功
}
else if(k == T->key)
return 0; // 树中存在相同关键字
else if(k < T->key)
return BST_Insert(T->left, k, T);
else
return BST_Insert(T->right, k, T);
}

构造一棵二叉查找树就是依次输入数据元素,并将它们插入到二叉排序树中的适当位置。具体过程是:每读入一个元素,就建立一个新结点;若二叉查找树为空,则新结点作为根结点;若二叉查找树非空,则将新结点的值与根结点的值比较,如果小于根结点的值,则插入到左子树中,否则插入到右子树中。

1
2
3
4
5
6
7
8
9
/**
* 构造:用数组arr[]创建二叉查找树
*/

void Create_BST(BSTree &T, int arr[], int n)
{

T = NULL; // 初始时为空树
for(int i=0; i<n; ++i)
BST_Insert(T, arr[i]);
}

注意,插入的新结点一定是某个叶结点。另外,插入操作既可以递归实现,也可以使用非递归(迭代)实现。通常来说非递归的效率会更高。

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
/**
* 非递归插入:将关键字k插入到二叉查找树
*/

int BST_Insert_NonRecur(BSTree &T, int k)
{

Node* pre = NULL; // 记录上一个结点
Node* t = T;
while(t != NULL)
{
pre = t;
if(k < t->key)
t = t->left;
else if(k > t->key)
t = t->right;
else
return 0;
}

Node* node = (Node*)malloc(sizeof(Node));
node->key = k;
node->left = NULL;
node->right = NULL;
node->parent = pre;

if(pre == NULL)
T = node;
else
{
if(k < pre->key)
pre->left = node;
else
pre->right = node;
}
return 1;
}

二、BST的查找

对于二叉查找树,最常见的操作就是查找树中的某个关键字。除了Search操作外,二叉查找树还能支持如 Minimum(最小值)、Maximum(最大值)、Predecessor(前驱)、Successor(后继)等查询。对于高度为 h 的树,这些操作都可以在 Θ(h) 时间内完成。

1. 查找

BST 的查找是从根结点开始,若二叉树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当给定值小于根结点关键字时,在根结点的左子树中查找,否则在根结点的右子树中查找。显然,这是一个递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 递归查找:返回指向包含关键字k的结点的指针
*/

Node* BST_Search(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BST_Search(T->left, k);
else
return BST_Search(T->right, k);
}

也可以使用非递归的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 非递归查找:返回指向包含关键字k的结点的指针
*/

Node* BST_Search_NonRecur(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->key)
T = T->left;
else
T = T->right;
}
return T;
}

2. 最大值与最小值

由二叉查找树的性质可知,最左下结点即为关键字最小的结点,最右下结点即为关键字最大的结点。此过程无需比较,只需要沿着最左和最右的路径查找下去,直到遇到 NULL 为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 最小值:查找二叉查找树中关键字最小的结点
*/

Node* BST_Minimum(BSTree T)
{
while(T->left != NULL)
T = T->left;
return T;
}

/**
* 最大值:查找二叉查找树中关键字最大的结点
*/

Node* BST_Maximum(BSTree T)
{
while(T->right != NULL)
T = T->right;
return T;
}

3. 前驱与后继

给定一个二叉查找树的结点,求出它在中序遍历中的前驱与后继。如果所有的关键字均不相同,则某结点 x 的后继是:

  • 若结点 x 的右子树不为空,则 x 的后继就是它的右子树中关键字值最小的结点;

  • 若结点 x 的右子树为空,为了找到其后继,从结点 x 开始向上查找,直到遇到一个祖先结点 y,它的左儿子也是结点 x 的祖先,则结点 y 就是结点 x 的后继。如下图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 后继:查找给定结点在中序遍历中的后继结点
*/

Node* BST_Successor(Node* node)
{
if(node->right != NULL)
return BST_Minimum(node->right);
Node* p = node->parent;
while(p!=NULL && p->right == node)
{
node = p;
p = p->parent;
}
return p;
}

求前驱(predecessor)的过程对称,对于某个结点 x ,它的前驱是:

  • 若结点 x 的左子树不为空,则 x 的前驱是它的左子树中关键字值最大的结点;

  • 若结点 x 的左子树为空,为了找到其前驱,从结点 x 开始向上查找,直到遇到一个祖先结点 y,它的右儿子也是结点 x 的祖先,则结点 y 就是结点 x 的前驱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 前驱:查找给定结点在中序遍历中的前驱结点
*/

Node* BST_Predecessor(Node* node)
{
if(node->left != NULL)
return BST_Maximum(node->left);
Node* p = node->parent;
while(p!=NULL && p->left == node)
{
node = p;
p = p->parent;
}
return p;
}

之所以在这里讨论如何求中序序列的后继,主要是为了后面讲删除操作做铺垫。

三、BST的删除

二叉查找树的删除操作是相对复杂一点,它要按 3 种情况来处理:

  • 若被删除结点 z 是叶子结点,则直接删除,不会破坏二叉排序树的性质;

  • 若结点 z 只有左子树或只有右子树,则让 z 的子树成为 z 父结点的子树,替代 z 的位置;

  • 若结点 z 既有左子树,又有右子树,则用 z 的后继(Successor)代替 z,然后从二叉查找树中删除这个后继,这样就转换成了第一或第二种情况。

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
void BST_Delete(BSTree &T,Node* z)
{

if(z->left == NULL && z->right == NULL)
{
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = NULL;
else
z->parent->right = NULL;
}
else
{
T = NULL; // 只剩一个结点的情况
}
free(z);
}
else if(z->left != NULL && z->right == NULL)
{
z->left->parent = z->parent;
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = z->left;
else
z->parent->right = z->left;
}
else
{
T = z->left; // 删除左斜单支树的根结点
}
free(z);
}
else if(z->left == NULL && z->right != NULL)
{
z->right->parent = z->parent;
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = z->right;
else
z->parent->right = z->right;
}
else
{
T = z->right; // 删除右斜单支树的根结点
}
free(z);
}
else
{
Node* s = BST_Successor(z);
z->key = s->key; // s的关键字替换z的关键字
BST_Delete(T, s); // 转换为第一或第二种情况
}
}

对于一个高度为 h 的二叉查找树来说,删除操作和插入操作一样,都可以在 Θ(h) 时间内完成。

四、随机构造的二叉查找树

二叉查找树可以实现任何一种基本的动态集合操作,且各基本操作的运行时间都是 Θ(h)。当树的高度较低时,这些操作执行的较快;但是,当树的高度较高时,性能会变差。比如,如果各元素是按严格增长的顺序插入的,那么构造出来的树就是一个高度为 n-1 的链。 为了尽量减少这种最坏情况的出现,我们可以随机地构造二叉查找树,即随机地将各关键字插入一棵初始为空的树来构造 BST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//#include <cstdlib>
//#include <ctime>
/**
* 随机构造二叉查找树
*/

void Create_BST(BSTree &T, int arr[], int n)
{

T = NULL;
// 随机遍历数组,进行插入操作
srand(time(NULL));
for(int i=n-1; i>=0; --i)
{
int j = rand() % (i+1);
BST_Insert(T, arr[j]);
swap(arr[j], arr[i]);
}
}






附:随机遍历数组

在随机构造二叉查找树时,需要解决 随机遍历数组 的问题,即随机遍历一个数组中的所有元素,既不重复也不遗漏。这里能想到的一种思路是:先随机生成0...n-1之间的一个数,然后与数组最后一个数交换,然后再随机生成0...n-2之间的一个数,与数组倒数第二个数交换,直到整个数组遍历结束。显然这个算法的时间复杂度是 O(n):

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
#include <iostream>
#include <cstdlib> // srand rand
#include <ctime> // time
using namespace std;

void swap(int &a, int &b)
{

int tmp = a;
a = b;
b = tmp;
}

/**
* 随机遍历数组
*/

void Traverse_Random(int arr[], int n)
{

srand(time(NULL));
for(int i=n-1; i>=0; --i)
{
int j = rand() % (i+1);
cout << arr[j] << " "; // 输出
swap(arr[j], arr[i]);
}
}

int main()
{

int arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Traverse_Random(arr, 9);
getchar();
return 0;
}



(全文完)