BST树

二叉排序树（Binary Sort Tree）又称二叉查找树。
它或者是一棵空树；或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有结点的值均小于左子树所在树的根结点的值；
(2)若右子树不空，则右子树上所有结点的值均大于右子树所在树的根结点的值；
(3)左、右子树也分别为二叉排序树；

二叉排序树(B树)的查找

时间复杂度与树的深度的有关。
步骤：若根结点的关键字值等于查找的关键字，成功。
否则：若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。

二叉排序树(B树)的插入和删除

二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

插入

首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左儿子还是右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点，所以算法复杂度是O(h)。

删除

1，如果删除的结点没有孩子，则删除后算法结束；
2，如果删除的结点只有一个孩子，则删除后该孩子取代被删除结点的位置；
3，如果删除的结点有两个孩子，则选择右孩子为根的树，它的左子树中，值最小的点作为新的根，同时在该最小值处开始，执行删除算法，如此继续到删除算法的前两种情况时，删除算法结束。

B树用途：查找信息快速，但是随着查找深度的增加，会影响查找的效率，所以，通常会使用平衡二叉树（最后的非子叶节点的深度之差的绝对值不大于1）的平衡算法来进行动态平衡。