平衡二叉树
平衡二叉树又称为AVL树，AVL树通过旋转（左旋/右旋）来保证二叉排序树的平衡状态，AVL树会保证树的左右子树高度差始终是<=1，AVL树达到的平衡状态是绝对平衡（左右子树的高度差<=1），看下图查看旋转变化：
红黑树
红黑树是实现了自平衡的二叉排序树，但并不是平衡二叉树那样的绝对平衡，它的左右子树相差可以大于1，正如其名，所有的节点要么红色，要么黑色。
保证平衡
旋转
调整节点颜色
根结点必须为黑色
新添加的节点必然是红色，但是添加成功后由于旋转，可能会变为黑色
红黑树的规则
节点为红色或者黑色
根结点为黑色
所有叶子结点是黑色
每个红色节点的左右子树为黑色，也就是说，每个叶子结点到根结点的路径上不能出现两个连续的红色节点
任意叶子结点到根节点的黑色节点数量相同，称作黑高相同
这里说明下叶子结点都为黑色的原因，图中看到的有红色，有黑色，大家应该看到我标出来的红色箭头，每个箭头默认还指着一个隐藏的黑色的为null节点 。
红黑树的应用
TreeMap
TreeSet
由于TreeSet底层调用了TreeMap，所以，我们猜测出，所有的set和map都有这样的关系：
HashSet/HashMap 数据结构为散列表，输出引用，得到的结果为无序结果
TreeSet/TreeMap 数据结构为红黑树 输出引用，得到的结果为中序遍历的结果 -- 升序排列
LinkedHashSet/LinkedHashMap 输出引用，得到的结果为有序的结果
所以，set集合是不可重复的集合，并不是无序的集合，实现类不同，可能就会出现有序的时候。
散列表
散列表其实算是红黑树的范畴，但是其涉及内容太多，所以就单独拉一个大标题来写一些，东西比较多，也是最后一个知识点，看到这里了，不妨继续看下去吧。
应用类为HashMap，散列表是一种数据结构，它的底层实现如下：
JDK1.8之前，散列表的数据结构为数组+链表
JDK1.8开始，散列表的数据结构为数组+链表+红黑树
向散列表中存数据
根据key调用hashCode()方法，得到哈希码值；
哈希码值再调用散列算法，得到一个整数，这个整数就是保存在数组中的下标；
如果散列桶为空，将键值对直接存入，否则用这个准备存入的值和已经存在散列桶中的值进行比较
相等，则新的value覆盖原来的value
否则，在该散列桶中形成链表
hashCode()方法特点
该方法的目的是尽可能的为不同的对象分配不同的整数，其特点如下：
一次程序运行期间，同一个对象多次调用次方法，哈希码值一定相等；
两个对象调用equals方法结果为true，这两个方法调用hashCode()方法生成的整数一定相等；
两个对象调用equals方法结果为true，这两个方法调用hashCode()方法生成的整数可能相等，也可能不同；
链表的产生原因
不同的对象调用hashCode()，可能会形成相同的整数，最终导致下标一致；
不同的对象调用hashCode()，可能会形成不同的整数，不同的整数再调用散列算法后得到相同的下标；
以上这种现象叫做哈希冲突或者哈希碰撞，要降低这种概率的发生，散列表可通过扩容的方式降低发生概率。
链表存在的问题
我们都知道，链表的查询效率是比较低的，若散列桶中只有一个键值对，那直接就能通过下标找到，但是若有多个的时候，通过下标找到后还需要对链表进行查询，这就降低了查询的效率。
所以我们做的就是尽可能减少链表的产生，怎么做呢？
没错，扩容！当数组中元素达到一定的数量后就对数组进行扩容，一般为原长度的两倍。所以要找一个扩容依据。
扩容因数=可保存最大数/总容量
初始状态总容量16，可保存最大数12，当第13个元素出现时，数组就扩容为原来的2倍。
数组的扩容
当数组中元素达到一定的数量后就对数组进行扩容，一般为原长度的两倍，特别注意，此时数组中的元素会重新进行散列。
散列表的初始容量为2的n次方，如果初始值给的不是2的n次方，则会自动给出相近的且大于设置值的2的n次方的值。比如给9，则容量为16，给17，容量为32。
前面说过，JDK1.8之后，散列表的数据结构变为数组+链表+红黑树，所以自JDK1.8开始，当散列表中元素数量超过64，或者散列桶中链表长度等于8时，会将链表转化为红黑树，红黑树的查询效率更高，可提高整体的查询效率。
结语
到这里，这篇博客就要和大家说再见了，基本知识点都有涵盖，如有遗漏或者讲的不对的地方，欢迎指正，也欢迎留言一起探讨数据结构，写作不易，觉得不错就点赞收藏来鼓励下博主吧。
