&12-2 查找二叉搜索树

#1，定理

在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可以在O(h)时间内完成。

#2，伪代码

分别是搜索，迭代形式的搜索，取最小值，取最大值，找后继，找前驱。

1 //x is an element of the tree, k is the key of element we want to search.
2 TREE-SEARCH(x,k)
3 if x==NULL or k==x.key
4     return x;
5 
6 if k<x.key
7     return TREE-SEARCH(x.left,k);
8 else
9     return TREE_SEARCH(x.right,k);

TREE-SEARCH

1 ITERATIVE_TREE_SEARCH(x,k)
2 while x!=NULL and k!=x.key
3     if k<x.key
4         x=x.left;
5     else
6         x=x.right;
7 return x;

ITERATIVE_TREE_SEARCH

1 TREE-MINIMUM(x)
2 while x.left!=NULL
3     x=x.left;
4 return x;

TREE-MINIMUM

1 TREE-MAXIMUM(x)
2 while x.right!=NULL
3     x=x.right;
4 return x;

TREE-MAXIMUM

1 TREE-SUCCESSOR(x)
2 if x.right!=NULL
3     return TREE_MINIMUM(x.right);
4 y=x.p;
5 while y!=NULL and x==y.right
6     x=y;
7     y=y.p;
8 return y;

TREE-SUCCESSOR

1 TERR-PREDECESSOR(x)
2 if x.left!=NULL
3     return MAXIMUM(x.left);
4 y=x.p;
5 while y!=NULL and x==y.right
6     x=y;
7     y=y.p;
8 return y;

TERR-PREDECESSOR