二叉树背景
最初，在进行有序数组遍历的时候，我们采取直观的O(N)遍历法，确保能在数组中找到目标。但，随着N在数学上趋近于无穷，并且顺序遍历是使用了很多次无效比较操作，所以我们进化成了二分查找法，舍弃解不在的那个区间，进而不断缩小区间进行查找，最终我们得到了O(logN)的较优解法，logN和N在函数图像的增长上，logN明显是速率更慢的。
我们在二分查找的时候，就生成了一系列的二分区间，因此，可以使用一颗二叉树来表示这种逻辑结构。
image.png
在计算机中，通常使用这种二叉树来支持一些高效的插入、查询功能，因为他们的时间复杂度比较优秀。
因此，诞生了二叉搜索树，即(root>left && root<right)的一个递归结构。
红黑树
image.png
红黑树是平衡二叉树的一种实现，为了高效的插入以及平衡查询效率，我们知道严格的平衡二叉树是左右孩子高度差不大于1，然而红黑树不一定能做到。
红黑树的特性，就是节点颜色只有红黑两种颜色，根节点是红色，红色节点的孩子是黑色等。
红黑树是自平衡的，因为他使用二叉搜索树的插入方式，在插入之后进行判定，经过左旋右旋达到平衡状态，在这一点上与AVL树进行了折中，不需要严格的高度差为1。
红黑树依靠它的优秀插入性能和查询性能，在内存中应用非常广泛。比如Java的TreeMap，epoll中存储链接的ctl等。
B+树
image.png
然而，在磁盘寻址的场景下，我们常用的树形结构，变成了B+树。它是一种多路树，原则上也保持着平衡树的性质。
我们了解一个特性，在磁盘寻址中，随机IO要比顺序IO花费的时间要多，因为随机IO需要频繁切换磁道。因此，多路树的优势是树高比较矮，并且数据节点是顺序存储的，从树的根节点开始往下搜索范围的时候是随机IO，到达数据节点的时候就是循序查找了。
B+树每个节点定长存储，如果插入数据使得节点满了，则会分裂。
这一数据结构在数据库中广泛使用，主要用于B树索引。
AVL树
在[计算机科学]中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次[树旋转]来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。 ---引用百度百科
因为实际开发代码中应用还是挺少的，譬如在ConcurrentHashMap中为什么使用的是r-b Tree，因为在插入链表的时候，别的线程是在等待锁的，如果插入的时候消耗的时间复杂度高，则引起等待时间变长。所以采用了r-b Tree。
