二叉排序树是 由树到索引(2)

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m；

4.所有的叶子节点都位于同一层次；

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划(这个在下面解释下);

接下来我们以3阶树为例子来说说上面这些特征是如何体现的，然后在讨论下B树的增加和删除节点情况，

上图是一颗3阶树，首先最大的孩子数目为3，所以是3阶树，我们来看下12，这是2结点，包含1个根节点和2个孩子结点，满足第2，3条，左子树11小于12，右子树13、15大于12，接下来我们看2，6结点，3结点包含2、6两个元素，和3个孩子结点，左子树1小于2、6，右子树8大于2、6，3、5位于左、右子树中间，满足以上条件；

增加操作有3种情况：

1.对于空树，插入一个2结点即可；

2.插入到一个2结点的叶子上。这种情况考虑将其升级为3结点即可，这里进行解释一下，当插入3的时候，通过遍历会发现3比4小，只能插入到4的左子树，4有个子结点，这个时候只能将其升级为3结点，3比1大，插入到1的后继，这个时候形成右图样子。

3.插入3结点的情况相对比较麻烦，3结点是3阶树最大的容量，当向3结点插入的时候就要考虑拆分的情况，我们来看一下这几种情况。

第一种情况：向2结点满元素的子节点插入时候，左图满足这种情况，当向4的右孩子结点6，7插入5的时候，6、7已经是3结点的，不能在增加，这个时候发现4结点是2结点，就需要将其升级为3结点，于是讲6、7拆分，6与4组成3结点，5成为中间孩子，7成为右孩子，如右图。

第二种情况：当向3结点的满元素的子节点插入时候，左图满足这种情况，当向12、14的左孩子9、10插入11的时候，发现9、10已经满足3结点，不能在增加，但是父亲节点也是3结点，这个时候在向上查找，发现12、14的父亲结点8，还可以进行插入，这个时候讲8升级为3结点，将8与12合并，最终生成右图样子。

再来看一种比较特殊的情况：当向4、6左孩子结点1、3插入元素的时候，发现都是3结点无法在进行拆分，这个是将1、3结点、4、6结点、8、12结点都进行拆分，形成右图样子；

删除操作:

1.删除位于3结点的叶子结点，删除改元素即可，不会影响到别的结构，如下图：

2.删除元素位于一个2结点上，这里的情况比较复杂，我们分情况介绍：

第一种情况：该结点的双亲都是2结点，且拥有一个3结点的孩子，如下图，删除结点1，这种情况只需要左旋，6成为父亲节点，4成为6的左孩子，7成为6的右孩子。

第二种情况：该节点的双亲是2结点，右孩子也是2结点，如下图，删除4，左旋导致没有右孩子，不满足B树定义的第一条，所以这个时候需要对树的结构进行调整，首先将7进行左旋，将8进行左旋，9也进行左旋，形成图三所示的样子。

第三种情况：该结点双亲是一个3结点，如下图所示，删除10结点，12、14不能成为3结点，于是将此结点拆分，并将12、13合并成左孩子。

第四种情况：满二叉树的情况，删除任何一个叶子都会使整棵树不能满足第一条的定义，如下图所示，当删除8的时候，需要考虑将整棵树的层数减少，这个时候将6、7合并为9的左孩子，这个时候不满足第4条定义，需要将9、14合并为，最终形成右图所示。

3.删除的元素元素如果不是叶子结点，则考虑按照中序遍历后得到的该元素的前驱或者后继来进行替换该结点。这里我们就不上图来说明了。

接下来我们做一些思考，由二叉树查找、二叉树排序树、平衡二叉树、B树我们能得出一个结论，树的高度越小查找的速度越快，当元素的数目一定的时候，怎么样才能使树的高度降低，当然是扩展树的阶数才能降低树的高度，之前很火的什么４Y个URL中查询某个URL等之类的题，我想看到这里的时候大家会有一些想法了吧，等等以后我会对类问题进行一次总结，这次先不谈了。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-68999-2.html