在开始讨论JAVA中的红黑树之前，就前几篇关于二叉树的文章做个总结。
平衡二叉树：高度差绝对值不超过1，任意节点左右子树均为平衡二叉树。
AVL树：平衡二叉树只是一个概念，AVL树，红黑树都是这个概念的落地实现。AVL树其实就是《手撕JAVA十三》一文中说的通过RR，RL，LL，LR旋转而成的平衡二叉树。这些旋转都属于AVL树的算法。
红黑树：由红黑两种颜色组成，根节点必为黑色，无连续红节点，各节点到叶节点路径上黑色节点数量相同。
红黑树与AVL树的优缺点比较：
1.红黑树并非严格平衡，高度差可能会超过1，AVL树严格平衡，高度差绝对值不超过1，所以AVL的查找效率比红黑树高。
2.插入删除操作红黑树的旋转操作次数要远小于AVL，所以插入删除效率红黑树远高于AVL树。
所以简单说，如果搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
JAVA的设计者基于以上各方面考虑最终选择了红黑树作为JAVA中基于平衡二叉树的数据结构中底层的平衡二叉树的实现。
JAVA中基于红黑树实现的容器类，有treeMap，TreeSet。先来看TreeMap的源码
TreeMap
首先内部自定义有一个节点类，默认颜色为黑色。
接下来从put方法开始跟踪插入操作
插入操作，首先判断了根节点是否为null，是null，来的节点直接就做根节点。
如果根节点不为null，就会一路比较，先找到节点该插入的位置，插入后调用fixAfterInsertion方法
首先是染红，然后接下来的调整其实就是严格按照之前《手撕JAVA十五》讨论过的算法来进行。
至于删除，跟入此函数会发现也是严格按照《手撕JAVA十六》一文中的算法来实现的。
TreeSet
至于TreeSet底层实现其实就是个TreeMap，只是将KV对中的V通过一个Object类型的常量封起来了，只暴露出来了K给用户操作。
