#1，定理
在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可以在O(h)时间内完成。
#2，伪代码
分别是搜索，迭代形式的搜索，取最小值，取最大值，找后继，找前驱。
//x is an element of the tree, k is the key of element we want to search.
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);
TREE-SEARCH
ITERATIVE_TREE_SEARCH(x,k)
while x!=NULL and k!=x.key
if k<x.key
x=x.left;
else
x=x.right;
return x;
ITERATIVE_TREE_SEARCH
TREE-MINIMUM(x)
while x.left!=NULL
x=x.left;
return x;
TREE-MINIMUM
TREE-MAXIMUM(x)
while x.right!=NULL
x=x.right;
return x;
TREE-MAXIMUM
TREE-SUCCESSOR(x)
if x.right!=NULL
return TREE_MINIMUM(x.right);
y=x.p;
while y!=NULL and x==y.right
x=y;
y=y.p;
return y;
TREE-SUCCESSOR
TERR-PREDECESSOR(x)
if x.left!=NULL
return MAXIMUM(x.left);
y=x.p;
while y!=NULL and x==y.right
x=y;
y=y.p;
return y;
TERR-PREDECESSOR