二叉查找树
1、二叉搜索树（B树）
一棵二叉搜索树（BST）是以一棵二叉树来组织的，可以用链表数据结构来表示，其中，每一个结点就是一个对象，一般地，包含数据内容key和指向孩子（也可能是父母）的指针属性。如果某个孩子结点不存在，其指针属性值为空（NIL）。 二叉搜索树中的关键字key的存储方式总是满足二叉搜索树的性质： 设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么会有y.key<=x.key；如果y是x右子树中的一个节点，那么有y.key>=x.key。
二叉搜索树上基本操作所花费的时间与这棵树的高度成正比，对于有n个结点的一棵完全二叉树而言，这样的操作的最坏运行时间是O(lgn)。然而如果这棵树是一条n个结点组成的线性链，那么操作需要花费的时间为0(n)。
由图可以看出，对于遇到的每个结点x，都会比较x.key与k的大小，如果相等，就终止查找，否则，决定是继续往左子树还是右子树查找。因此，整个查找过程就是从根节点开始一直向下的一条路径，若假设树的高度是h，那么查找过程的时间复杂度就是O(h)。
查询二叉搜索树
//递归实现
Tree_Search(x, k):
if x == NIL or x.key == k :
return x
if k < x.key
return Tree_Search(x.left, k)
else return Tree_Search(x.right, k) //非递归迭代实现
Tree_Search(x, k) :
while x!=NIL and k!=x.key:
if k < x.key
x = x.left
else x = x.right
return x 最大关键字元素和最小关键字元素
通过树根开始沿着left孩子指针一直到NIL，可以找到最小元素。
TREE-MINMUM(X)
while x.left != NIL
x = x.left
return x同样的方法可以找到最大值。
TREE-MAXMUM(X)
while x.right!= NIL
x = x.right
return x查找最小值和最大值的方法均能够在O(h)的时间内完成。
后继和前驱
都在利用之前的部分，通过找x的右子树找到后继，通过找x的左子树找到前驱。找前驱和找后继的方法是相同的。
Tree_Successor(x):
if x.right != NIL
return Tree_MinNode(x.right)
y = x.p
while y!=NIL and x == y.right
x = y
y = y.p
return y 插入操作
当需要插入一个新结点时，从根节点开始，迭代或者递归向下移动，直到遇到一个空的指针NIL，需要插入的值即被存储在该结点位置。这里给出迭代插入算法，递归方式的比较简单。
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
else if z.key < y.key
y.left = z
else y.right = z 删除操作
二叉搜索树的节点删除比较复杂，可以分为三种情况：
1、如果z没有孩子节点，那么直接删除，并修改父节点，用NIL代替z；
2、如果z只有一个孩子，那么将这个孩子节点提升到z的位置，并修改z的父节点，用z的孩子替换z；
3、如果z有两个孩子，那么查找z的后继y（y一定在z的右子树中），然后用y替换z。
对于情况3，可以继续细分为2种情况：
1.z的后继y位于右子树中，但是没有做孩子，也就是说y的是后继。
2.z的后继位于z的右子树中，但是并不是z的右孩子，此时，用y的右孩子替换y，然后用y替换z。
