二叉排序树（Binary Sort Tree）又称二叉查找（搜索）树。 它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
二叉查找树中序遍历可得到一个有序序列。
定理：如果x是一颗包含n个节点的子树的根，则调用中序遍历过程的时间为O(n).（导论上有证明）。
（1）查找SEARCH
在二叉查找树中查找一个给定的关键字k的过程与二分查找很类似，根据二叉查找树在的关键字存放的特征，很容易得出查找过程：首先是关键字k与树根的关键字进行比较，如果k大比根的关键字大，则在根的右子树中查找，否则在根的左子树中查找，重复此过程，直到找到与遇到空结点为止。例如下图所示的查找关键字13的过程：（查找过程每次在左右子树中做出选择，减少一半的工作量）
书中给出了查找过程的递归和非递归形式的伪代码：
TREE_SEARCH(x,k) if x=NULL or k=key[x] then return x if(k<key[x]) then return TREE_SEARCH(left[x],k) else then return TREE_SEARCH(right[x],k) ITERATIVE_TREE_SEARCH(x,k) while x!=NULL and k!=key[x] do if k<key[x] then x=left[x] else then x=right[x] return x
2）查找最大关键字元素和最小关键字元素
要查找二叉树中具有最小关键字的元素，只要从根节点开始，沿着各节点的left指针查找下面，直到遇到NIL时为止，下面的过程返回
以给定节点x为根的子树中最小元素的指针：
Tree-minimum(x)
while left[x]!=NIL
do x<------left[x]
return x;
最大节点：
1 TREE_MAXMUM(x) 2 2 while right[x] != NULL 3 3 do x= right[x] 4 4 return x
对高度为h的树，这两个过程都是O（h），这是因为，如在TRee-search 过程中一样，所遇到的节点序列构成了一条沿着根节点向下的路径。
（3）前驱和后继
给定一个二叉查找树中的结点，找出在中序遍历顺序下某个节点的前驱和后继。如果树中所有关键字都不相同，则某一结点x的前驱就是小于key[x]的所有关键字中最大的那个结点，后继即是大于key[x]中的所有关键字中最小的那个结点。根据二叉查找树的结构和性质，不用对关键字做任何比较，就可以找到某个结点的前驱和后继。
书中给出了求x结点后继结点的伪代码:
TREE_SUCCESSOR(x) if right[x] != NULL then return TREE_MINMUM(right(x)) y=parent[x] while y!= NULL and x ==right[y] do x = y y=parent[y] return y
Tree-successor的代码中包含2种情况.如果节点x的右子树非空，则x的后继即右子树中的最左节点。
另一种情况，正如练习12.2-6中要求读者证明的那样，如果节点x的右子树为空，且x有一个后继y，则y是x的最低祖先节点，且y的左儿子也是x的祖先。
查找后继步骤：先判断x是否有右子树，如果有则在right[x]中查找关键字最小的结点，即使x的后继。如果没有右子树，则从x的父节点开始向上查找，直到遇到某个结点是其父结点的左儿子的结点时为止。例如下图查找结点13的后继结点15的过程：
查找前驱步骤：先判断x是否有左子树，如果有则在left[x]中查找关键字最大的结点，即是x的前驱。如果没有左子树，则从x继续向上执行此操作，直到遇到某个结点是其父节点的右孩子结点。例如下图查找结点7的前驱结点6过程：
或者可以看如何查找17的前驱15的。
定理：对一棵高度为h的二叉查找，动态集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的运行时间均为O(h)。
12.3插入和删除
插入和删除会引起以二叉查找树表示的动态集合的变化，要反映出这种变化，就要修改数据结构，但在修改的同时还要保持二叉查找树性质。插入过程相当来说要简单一些，删除结点比较复杂。
插入:
TREE_INSERT(T,z) y = NULL; x =root[T] while x != NULL do y =x if key[z] < key[x] then x=left[x] else x=right[x] parent[z] =y if y=NULL then root[T] =z //tree T was empty else if key[z]>key[y] then keft[y] = z else right[y] =z
Tree-insert从根节点出发，并沿着树下降，指针x跟踪了这条路径，而y始终指向x的父节点。在初始化后，第3-7行中的while循环
是这两个指针下降，根据key[z]和key[x]的比较结果，可以决定是向左转还是向右转。直到x称为NIL时为止。
这个NIL所占位置就是我们想插入项Z的地方。第8-13行设置有关z的指针。
删除：
删除时有三种可能：
1) 如果z没有子女，则修改其父节点p[z]， 使NIL为其子女，如图(a)
2) 如果结点只有一个子女，则可以通过在其子结点与父节点间建立一条链来删除z，如图(b)
3)如果结点z有两个子女，先删除z的后继y，再用y的内容来替代z的内容，如图(c)
1 TREE_DELETE(T,z) 2 if left[z] ==NULL or right[z] == NULL 3 then y=z 4 else y=TREE_SUCCESSOR(z) 5 if left[y] != NULL 6 then x=left[y] 7 else x=right[y] 8 if x!= NULL 9 then parent[x] = parent[y] 10 if p[y] ==NULL 11 then root[T] =x 12 else if y = left[[prarnt[y]] 13 then left[parent[y]] = x 14 else right[parent[y]] =x 15 if y!=z 16 then key[z] = key[y] 17 copy y's data into z 18 return y
第1-3行确定要删除的结点y，该节点是y或者是输入结点z（如果z至多只有一个节点），或者是z的后继（如果z有2个子女）。