数据结构之二叉树家族2
上一篇文章介绍了二叉树及其遍历，这篇文章主要来介绍其他几种常见的数据结构的树：
二叉查找树
平衡二叉树
红黑树
B+树
具有功能性的树：二叉查找树、平衡二叉树。
二叉查找树在我看来，具有功能性，被我强调的功能二字主要就体现在它的查找二字上，依次围观一下二叉查找树的各项介绍：
基本结构：
(1) 除叶子节点外，每个节点都有两个子节点。
(2) 若有左子节点，左子节点的值小于父节点的值。
(3) 若有右子节点，右子节点的值大于父节点的值。
特点：
支持动态数据集合的快速插入、删除、查找操作。
查找时间复杂度：O(logn)
最坏时间复杂度：当二叉查找树退化为链表时，查找时间复杂度为O(n)，这一点也是二叉查找树的缺点。
应用：
如果说到二叉查找树的应用，那不得不提查找非常优秀的HashMap（查找时间复杂度为O(1)）, 这两者都主打查找功能，所以在应用时有需要权衡的点有哪些：
(1) HashMap查找时间复杂度为O(1)，但不足之处是会牵扯到扩容、哈希碰撞、装载因子等一系列问题。
(2)中序遍历二叉查找树之后，在O(n)的时间复杂度下能输出一个有序数组。
所以，在实际应用中可以权衡二者的利弊，再选择适合自己需求的数据结构。
平衡二叉树：
它的产生，其实是为了解决二叉查找树退化为单链表的情况。
基本结构：
(1) 首先是一个二叉查找树。
(2) 是一个完全二叉树，也就是叶子节点从左往右排布在结构上是连续的，中间没有断开。
特点：
能满足二叉查找树快速插入、删除、查找的操作。
最坏查询时间复杂度：O(logn)
不足之处：每次进行完插入删除操作后，平衡二叉树都要为了维护它的完全二叉树的结构而左旋/右旋。
应用：
可以用在查询次数较多，但删除和插入操作很少的情境中。
红黑树：
它的产生是为了降低平衡二叉树在频繁插入删除操作后，又得维护它的结构而耗费的时间复杂度。
基本结构：
具有二叉树的基本结构
根节点是黑色
红节点被黑节点隔开
从任意节点出发，可达其叶子节点里的所有路径，包含相同数目的黑节点
特点：
查询时间复杂度：O(logn)
RBTree.jpg
应用：
红黑树在工程中的应用很广泛，但我们日常能见到的，即HashMap底层就使用了红黑树。
B+树：
基本结构：
- 每个节点的子节点数不超过m, 也不小于m/2;
- 根节点的子节点个数不超过m/2;
- 叶子节点储存数据，其他节点仅储存索引；
- 通过链表将叶子节点串联在一起，方便区间查询；
- 一般情况下，根节点储存在内存中，其他节点在磁盘中。
B+与B树的区别：
- B树的每个节点都储存数据，B+树仅叶子节点储存数据；
- B树的叶子节点没有链表串联起来，B+树的叶子节点用链表串在一起；
- B树遍历是必须用中序遍历的方法，按顺序扫库，B+树直接扫一遍叶子节点就结束了。
应用：
B+树作为一种查找效率高，且存储空间小、执行效率高的数据结构，MySQL的InnoDB 用它来作索引。
