红黑树
本篇文章看完，可以看hashmap源码分析，源码逐行解释 红黑树模拟网站cs.usfca.edu/~galles/visualization/RedBlack.html
定义
红黑树是一种含有红黑节点并能自平衡的二叉查找树(左节点小于父节点，右节点大于父节点)性质
每个节点要么是红色，要么是黑色
根节点是黑色
每个叶子节点(NIL,虚拟节点,value为null)是黑色
每个红色节点的两个子节点一定都是黑色
任意一节点到每个叶子节(NIIL)点的路径都包含数量相同的黑节点
红黑树的平衡性
红黑树并非完美平衡的二叉查找树，是完美黑色平衡的二叉查找树红黑树的自平衡每次只考虑CPGU三代即可，其余部分无需考虑 祖父母G-Grandparents父母P-Parents叔叔U-Uncle兄弟B-Brother根R-Root当前新增节点C-Current 红黑树自平衡性的原子操作 变色旋转，包括左旋和右旋红黑树的查找操作
即二分查找红黑色的新增操作
需要考虑的几种情况
情况1：c == root情况2：c.parent.color == black情况3：c.parent.color == red && c.uncle == red情况4：c.parent.color == red && (c.uncle == black || c.uncle == null)针对上满几种情况的处理办法
对上面4种情况举例分析
情况1：c == root
设置新增节点为红色修改新增节点颜色为黑色情况2：c.parent.color == black
设置新增节点为红色情况3：c.parent.color == red && c.uncle == red
设置新增节点为红色父节点变成黑色叔叔节点变成黑色祖父节点变成红色如果祖父借你单变红导致不满足红黑树的性质，将祖父及诶单作为新增节点，递归处理前4步情况4.1c.parent.color == red && (c.uncle == black || c.uncle == null)且新增节点、父亲节点、祖父节点三点一线
以父节点为圆心，旋转祖父节点给父节点和祖父节点变色，使其满足性质情况4.2c.parent.color == red && (c.uncle == black || c.uncle == null)且新增节点、父亲节点、祖父节点三角关系
以新增节点为圆心，旋转父亲节点，也就是将三角关系转换为三点一线关系按照情况4.1方法来处理本篇文章看完，可以看hashmap源码分析，源码逐行解释
