java面试题之二叉树、红黑树、B树、B+树、B*树

1.二叉树

所有的非叶子节点至多拥有两个儿子（left和right），所有节点存储一个关键字，非叶子节点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树,如下图所示

在二叉树查询时，最坏的情况下查找的次数是树的高度，即io次数为树的高度。

2.红黑树

是一种自平衡的二叉查找树，除了符合二叉搜索树的基本特性外，还具有单独的规则约束：

①节点是红色或黑色

②根节点是黑色

③每个叶子节点都是黑色的空节点（NULL节点）

④每个红色节点的两个子节点都是黑色

⑤从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点；

在删除或插入节点的时候，就会打破这些规则，这时候需要作出调整，调整的方法有两种，变色和旋转，其中旋转包括左旋转和右旋转；
变色：将一个或多个节点颜色变成相反色，以使得红黑树符合上述五条规则；

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。

3.B树

B是balanced的意思,是在二叉查找树的基础上增加了平衡的性质 导致它不是 二叉树了，变成了多叉树，但是叉几路又有了限制 否则怎么平衡呢

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

①根结点至少有两个子女；

②每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；（这是百度词条上给出的，应该说在第几层就最多只有m个孩子，容易理解,其中m>=2;如果是最少的话，应该是m/2取上限）

③除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；

④所有的叶子结点都位于同一层。

除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数，最屁也是2个孩子）；

B树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

可以看到，B树中，关键字集合分布在整棵树中，且任何一个关键字出现且只出现在一个节点中，因此搜索可能在非叶子节点结束，其搜索性能等价于在关键字全集内做一次二分查找；B树的性能总是等价于二分查找（与M值无关），也就没有B树平衡问题；

4.B+树

B+树是基于B-树的，增加了如下规则：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

所以，B+树对比B-树有如下好处：

io次数少：b+树中间节点只存索引，不存在实际的数据，所以可以存储更多的数据。索引树更加的矮胖，io次数更少。
性能稳定：b+树数据只存在于叶子节点，查询性能稳定
范围查询简单：b+树不需要中序遍历，遍历链表即可。

5.B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；