在二叉判定树以及二分搜索的基础上，基于二叉树的搜索树产生，该数据结构可以随时进行调整，可以保证高效的搜索效率。

内容：

1.二叉搜索树

2.二叉平衡树

3.B-树

一、二叉搜索树

1、定义：（1）所有节点的值都不一样；（2）根节点的值大于左子树所有节点的值；（3）根节点的值小与右子树所有节点的值；（4）左右子树也都是二叉搜索树。

2、基本算法：查找、插入和删除

    查找：类似于二分查找，将带查找的值与根节点的值比较，若小于根节点的值，则递归搜索根节点的左子树；否则递归搜索根节点的右子树；若等于根节点的值，则返回成功。

    插入：若根节点的为空，则将待插入的值作为根节点；若待插入值小于根节点，则递归搜索根节点的左子树至搜索失败，新建节点并令新节点的值等于待插入的值；若待插入的值大于根节点的值，按类似的方法搜索右子树。当待插入的值等于树中某一节点值时，返回。

    删除：当进行删除操作时，如果被删除的节点为叶子节点，则直接将叶子节点删除掉；如果被删除节点只有一个孩子，则将它的孩子代替被删除节点的位置；如果被删除的节点有两个孩子，则令其左子树中最大的元素代替被删除节点的位置，或者令被删除节点右子树中最小的节点代替被删除节点。

二、二叉平衡树

虽然二叉搜索树具有很强的搜索效率，但是假如插入的数据为一有序序列时，二叉树就变为了一个有序链表，搜索效率变低。为了解决这个问题，二叉平衡树出现了。

1、定义：二叉平衡树是一颗二叉搜索树，但是其每个节点左右子树的高度差小于1。

2、基本算法：插入、删除

    插入：平衡树的插入与搜索树的插入相同，但是要保证其平衡性。当出现了不平衡现象时，要进行调整：

    （1）假设p指向AVL树的树根，若p==NULL,则插入元素的值为即为跟节点的值，树的高度+1。

    （2）若根节点不为空，调用Search(p,key)判断待插入元素在树内是否存在。若存在，则返回；若不存在，记录待插入位置A，并转入步骤（3）。

    （3）考虑离A最近的节点，若执行插入运算后改节点的平衡因子的绝对值大于一，则把该祖先节点的位置标记为B，左孩子为Bl,右孩子为Br。转入步骤（6）。

    （4）若从根节点到A位置的平衡因子都为0，则修改其平衡因子。当插入位置在某个节点的左子树上，改节点的平衡因子+1，插入位置若在某右节点的子树上时，改节点的平衡因子-1。树的高度+1。

    （5）若B的平衡因子为１，且新节点插入到B的右子树上时，则B的平衡因子该为０，树的高度不变。

    （６）此时B的平衡因子为２，下面细分LL型和LR型：

LL：如果Bl的平衡因子为1，新插入的节点插在Bl的左子树上，则向右旋转调节B为根的子树，树的高度不变；

LR型： 若Bl的平衡因子为-1，且新插入的节点在Bl的右子树上，则参考三原则，最以B为根的节点进行调整。树的高度不变。（一般是先左旋转后右旋转）

    （7）当B的平衡因子为-2时，对应的情况时RR和RL，与（6）类似。

三、B-树

在学习B树之前，我们应该先知道什么是m叉搜索树。

（一）、m叉搜索树

如图为m叉搜索树的递归定义

可以看出：一个节点中最多存放m-1个元素和m个指向子树的指针；每个节点中包含的元素树比指针树少1。

性质：高度为h的m叉搜索树中最多有m^h-1个元素；

           含有N个元素的m叉搜索树的高度在log[m](N+1)到N之间。

（二）、B-树

1、定义

可以看出：

A.一个节点最多有m个孩子，m-1个关键字；

B.除根结点和失败节点外每个节点最少有[m/2]个孩子，[m/2]-1个关键字；

C.根节点最少有两个孩子；

D.所有的失败节点均在同一层上，即失败节点为双亲的叶子节点。

那我们怎末判断一颗树是不是B树呢？

1、首先看失败节点是否在同一层上；

2、查看根节点是否最少有两个孩子；

3、确定m的值，并计算m/2的值；

4、查看每个节点（除根节点和失败节点）的孩子数量有没有少于[m/2]个。

（二）、B-树的性质

1、设失败节点的数目为s，那么一个B树包含的元素总数N是失败节点的个数减一，即N=s-1；

2、含有N个元素的m阶B树的高度h有：h<=1+log[m/2](N+1)/2；

(三）B树的操作

1、查找操作

与搜索树的查找类似。

B树主要做文件的索引

在B树寻找节点，需执行的磁盘访问次数最多的是1+log[m/2]((N+1)/2);

在节点中找关键字可以采用顺序搜索或者二分搜索。

2、插入

步骤为：

（1）、搜索   （2）、插入    （3）、调整（分裂）

3、删除

步骤为：