二叉搜索树
二叉搜索树
搜索树结构支持许多动态集合操作，包括search,minimum,maximum,predecessor,successor,insert,delete等。使用一棵搜索树既可以作为一个字典，又可以作为一个优先队列。
什么是二叉搜索树
顾名思义，二叉搜索树就是以一棵二叉树来组织的。这样的一棵树可以用一个链表来表示，每一个结点都是一个对象，除了对象中的数据外，还有left,right,p，是分别指向当前结点的左孩子，右孩子和双亲的指针。如果不存在那么对应的值为nil。根结点是唯一父指针为nil的结点。
树中的关键字总是以某种性质的方式来存储：
当前结点的关键字大于等于左子树小于等于右子树。
这个性质让我们可以通过一个简单的递归算法来按序输出二叉搜索树种的所有关键字，这种算法就是中序遍历。
中序遍历：递归遍历 左子树->根->右子树
先序遍历：递归遍历 根->左子树->右子树
后序遍历：递归遍历 左子树->右子树->根
中序遍历伪代码：
INORDER-TREE-WALK(x)
if x != NIL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
时间，因为初次调用之后，对于每一个结点这个过程都要自己调用两次：一次左孩子，一次右孩子。
查询二叉搜索树
经常需要查找一个存储在二叉搜索树中的关键字。
查找
输入一个指向树根的指针和一个关键字k，如果这个节点存在，返回一个指向k的结点指针，否则返回nil。
TREE-SEARCH(x,k)
if x == NIL or k == x.key
return x
if k < x.key
return TREE-SEARCH(x.left,k)
else return TREE-SEARCH(x.right,k)
这个过程从根开始，沿着这棵树中的一条简单路径向下进行。所以运行时间为O(h)，其中h是树的高度。
可以用while循环来展开递归，用一种迭代的方式重写这个过程。对于大多数计算机，迭代版本的效率要高得多。
ITERATIVE-TREE-SEARCH(x,k)
while x != NIL and k != x.key
if k < x.key
x = x.left
else x = x.right
return x
最大关键字好最小关键字
如果一个结点没有左子树，那么该结点就是最小关键字。没有右子树的就是最大关键字。
TREE-MINIMUM(x)
while x.left != NIL
x = x.left
return x
TREE-MAXIMUM(x)
while x.right != NIL
x = x.right
return x
和查找一样，过程也是一条简单路径，时间也是O(h)。
后继和前驱
如果给的关键字都不相同，那么一个结点的后继就是大于x.key的最小关键字结点。前驱就是小于x.key的最大关键字结点。
TREE-SUCCESSOR(x)
if x.right != NIL
return TREE-MINIMUM(x.right)
y = x.p
while y != NIL and x == y.right
x = y
y = y.p
return y
分两种情况：
- x的右子树非空，后继就是右子树的最左结点。
- x的右子树为空，后继y就是x的某个祖先结点的父节点，而且祖先结点在y的左子树。
查询过程和上面的操作一样也是简单路径。时间也是O(h)。前驱操作和后继是对称的就不再写了。
插入和删除
插入
TREE-INSERT(T,z)
y = NIL
x = T.root
while x != NIL
y = x
if z.key < x.key
x = x.left
else x = x.right
z.p = y
if y == NIL
T.root = z
elseif z.key < y.key
y.left = z
else y.right = z
删除
删除比插入要复杂，可以分为三种情况：
- 如果z没有孩子，那么就可以简单的删除，然后修改它的父节点，用NIL来代替z
- 如果只有一个孩子，那么将孩子提升到z的位置，然后修改父节点，用z的孩子来代替z
- 如果有两个孩子，那么寻找z的后继y，让y占据z的位置。z的右子树成为y的右子树，z的左子树成为y的左子树。
为了在二叉搜索树中移动子树，定义一个子过程TRANSPLANT。
TRANSPLANT(T,u,v)
if u.p == NIL
T.root = v
elseif u == v.p.left
u.p.left = v
else u.p.right = v
if v != NIL
v.p = u.p
删除：
TREE-DELETE(T,z)
if z.left == NIL
TRANSPLANT(T,z,z.right)
elseif z.right == NIL
TRANSPLANT(T,z,z.left)
else y = TREE-MINIMUM(z.right)
if y.p != z
TRANSPLANT(T,y,y.right)
y.right = z.right
y.right.p = y
TRANSPLANT(T,z,y)
y.left = z.left
y.left.p = y
