算法导论：二叉搜索树

二叉搜索树

1、什么是二叉搜索数

　　对任何节点x，其左子树的关键字小于等于x.key，右子树的关键字大于等于x.key。

　　中序遍历可以算法可以按从小到大的顺序输出二叉搜索树的关键字。中序遍历代码如下：

inorder_tree_walk(x)
1.     if(x!=NIL)
2.            inorder_tree_walk(x.left)
3.            print(x.key)
4.            inorder_tree_walk(x.right)

　　中序遍历算法遍历一个含有n个节点的树，时间复杂度为Θ(n)。

作业 12.1-4　　设计先序遍历算法和后续遍历算法，并且时间复杂度为Θ(n)。

preorder_tree_walk(x)
1.     if(x!=NIL)
2.         print(x.key)
3.         preorder_tree_walk(x.left)
4.         preorder_tree_walk(x.right)
5.　　//先序遍历

postorder_tree_walk(x)
1.     if(x!=NIL)
2.         postorder_tree_walk(x.left)
3.         postorder_tree_walk(x.right)
4.         print(x.key)
5.     //后序遍历

2、查询二叉搜索树

2.1、查找

　　在一颗给定的二叉搜索树中，x指向该二叉数的根节点，查找关键字k，如果存在关键字k为节点，则返回该节点，否则返回NIL。

　　从根节点向下递归形成一条向下的简单路线，所以tree_search(x,k)的运行时间为O(h)。h为树的高度=log(n)。

tree_search(x,k)
1. if x==NIL || k==x.key
2.          return x
3. if k>=x.key
4.     tree_search(x.right,k)
5. else
6.     tree_search(x.left,k)

　　使用while循环展开上面的递归。

iterative_tree_search(x,k)
1. while( x!=NIL && k!=x.key )
2.     if(k<x.key)
3.         x=x.left
4.     else
5.         x=x.right
6. return x

2.2、查找最大关键字元素和最小关键字元素

　　二叉搜索树的性质决定了最大元素是最右的那个元素，最小关键字元素是最左的那个元素。查找最大关键字的两个过程都能在O(h)时间内完成。

tree_maximum(x)
1. while( x.right!=NIL )
2.     x = x.right
3. return x

tree_minmum(x)
1. while(x.left!=NIL)
2.     x = x.left
3. return x

2.3、后继和前驱

　　如果二叉搜索树每个节点关键字不相同，那么在节点x的后继为大于x.key的最小关键字的节点，节点x的前驱为小于x.key的最大关键字节点。搜索路径为一条简单的向上的路径，两个过程都能在O(h)时间内完成。

tree_successor(x)
1. if(x.right!=NIL)
2.     return tree_minmum(x.right)
3. y = x.p
4. //if(y!=NIL && y.left==x)
5. //    return y
6. while(y != NIL && x == y.right)
7.     x = y
8.     y = y.p
9. return y

tree_predecessor(x)
1. if(x.left!=NIL)
2.     return tree_maxmum(x.left)
3. y = x.p
4. while(y!=NIL && x = y.left)
5.     x = y
6.     y = y.p
7. return y

练习 12.2-2 写出tree_maxmum和tree_minmum的递归画版本

tree_maxmum(x)
1. if(x.right != NIL)
2.     return tree_maxmum(x.right)
3. return x

tree_minmum(x)
1. if(x.left!=NIL)
2.     return tree_minmum(x.left)
3. return x

3、插入和删除

　　插入操作，将要插入的元素从根节点开始依次向下搜索，直到找到合适的位置插入。伪代码如下：

tree_insert(T,z)
1. y=NIL
2. x = T.root
3. while(x!=NIL)
4.     y=x
5.     if(x.key>z.key)
6.         x = x.left
7.     else    x = x.right
8. z.p = y
9. if(y==NIL)
10.     T.root=z
11. else if(y.key>z.key)
12.     y.left = z
13. else y.right = z