二叉搜索树

1. 什么是二叉搜索树

一棵二叉搜索树是以一棵二叉树来组织的。每个结点包括关键字key及其卫星数据，左孩子left, 右孩子right, 父节点p。

二叉搜索树中的关键字key总是以满足二叉搜索树性质的方式来存储： 设x是二叉搜索树的一个结点。如果y是x左子树中的一个结点，则y.key <= x.key。如果y是x右子树中的一个结点，则y.key >= x.key。

如图，根节点的关键字为12，在其左子树中有关键字2、5、9，它们均不大于12。在其右子树中有关键字15、16、17、18、19，它们均不小于12。

2.二叉搜索树的操作

2.1 按序输出关键字

我们通过一个简单的递归算法按序输出搜索树的关键字，这种算法为中序遍历。上图搜索树的输出结果应为2,5,9,12,15,16,17,18,19。

伪代码：

FUNCTION Output_Tree(x) if x != NULL Output_Tree(x.left) printf x.key Output_Tree(x.right)

如果x是一棵有n个结点的子树的根，那么调用Output_Tree需要O(n)时间。

2.2 二叉树的查找

2.2.1 关键字的查找

在一棵搜索二叉树中查找一个具有给定关键字的结点。输入一个指向树根的指针x和一个关键字k。如果结点存在则返回一个指向关键字k的指针，否则返回NULL。

伪代码：

FUNCTION Tree_Search(x, k) if x == NULL or k == x.key return x if k < x.key return Tree_Search(x.left, k) else return Tree_Search(x.right, k)

先判断返回条件，如果当前结点为空，或者关键字k与x.key相同，那么查找终止。否则递归向下查找。

我们也可以采用while循环来迭代查找关键字。

FUNCTION Tree_Search(x, k) while x != NULL or k != x.key if k < x.key x = x.left else x = x.right return x

查找关键字Tree_Search的运行时间为O(h)，其中h是搜索树的高度。

2.2.2最大值与最小值的查找

递归向下找到最左子树结点即为最小值。 最小值伪代码： FUNCTION Tree_Minimum(x) while x.left != NULL x = x.left return x 递归向下找到最右子树即为最大值。 最大值伪代码： FUNCTION Tree_Maximum(x) while x.right != NULL x = x.right return x

2.2.3 搜索树的前驱和后继

查找后继结点分为两种情况：

如果x结点存在右子树，则后继结点为右子树的最小值，如下图的根节点关键字为12，后继为15；如果x结点不存在右子树，则后继结点需要向上查找祖先结点y为其父节点的左子树，如下图关键字为9的结点，其后继为12。

查找后继结点-伪代码：

FUNCTION Tree_Successor(x) if x.right != NULL return Tree_Minimum(x.right) y = x.p while y != NULL && x = y.right x = y y = x.p return y

查找前驱结点的伪代码与查找后继结点的类似，如下。 前驱结点-伪代码：

FUNCTION Tree_Predecessor(x) if x.left != NULL return Tree_Maximum(x.left) y = x.p while y != NULL && x = y.left x = y y = x.p return y

2.3 二叉搜索树的插入与删除

一棵高度为h的二叉搜索树的插入和删除运行时间均为O(h)。

2.3.1 搜索二叉树的插入

搜索树的插入-伪代码：

FUNCTION Tree_Insert(T, z) y = NULL /* y 用来记录x的父节点 */ x = T.root /* x 用来查找z结点的位置 */ while x != NULL /* 当x为空时，y记录的位置即为z结点的父节点*/ y = x if z.key < x.key /* 比较z的关键字与x的关键字的大小，决定z结点的位置*/ x= x.left else x = x.right z.p = y if y = NULL /* 当树为空的时候 */ T.root = z else if z.key < y.key y.left = z else y.right = z 代码while循环部分通过比较结点关键字大小确定z结点最后插入的位置。代码if 、elseif、else最后插入z结点到正确的位置。一棵高度为h的搜索树插入算法需要的运行时间为O(h)。

2.3.2 搜索二叉树的删除

从搜索二叉树中删除一个结点z整个策略分为三种情况：

如果z结点没有孩子结点，那么只是简单的将其删除，并修改其父节点为NULL。如果z结点只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父节点。如果z结点有两个孩子，那么找到z的后继y，并让y占据树中z的位置。z的原来右子树部分成为y的新的右子树，并且z的左子树成为y的新的左子树部分。

从一棵二叉搜索树中删除一个结点z，这个过程取树T和结点z指针作为输入参数。算法的分析有四种情况：

如果z结点没有左孩子，那么用其右孩子来代替z，这个右孩子可能是NULL，此时表示z结点没有孩子，如图1-结点9。当右孩子不为NULL时，表示z只有一个孩子结点，即右孩子，如图1-结点15。如果z结点仅有一个孩子且为左孩子，那么用其左孩子来代替z，如图1-结点17。如果z既有左孩子又有右孩子，查找z的后继结点y，这个后继结点位于z的右子树中且没有左孩子。判断y是z的右孩子，那么用y替换z，并且仅留下y的右孩子，如图2-结点6。如果y不是z的右孩子，那么先用y的右孩子替换y，然后在用y替换z，如图1-结点12。

为了在二叉树中移动子树，定义一个子过程Tree_Transplant，用另一棵树u代替子树v并成为其双亲的孩子结点。 移动子树-伪代码：

FUNCTION Tree_Transplant(T, u, v) if v.p = NULL /* 如果v是树根*/ T.root = u else if v = v.p.left v.p.left = u else v.p.right = u if u != NULL u.p = v.p

删除结点-伪代码：

FUNCTION Tree_Delete(T, z) if z.left = NULL /* 当左孩子为NULL时 */ Tree_Transplant(T, z.right, z) else if z.right = NULL /* 当右孩子为NULL时 */ Tree_Transplant(T, z.left, z) else /* 当左右孩子均存在时 */ y = Tree_Minimum(z.right) /* 寻找z结点的后继结点y */ if y.p != z /* 如果结点y是z的右孩子 */ Tree_Transplant(T, y.right, y) /* 用y的右孩子代替y */ y.right = z.right /* 更新y的右孩子，用z的右孩子代替 */ y.right.p = y /* 将y的新的右孩子的父节点指向y */ Tree_Transplant(T, y, z) /* 用y代替z */ y.left = z.left /* 更新y的左孩子，用z的左孩子代替 */ y.left.p = y /* 将y的新的左孩子的父节点指向y */