红黑树定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
- 每个节点要么是黑色，要么是红色。
- 根节点是黑色。
每个叶子节点（NIL）是黑色。
- 每个红色结点的两个子结点一定都是黑色。
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
|  |
自平衡
三种操作：左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
变色：结点的颜色由红变黑或由黑变红。
|  |
|  |
红黑树的查找
红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异。
HashMap中的红黑树是根据节点key的hash值大小，其次是比较compare，如果都相等或者无法比较，就执行一个内置的方法打破僵局。
TreeMap的红黑树，只用比较的方式，因为是有序的，TreeMap不允许key为null。
红黑树的插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大。
红黑树的删除
二叉树删除结点找替代结点有3种情情景：
- 情景1：若删除结点无子结点，直接删除；
- 情景2：若删除结点只有一个子结点，用子结点替换删除结点；
- 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点。
删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！
基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！
情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（对于红黑树来说，根据性质5.1，只存在一个子结点的结点肯定在树末了）
情景3：删除结点用后继结点（肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。
综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。
|  |
Tagged #Java集合.