认识二叉搜索树，平衡二叉树，B树，B+树，红黑树

二叉搜索树BST
是一种根节点的值大于左节点，小于右节点的排序树，英文BST。
如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为log2(n+1),其查找效率为O(log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。

平衡二叉树AVL
平衡二叉树在BST的基础上进行了改进，规定左子树和右子树高度差不超过1(每个节点的平衡因子只能是1,0,-1)，使其不会退化为线性链表。AVL在查找和删除时需要进行旋转操作。
AVL树的子节点只有2个，为了提高频繁查找效率，出现了后面的多路平衡树。
非平衡二叉树与平衡二叉树

B树
Balance-Tree，一种多路平衡树。
特点
一个m阶的B树规定了：

1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 。
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划
B+树
特点
B+树每个非叶子结点存放的元素只用于索引作用，所有数据保存在叶子结点。

一个m阶的B+树规定了：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
红黑树

1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点)。
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
优点
红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树广泛用于TreeMap、TreeSet，以及jdk1.8后的HashMap。

————————————————
原文链接：https://blog.****.net/wanderlustLee/article/details/81297253