二叉树、平衡二叉树、红黑树、B树、B+树与B*树
- 2020-10-24 11:30:00
- 六月
- 来源：
- https://www.jianshu.com/p/b597aa97c9de
- 转贴 931
一、 二叉树
二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大
二、平衡二叉树
1、概念
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。
2、规则
平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：
①非叶子节点只能允许最多两个子节点存在。
②每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)。
三、红黑树
1、为什么有了平衡树还需要红黑树？
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
2、红黑树的特性
显然，如果在插入、删除很频繁的场景中，平衡树需要频繁调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：
①每个节点或者是黑色，或者是红色。
②根节点是黑色。
③每个叶子节点(NIL)是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点]
④如果一个节点是红色的，则它的子节点必须是黑色的。
⑤从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径]
四、B树(B-tree)
B树和B-tree，其实是同一种树。
1、概念
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)，数据库索引技术里大量使用B树和B+树的数据结构。
2、规则
①排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则。
②子节点数：非叶子节点的子节点数>1，且<=M ，且M>=2，空树除外(注：M阶代表一个树节点最多有多少个查找路径，M=M路，当M=2则是2叉树，M=3则是3叉)。
③关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注：ceil()是个朝正无穷方向取整的函数。如ceil(1.1)结果为2)。
④所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null
1、概念
B+树是B树的一个升级版，B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定？
2、规则
①B+跟B树不同。B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加。
②B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样。
③B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
④非叶子节点的子节点数=关键字数(百度百科。根据各种资料，这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1(维基百科)，虽然数据排列结构不一样，但其原理还是一样的。
Mysql 的 B+树是用第一种方式实现)。
1、规则
B*树是B+树的变种，区别如下：
①首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，B*树的初始化个数为cei(2/3*m)。
②B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针)，如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来。
2、特点
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；
