红黑树详解
红黑树是一种重要的数据结构，在jdk中有广泛的应用。
Map的实现类中，如TreeMap,HashMap,ConcurrentHashMap等都是使用红黑树作为其底层数据结构。红黑树的查找、插入、删除都有着固定的算法，不管是哪一种编程语言，都是对这种算法的实现。因此掌握红黑树的这些算法思想，在阅读源码的时候对照着流程看会起到事半功倍的效果。在讲红黑树之前，先简单了解下其他树结构的定义。
二叉树：每个节点最多有两个子树的树结构。
二叉查找树：将所有节点映射到水平轴，键不重复，值从左到右依次递增的二叉树。
红黑树：能够完成自平衡的二叉查找树。
由此可见，红黑树是二叉查找树的升级版，解决了特殊情况下树结构层级过深导致查找慢的问题。先通过一张图感性认识下红黑树。在java中nil节点就是null节点。
红黑树的插入和删除操作涉及到了众多的操作场景，要掌握红黑树的这些算法，大量的练习是必不可少的，推荐一个红黑树动态生成的网址，能够形象地展示其生成过程，在阅读操作场景的时候对比使用。
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
1.性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。（黑节点的两个子节点可以是两黑、两红、一黑一红）
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
2.key值特征：
将树节点的key值映射到水平轴上（x轴），key值从左到右递增。不管插入还删除，树结构的最终状态都是符合这个特征的。
3.自平衡（左旋、右旋、变色）：
通过旋转，使两边的节点数差不多。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
变色：红黑树节点从红色变为黑色，或者从黑色变为红色。
4.节点查找：
查找最坏时间复杂度为O(2lgN)
Key值从左到右递增，采用的递归算法，二分法思想。
5.节点插入：
节点插入步骤：
1.查找插入的位置,返回的是子节点为空的父节点。
2.插入的场景分析。
3.注意，插入的节点为红色！
8中基本场景
更改：情景4.3.2：插入节点是其父节点的左子节点
6.节点删除：
替代节点的查找
情景1：若删除结点无子结点，直接删除
情景2：若删除结点只有一个子结点，用子结点替换删除结点
情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点即子树的最左节点）替换删除结点。
删除步骤：
1.查找替代节点。因为从最终结果看，就像是删除了替代节点一样，而替代结点最后总是在树末。
2.删除节点和替代节点相关引用的替换。如左子树left，右子树right，父节点parent。
3.删除操作场景分析。
9中基本场景
更改：2.1.1重新进入场景2.1.2处理；2.2.1重新进入场景2.2.2处理
删除场景总结：自己能够搞定的自己消化；不能搞定的找兄弟帮忙；兄弟帮不了的，通过父母，找远方亲戚。
特别声明，本文的知识点只要来自以下作者博客：