平衡二叉树、红黑树、B树、B+树
目录
平衡二叉树
红黑树
B树和B+树
B树和B+树的区别
平衡二叉树
平衡二叉树又称平衡二叉搜索树，由于是Adelson-Velsky and Landis二人发明的，所以又叫AVL树。平衡二叉树要求左右子树的高度差不能大于一。所以极限条件下，搜索的时间复杂度是O(logn)。但由于其调整起来十分麻烦，所以并不适用于经常需要进行插入和删除的环境。因此引入红黑树（也是二叉搜索树的一种）来解决这一问题。
平衡二叉树的基础是二叉搜索树，对于一个二叉搜索树而言，新插入的数字若小于根节点则放在左边，反之放在右边。但如果插入的数字一直小于或大于根节点，那这个树，就和链表差不多了。如图，我按顺序插入(1, 0, 3, 2, 4, 5, 6)。
本来二叉树的实现就是为了减低搜索的时间复杂度的，而如果树构建得和单链表差不多，那便失去了意义。所以二叉平衡搜索树，又称平衡二叉树应运而生。
平衡二叉树要求左子树的高度和右子树的高度之不能超过1。
红黑树
红黑树，顾名思义是有红黑两种节点。然而对于红黑树的构成却有许多限制，我们先来看看这些限制。
- 根节点必须是黑色的。
- 子节点要么是红色要么是黑色
- 不能有两个红节点构成亲子关系，即不能有两个连在一起的红节点。
- 从任意节点到叶子节点的所有路径都包含相同数目的黑节点。
- 所有叶子节点都是黑色的，这里的叶子节点指的是最末端的虚拟节点（NULL节点）。个人觉得，设置这些虚拟节点，是为了使限制3不失一般性
通过以上五点设置便可以限制左右子树的高度差在一倍之内。我们不妨设一种极限情况，从根节点出来的左路径全是黑节点，右路径全是红黑交叉的节点。那么由于红节点不能两两相连，且右路径的黑节点数必须和做路径相同，所以右路径的节点是顶多是左路径的两倍。
如果把所有红色节点擦除，那么N个黑色节点所构成的必然是一颗平衡二叉树，搜索时的时间复杂度是logn。那么加上所有红色节点，由于极限情况下，最长路径是纯黑色节点的两倍。故而搜索时间复杂度是2logn，忽略常数项，那么复杂度还是O(logn)。
此外，基于红黑树的限制条件，在插入一个新的节点之后，红黑树的调整次数通常较少，大多数情况下不超过三次旋转。这是因为红黑树的设计允许它在维持平衡的同时允许某种程度的不完全平衡，因此调整的复杂性和频率通常低于AVL树。
至于如何插入节点，仅作了解吧。
首先，除了根节点之外，任何新增的节点都先被视为红节点，然后再进行以下判定。
这里的左旋右旋具体时如何操作的，和平衡二叉树那里基本差不多，所以不赘述了。
由于红黑树在搜索中，时间复杂度是O(logn)，且插入节点所需的调整的频率也低于AVL树，所以应用比较广泛。如C++中map和set这两种容器的底层就是红黑树。
B树和B+树
B树和B+树都是被广泛应用的数据结构。它们最显著的特征便是每一个节点可以存放多个数据，且可以有N个子树。下图是B树的示意图。
在构建一棵B树的时候，需要预先定义它的阶数m，限制一个节点至多存放m-1个值，并且也表明一个节点至多可以有m个子树。故而B树也可以被叫做m叉树。
一颗m叉树的每一个节点大概长这样。
n表示这个节点存放n个数据，k1,k2,…,kn-1是这个节点存放的数据，这些数据从小到达依次排序。p0,p2,…,pn是指向子树的指针。其中p0所指的子树的值全部在0和k1之间，p1所指子树的值全部在k1和k2之间，以此类推。
B树和B+树的区别
顾明思意B+树事B树的升级版，克服了B树的许多缺点，有更高的搜索效率。但它们之间的较量关乎内存和磁盘，我放在最后讲。先来看看B树和B+树在构成上的区别。
1、B+树的每一个子节点都会存储父节点的key，这里的key就是图中节点的值。
2、B+树的所有叶子节点（末端的那些节点）通过指针串在一起。因而B+树除了随机搜索的方式（从根节点开始搜索），还多了一种顺序搜索方式（直接从叶子节点开始按顺序搜索）。
以上两点就是B树和B+树从观感上比较明显的差别。但其核心差距还是在存储方式上。