序言
为什么需要树这种数据结构？
数组，查找很快，但是增删慢。
链表，插入和删除很快，但是查询速度慢。
我们希望有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是树诞生了。
二叉树
二叉树支持动态的插入和查找，保证操作在Oheight)时间，这就是完成了哈希表不便完成的工作，动态性。
但是二叉树有可能出现worst-case，如果输入序列已经排序，则时间复杂度为ON)平衡二叉树/红黑树就是为了将查找的时间复杂度保证在OlogN)范围内。
如果输入集合确定，所需要的就是查询，则可以考虑使用哈希表；如果输入集合不确定，则考虑使用平衡二叉树/红黑树，保证达到最大效率平衡二叉树主要优点集中在快速查找。
每个结点最多有两颗子树
二叉树是递归定义的。
二叉查找树
我们来思考这么一个问题，如何在n 个动态的整数中搜索某个整数？（查看其是否存在）
看着还是很简单的，以动态数组存放元素，从第0个位置开始遍历搜索，运气好的话，第一个就找到了，运气差的话，可能找到最后都找不到，算一下的话平均时间复杂度是 On)，数据规模大的话，是比较慢的 再好一点的话，上一篇 二分查找及其变种算法 说到了，使用二分查找的话，效率是很高的，最坏时间复杂度：Ologn)，不怕你数据规模大，但是我们要注意一点，这是一个动态的序列，而前面也说到了二分查找针对的是有序集合，那么维护这样的一个有序的集合，每次修改数据，都需要重新排序，添加、删除的平均时间复杂度是On)，对于这种动态的数据集合，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。 那么针对这个需求，有没有更好的方案？能将添加、删除、搜索的最坏时间复杂度均可优化至：Ologn)，主角登场，二叉搜索树可以办到。
平衡二叉树
AVL树
2-3树
2-3-4树
B树
文件系统和数据库系统一般都采用树（特别是B树）的数据结构数据，主要为排序和检索的效率。二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序一样，虽然因为效率问题并不实用，单不失一种教学例子的好手段。
B+树
为什么文件存储要选用B+树这样的数据结构？
因为要降低搜索一个文件的IO的次数。
比如一个1000度的B树，磁盘上面有10亿个文件的话，B树只需要4次就好了。其他的数据结构做不到。
磁盘很慢，当涉及到磁盘的输入输出的时候，CPU的时间就已经可以忽略不计了，数据结构的设计要集中考虑到尽可能降低IO的次数，所以B树应运而生。
MySQL数据库的索引就是基于B+树。
红黑树
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 Ologn)，不过却不是最佳的。
因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。
红黑树具有如下特点：
1、具有二叉查找树的特点。
2、根节点是黑色的；
3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。
正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 Ologn) 的时间复杂度查找到某个节点。
不过，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。
不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。
所以，我们也可以说，红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。
而关于红黑树的应用，一个非常经典的就是JDK1.8的HashMap中，当链表长度超过8时，就会由链表变成红黑树
小结：
有了二叉查找树、平衡树（AVL）为啥还需要红黑树？
平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。