二叉查找树（BST）

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

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

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

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

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

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

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

typedef struct Node 
{
	int key;
	Node* left;
	Node* right;
	Node* parent;
} *BSTree;

一、BST的插入与构造

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

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

/** * 插入：将关键字k插入到二叉查找树 */
 * 插入：将关键字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);
}

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

/** * 构造：用数组arr[]创建二叉查找树 */
 * 构造：用数组arr[]创建二叉查找树
 */
void Create_BST(BSTree &T, int arr[], int n){

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

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

/** * 非递归插入：将关键字k插入到二叉查找树 */
 * 非递归插入：将关键字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 的查找是从根结点开始，若二叉树非空，将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当给定值小于根结点关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。显然，这是一个递归的过程。

/** * 递归查找：返回指向包含关键字k的结点的指针 */
 * 递归查找：返回指向包含关键字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);
}

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

/** * 非递归查找：返回指向包含关键字k的结点的指针 */
 * 非递归查找：返回指向包含关键字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 为止。

/** * 最小值：查找二叉查找树中关键字最小的结点 */
 * 最小值：查找二叉查找树中关键字最小的结点
 */
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 的后继。如下图

/** * 后继：查找给定结点在中序遍历中的后继结点 */
 * 后继：查找给定结点在中序遍历中的后继结点
 */
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 的前驱。

/** * 前驱：查找给定结点在中序遍历中的前驱结点 */
 * 前驱：查找给定结点在中序遍历中的前驱结点
 */
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，然后从二叉查找树中删除这个后继，这样就转换成了第一或第二种情况。

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。

//#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)：

#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;
}

（全文完）