红黑树与平衡二叉树和b树,4阶b树

一、二叉树是每个节点最多有两个子树的有序树，子树的根称为左子树和右子树。 二叉树常用作二叉树的搜索树和二叉树的山或二叉树的排序树。 不对叶节点、分支节点、根节点这些基本概念进行说明。二叉树性质：

二叉树的i层最多有2i-1个节点。 深度为k的二叉树最多具有2k-1个节点。 在任何二叉树中，如果2度的节点数为n2个，则叶数n0一定是

n2 1即n0=n2 1 二叉树分类：

1、完全二叉树以二叉树高度为h，除第h层外其他各层(1~h-1 )的节点数达到最大个数，第h层有叶节点，叶节点从左向右依次排列的为完全二叉树。

性质：

具有n个节点的完全二叉树的深度可能对int(log2n ) 1前k-1层节点均为“满”的第k层不满意，且节点偏左聚集的叶只出现在最后两层。 对于任意节点，如果将其右枝下的子孙的最大层次设为l，则其左枝下的子孙的最大层次必须为l或L 1。 也就是说，度为1的点为只有最后一片叶子的1或0个，且有左子女无右子女，其余非叶结节度均为2 2，满二叉树除叶结节外所有节点均有左右子叶，叶节点均为最底层二叉树。性质：

任何充满二叉树的节点都“填满”每个层的节点，这取决于度是0还是2。 即每层i的节点数最大值2i -1二叉树与完全二叉树有区别。

二叉树是至少有一个节点的树，而完全二叉树前面的k-1层是满的，但最底层允许缺少右侧连续的几个节点。

二、平衡二叉树(AVL )是一种空树，或具有以下性质的二叉树：

左侧子树和右侧子树深度差(平衡因子)的绝对值小于等于1，而左右子树是平衡二叉树的主要使用场景。 使用windows管理进程地址空间

二叉树的平衡调整有四种情况。 分别是LL、LR、RR、RL。 关于这四个案例的具体调整过程请看本博客：

二叉树(AVL )的图解与实现

三、红黑树红黑树是各节点具有颜色属性的自平衡二叉树，都是在插入和删除操作时通过特定操作保持二叉树的平衡，获得较高的搜索性能。

除了四元查找树的一般要求外，还为有效的红黑树添加了以下附加要求：

节点为红色或黑色。 根节点是黑色的。 每个叶节点(NIL节点、空节点)为黑色。 每个红色节点的两个子节点是黑色的。 (从每个叶到根的所有路径不能有两个连续的红色节点)从其中一个节点到每个叶的所有路径都包含相同数量的黑色节点。 红黑树通过旋转和变色达到自我平衡。 具体过程可浏览以下博客：

30张图让你彻底了解红黑树

使用场景： map、set和Linux文件管理

四、B/B树1、b树b树是多叉树别名平衡多重搜索树，一般说m阶b树，必须满足以下条件：

每个节点最多只有m个子节点。 每个非叶节点(根节点除外)至少有m/2个子节点。 如果根不是叶节点，则根至少有两个子节点。 具有k个子节点的非叶节点包含k -1个密钥。 所有叶出现在同一水平上、没有任何信息的(高度一致的) b树的一个节点的子节点数的最大值用m表示，如果最大值为10则为10次。 例子如下。

在所有节点中，节点【13、16、19】具有最多的子节点，是4个子节点(灰色节点)，因此上面的图像可以定义为4阶b树。

排序方式：在b树中，所有节点密钥按升序排列，遵循左小右大原则。 而且，在该节点的孩子是非叶节点的情况下，该k-1个密钥正好是k个孩子所包含的密钥的值域的分隔。

有关查询、插入和删除Web树的流程，将显示本文。 是b树和b树

2、b树b树是文件系统所需的b树的变形树。 b树更充分地利用节点空间，使查询速度更稳定，速度完全接近二分法搜索。

特征：

具有m个子树的中间节点包含m个元素(在b树中为k-1个元素)，每个元素不存储数据，只用于索引。 所有叶节点包含所有关键字的信息和指向包含这些关键字的记录的指针，叶节点自身按照关键字大小从小到大的顺序链接； 的所有非终结节点都可以视为索引部分，该节点只包含其子树的根节点中最大(或最小)的关键字。特点

较低的b树级别：由于树级别比为b树b中的每个非叶节点存储的关键字少，因此对数据的查询速度更快。 b树查询速度更稳定： b由于叶节点上存在所有关键字数据地址，每次查询次数相同，因此查询速度比b树稳定的b树自然具有排序功能。 b树中所有叶节点的数据组成有序的链表，在查询大小区间的数据时方便，数据紧密性强，缓存命中率也高于b树。 b树全

节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

使用场景：磁盘文件组织数据索引和数据库索引

五、相关面试题 1、为什么说B+树比B树更适合数据库索引？

（1）B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

（2）B+树查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

（3）B+树便于范围查询
B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

B树的范围查找用的是中序遍历，而B+树用的是在链表上遍历；

2、B树的缺点

不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找

3、B树与B+树的区别： B+树内部有两种结点，一种是索引结点，一种是叶子结点；B树没有索引结点。B+树的索引结点并不会保存记录，只用于索引，所有的数据都保存在B+树的叶子结点中；而B树则是所有结点都会保存数据。B+树由于叶子结点都有链表，且链表是以从小到大的顺序排好序的，因此可以直接通过遍历链表实现范围查找，而B树不支持范围查找。B树的所有索引值是不会重复的，而B+树非叶子结点的索引值最终一定会全部出现在叶子结点中。 4、平衡二叉树优缺点、与红黑树的区别

二叉查找树在某些情况下可以退化为一条链表，这样的二叉查找树的查找时间复杂度变成了 O(n)，为了解决这个问题，于是引申出了平衡二叉树。

优点： 在插入或者删除元素时不需要移动元素，插入和删除的性能较好；

缺点： 平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在插入、删除很频繁的场景中，平衡树需要频繁着进行调整，会使平衡树的性能大打折扣。

与红黑树的区别：

AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，插入最多两次旋转，删除最多三次旋转；平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

参考文章：【数据结构】二叉树