【数据结构】二叉搜索树、平衡树、红黑树、B树和B+树深入浅出
红黑树和B树、B+树这些数据结构上学时不是重点，但是在很多地方用处较多。面试也经常被问到。
参考文章
二叉搜索树
二叉查找树（BST）具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
下图中这棵树，就是一颗典型的二叉查找树：
对二叉排序树进行中序遍历可以得到一个递增的有序序列。
二叉排序树的查找过程类似于二分查找。
小灰说的上面这句话是重点。查找所需的最大次数等同于查找树的高度。
方便进行二分查找。
但是二叉搜索树也有缺陷，缺陷体现在插入节点的时候。
假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：
接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？
二叉搜索树的缺点在于多次插入新节点后导致不平衡，失去了二分查找的性质。
这时候引入红黑树来解决这个问题。
平衡二叉树
这里插播一下平衡二叉树。
为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树的节点的时候。要保证任意节点的左、右子树的高度差的绝对值不超过1。
红黑树
红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是RED或BLACK。
通过对任何一棵从根到叶子的简单路径上各个节点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。
需要了解特性和优势。变色和旋转。
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5**.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点**。
什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：
1.向原红黑树插入值为14的新节点：
由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。
2.向原红黑树插入值为21的新节点：
由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。
这里是红黑树的重点，调整分为变色和选择 旋转分为左旋转和右旋转。
B树
真的是这样，每次面试都会问索引。然后再问到B+树和B树。
树的查询效率高，而且可以保持有序。
二叉排序树的查询时间复杂度已经是O(log N)。性能足够高了。但是还不明白为什么不用二叉查找树。
可以看到磁盘IO的次数为4。说明磁盘IO的次数取决于索引树的高度。
既然如此，那么我们就需要把原本瘦高的树结构变得矮胖。这就是B树的特征之1。
上个这个是重点。
B树是一种多路平衡查找树，每一个节点最多包含k个孩子。k称为B树的阶。k的大小取决于磁盘页的大小。
下面来具体介绍一下B-树（Balance Tree）
一个m阶的B树具有如下几个特征：
- 根结点至少有两个子女。
- 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
- 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
- 所有的叶子结点都位于同一层。
-
每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
第1次磁盘IO：
和9比较
第2次磁盘IO：
第3次磁盘IO：
总结
B树与二叉搜索树的优势在于，降低了树的高度。从而降低了磁盘的IO次数。
B+树
B+ 树是B树的一种变种，有着比B树更高的查询性能。
首先回顾下B树的特征
一个m阶的B树具有如下几个特征：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
一个m阶的B+树具有如下几个特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点.
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
下面展示一个B+树
卫星数据
好处
B树与B+树的两点不同
总结
B+树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。