查找树(search tree)是一种数据结构,它支持多种集合操作,包括SEARCH,MINIMUM,MAXIMUM,PREDECESSOR,SUCCESSOR,INSERT和DELETE。
二叉查找树是用二叉树结构来组织的查找树。它满足这样的性质:每个结点的左子树中所有的元素都小于等于该结点的值,而该结点同时小于等于它的右子树中的所有元素的值。基于这个性质,只需一个中序遍历便可以按由小到大的顺序遍历树内的所有的元素:
- INORDER_TREE_WALK(x) {
- 1 if x ≠ NIL {
- 2 INORDER_TREE_WALK(x.left);
- 3 print x.key;
- 4 INORDER_TREE_WALK(x.right);
- 5 }
- }
其实从直观上,可以发现上面的代码就是遍历树中的所有的元素,所以它的运行时间为Ө(n)。但我们还是稍微证明下:
设根结点的左子树中元素个数为k,则其右子树中元素个数为n-k-1,所以:
T(n) = T(k) + T(n-k-1) + d (d为常数,为访问一个元素的时间)
我们假设T(n) = c*n + d(这里取等于,不是大于或小于,可以同时求上界与下界),用代换法证明上式:
T(n) = (c*k+d) + (c*(n-k-1)+d) + d = c*n - c + 2*d
为使上式等于c*n+d,只需取c = d即可。
查询二叉查找树
下面的代码在二叉查找树中查找特定的关键字:
- TREE_SEARCH(x, k) {
- 1 if x == NIL or x.key == k
- 2 return x;
- 3 if k < x.key
- 4 return TREE_SEARCH(x.left, k);
- 5 else
- 6 return TREE_SEARCH(x.right, k);
- }
很明显,查找时会从根结点一直沿着某路径到达所要查找的元素或者叶结点,所以该算法运行时间为O(h),其中h为二叉树的高度。
下面的代码是查找的非递归版本:
- ITERATIVE_TREE_SEARCH(x, k) {
- 1 while x ≠ NULL and k ≠ x.key {
- 2 if (k < x.key)
- 3 x = x.left;
- 4 else
- 5 x = x.right
- 6 }
- 7 return x;
- }
下面的代码找出二叉查找树的最小元素:
- TREE_MINIMUM(x) {
- 1 while x.left != NIL
- 2 x = x.left
- 3 return x;
- }
其实最小元素就是树的最左结点,这是一个从根到叶结点的一条路径,所以它的运行时间为O(h)。
下面找出最大元素:
- TREE_MAXIMUM(x) {
- 1 while x.right != NIL
- 2 x = x.right;
- 3 return x;
- }
它找出树的最右结点,运行时间也为O(h)。
我们同样可以找到某结点的前趋(predecessor)和后继(successor)(分别为刚好比该结点小和刚好比该结点大的两个结点)。
查找后继:
- TREE_SUCCESSOR(x) {
- 1 if x.right ≠ NIL
- 2 return TREE_MINIMUM(x.right);
- 3 y = x.parent;
- 4 while y ≠ NULL and x ≠ y.left {
- 5 x = y;
- 6 y = y.parent;
- 7 }
- 9 return y;
- }
如果一个结点有右子树,它的后继便是它右子树中的最小元素;如果它没有右子树,它的后继便是离它最近的并把它当成左子树部分的祖先。可以发现它不是从上往下查找便是从下往上查找,所以它的运行时间也为O(h)。
前趋也后继类似,它的运行时间也为O(h)。
插入与删除
插入时,从根开始向下查找,直到发现某结点,使得插入的元素可以作为叶结点直接成为该结点的子女,而不改变现有的其它元素的结构。
下面是插入的代码:
- TREE_INSERT(T, z) {
- 1 x = NIL;
- 2 y = T.root;
- 3 while y ≠ NIL {
- 4 x = y;
- 5 if z.key ≤ y.key
- 6 y = y.left;
- 7 else
- 8 y = y.right;
- 9 }
- 10 if x == NIL // tree was empty
- 11 T.root = z;
- 12 else
- 13 if z.key ≤ x.key
- 14 x.left = z;
- 15 else
- 16 x.right = z;
- }
插入时主要的操作也是查找,所以它的运行时间为O(h)。
删除一个元素要更复杂一些,因为我们在删除一个结点后,还要维护整棵树的二叉查找的性质。我们可以从三种情况考虑:
1、如果要删除的结点没有子女,那么可以直接把这个结点从树中删除;
2、如果要删除的结点只有一个孩子,则不论它是左孩子还是右孩子,用这个孩子代替被删掉的结点,(例如,要删除的结点是其父结点的右孩子,该结点只有一个左孩子,则使它的左孩子成为它的父结点的新的右孩子,再把要删除的结点从树中移除);
3、如果要删除的结点有两个子女,则找到它的后继(右子树的最左结点)来代替这个被删除结点。(之所以这么做,因为它的后继比它的左子树的所有元素都大,又比它的右子树中的所有其它元素小。)
下面是删除的代码:
- TREE_DELETE(T, z) {
- 1 if z.left == NIL or z.right == NIL
- 2 y = z;
- 3 else
- 4 y = TREE_SUCCESSOR(z);
- 5 if y.left ≠ NIL
- 6 x = y.left;
- 7 else
- 8 x = y.right;
- 9 if x ≠ NIL
- 10 x.parent = y.parent;
- 11 if y.parent == NIL
- 12 T.root = x;
- 13 else if y == y.parent.left
- 14 y.parent.left = x;
- 15 else
- 16 y.parent.right = x;
- 17 if y ≠ z {
- 18 z.key = y.key;
- 19 copy y's satellite data into z;
- 20 }
- 21 return y;
- }
上面代码中,在第一种和第二种情况下(删除的结点没有子女或只有一个子女),y为要删除的结点,x为要删除的结点的孩子(可能为NIL),
再把x代替y。在第三种情况下(删除的结点有两个子女),y为要删除的结点的后继,x只可能为该后继的右孩子,将后继的右孩子x代替该后继y,接着在第
17行,如果y≠z,则意味着情况三,需要用后继代替被删除的元素,但这里并不是通过改变父亲指针、子女的指针来代替,而是直接把后继的值拷贝到要删除的
元素中。
虽然要复杂些,但删除操作中结点替代的操作为常数,主要的性能消耗在对后继的查找中,所以删除操作的运行时间也为O(h)。
综上所述,二叉寻找树的所有操作,包括查找特定关键字、查找最大元素、查找最小元素、查找前趋、查找后继、插入和删除的运行时间都为O(h),其中h为二叉寻找村的高度。
随机构造的二叉寻找树
通过前面的分析可以发现,二叉查找树的性能与树的高度密切相关。我们可以用随机选择插入元素的方式来获得一个好的期望性能:对于n个要插入的元素,每次随机选取其中一个插入,这种方式构造出来的二叉寻找树的期望高度为lg(n)。证明参考原书12.4节。
阅读(777) | 评论(0) | 转发(0) |