红黑树
一、定义
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在普通的二叉搜索树的基础上增加了一些额外的规则来保持树的平衡性，可以叫平衡二叉B树
二、红黑树的性质
只要满足以下5个性质的二叉树，一定是红黑树
- 节点是RED或者BLACK
- 根节点是BLACK
- 叶子节点（外部节点和空节点）都是BLACK
- RED节点的父、子节点必然是BLACK，即从根节点到叶子节点的路径上不能有两个连续的RED节点
- 从任一节点到叶子节点的所有路径都包含相同数目BLACK节点
三、红黑树与4阶B树
红黑树与4阶B树（2-3-4）树具有等价性
红黑树的BLACK节点与它的RED子节点融合在一起，形成 一个B树节点。
红黑树的BLACK节点个数与4阶B树的节点总个数相等。
四、添加红黑树
1、新添加的节点值默认为红色节点，这样可以保证尽快满足性质1、2、3、5，只需要解决4的情况。
2、如果添加的是根节点，染成黑色即可。
3、有4种情况满足红黑树的性质4：parent为BLACK。将红黑树结合形成4阶B树，满足了4阶B树的性质，所以也满足红黑树的性质，不需要做额外的处理。
父节点为黑色的以下四种情况：新添加的节点为红色，兄弟节点为红色或者为空。对于4阶B树的红黑树，黑色节点一定是父节点，同上面红黑树与4阶B树的性质。所以兄弟节点要么为空，要么为红色。
4、有8种不满足红黑树的性质4：parent为RED（DOUBLE RED）的情况。
以下情况：LL、RR、LR、RL的情况。
LL和RR的解决方法：如果uncle节点不是RED（为BLACK或者null），1、将parent染成BLACK,将grandParent染成RED。对grandParent进行单旋转，如果是LL进行右旋转，如果是RR进行左旋转。
LR和RL的解决方法：
- 如果uncle节点不是RED（为BLACK或者null），1、将自己（新添加的节点）染成BLACK,将grandParent染成RED。对grandParent进行双旋转，先对parent旋转，再对grandParent旋转。
- 如果uncle节点是RED（为BLACK或者null），1、将parent和uncle染成BLACK,将grandParent向上合并。把grandParent染成RED，并且当成新增的节点（递归），进行旋转操作（上溢）。如果上溢到根节点，只需要将根节点染成BLACK。
五、删除红黑树
为了满足4阶B树的性质，删除红黑树的节点一定是B树的叶子节点。也就是说，真正被删除的节点一定是最后一层的树节点，即需要移除元素的前驱或者后继节点。
根据最后删除的是RED或者BLACK节点，分为以下情况：
1、如果删除的是RED节点，依然是一颗红黑树，因为红色的在底部的节点就是单独的节点存在。
2、如果删除的是BLACK节点：
- 有两个子节点（如果是在底部必定是红色，根据4阶B树和红黑树的性质），不可能被直接删除，根据二叉搜索树的性质。度为2的节点，删除前驱或者后继节点。
- 拥有一个RED子节点，RED子节点替代BLACK节点，用以替代的RED子节点染成黑色。这样就能保持红黑树的性质。
- 没有子节点，如果是根节点，不需要做任何处理。如果是非根节点（4阶B树性质下溢）。
- 如果sibling节点是黑色（兄弟节点一定会有，如果没有sibling节点，说明被删除的节点一定是红色，否则不满足4阶B树和红黑树的性质），并且拥有至少一个RED子节点。根据场景进行旋转，如果删除的节点是右节点，sibling节点是左节点，sibling节点的红色子节点是左子节点，需要将删除节点的parent节点进行右旋转（LL），如果红色子节点为右子节点，先进行左旋转，再进行右旋转（LR）。旋转以后的中心节点与原来的中心节点颜色一致，即如果被删除的节点的parent节点是红色节点，旋转以后的中心节点也要改变成红色。 旋转以后的左右节点，改为黑色（满足4阶B树和红黑树的同等性质，一个黑色节点对应一个4阶B树的节点）。
- 如果sibling节点是黑色，但是它没有子节点。将sibling节点染成RED，parent节点染成BLACK。如果parent节点原来是黑色，根据4阶B树的性质，parent节点还是存在下溢，将parent节点当做被删除的节点继续往上递归。
- 如果sibling节点是红色。把sibling节点染成BLACK，parent染成RED，将parent节点进行旋转，如果被删除的节点是右子节点，则进行右旋转。如果是左子节点，则进行左旋转。旋转以后，就变成了上面的两种情况。sibling节点是黑色的情况。
六、红黑树的平衡
红黑树的5条性质可以保证红黑树等价于4阶B树。B树是一颗平衡搜索树。
相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其它路径的2倍。
红黑树的平衡是一种弱平衡、黑高度平衡：任意节点到叶子节点的路径，黑色节点个数一致。
红黑树的最大高度是2*log2(n+1)，依然是O(logN)级别。
七、实现
/**
* @Description 红黑树
* @Author lcy
* @Date 2020/11/17 11:13
*/
public class RedBlackTree<E> extends BalanceBinarySearchTree<E> {
/**
* 红色节点
*/
private static final boolean RED = true;
/**
* 黑色节点
*/
private static final boolean BLACK = false;
public RedBlackTree(Comparator<E> comparator){
super(comparator);
}
public RedBlackTree(){
super(null);
}
@Override protected void afterAdd(Node<E> node){
Node<E> parent = node.parent;
//如果是根节点
if (parent == null) {
//变成黑色
changeBlack(node);
return;
}
//如果父节点是黑色--维持红黑树平衡，不需要操作
if (isBlack(parent)) {
return;
}
//获取uncle节点--叔父节点
Node<E> uncle = parent.sibling();
//祖父节点--祖父节点一定染成红色
Node<E> grandParent = changeRed(parent.parent);
//叔父节点是红色
if (isRed(uncle)) {
//父节点和叔父节点染成黑色
changeBlack(parent);
changeBlack(uncle);
//将祖父节点当成新添加的节点处理
afterAdd(grandParent);
return;
}
if (parent.isLeftChild()) {
if (node.isLeftChild()) {
//LL--父节点染成黑色，祖父节点染成红色
changeBlack(parent);
} else {
//LR--当前节点和祖父节点染成黑色，父节点染成红色
//父节点左旋转，祖父节点右旋转
changeBlack(node);
rotateLeft(parent);
}
rotateRight(grandParent);
} else {
if (node.isLeftChild()) {
//RL--当前节点和祖父节点染成黑色，父节点染成红色
//父节点右旋转，祖父节点左旋转
changeBlack(node);
rotateRight(parent);
} else {
//RR--父节点染成黑色，祖父节点染成黑色,左旋转
changeBlack(parent);
}
rotateLeft(grandParent);
}
}
@Override protected void afterRemove(Node<E> node){
//二叉搜索树删除以后的操作，如果删除的节点是度为2的节点，即有两个子节点，node为该节点的后继节点。
//如果替换的节点是红色
//如果是删除的节点是红色节点，直接删除。如果是用于取代删除节点的子节点是红色，进行染色。然后直接返回。
if (isRed(node)) {
//改成黑色，保持4阶B树和红黑树性质，根节点一定要有黑色，因为删除了黑色节点，必须重新生成一个黑色。
changeBlack(node);
return;
}
Node<E> parent = node.parent;
//如果黑色节点是根节点--不需要处理
if (parent == null) {
return;
}
//兄弟节点--如果是叶子节点，parent已经不指向node了。即原本指向node节点的指针已经为null。
//但是如果是下溢的情况，parent递归调用，因为parent的父节点还是它，所以要再增加一个不为空的情况判断。
boolean left = parent.left == null || node.isLeftChild();
//如果node节点是左子节点，取右子节点
Node<E> siblingNode = left ? parent.right : parent.left;
//如果被删除的子节点在左边
if (left) {
//如果被删除的子节点在左边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateLeft(parent);
//兄弟节点改变
siblingNode = parent.right;
}
} else {
//如果被删除的子节点在右边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateRight(parent);
//兄弟节点改变
siblingNode = parent.left;
}
}
//兄弟节点是黑色,一定是黑色
//如果兄弟节点的子节点都是黑色
if (isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
//如果都不为黑色，说明没有子节点。因为没有子节点，父节点要向下合并。即染色
boolean isParentBlack = isBlack(parent);
changeBlack(parent);
changeRed(siblingNode);
//如果父节点是黑色，说明上面的节点还存在下溢
if (isParentBlack) {
//相当于二叉搜索树的叶子节点
afterRemove(parent);
}
} else {
if (left) {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.right)) {
rotateRight(siblingNode);
siblingNode = parent.right;
}
//对父节点进行右旋转
rotateLeft(parent);
} else {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.left)) {
rotateLeft(siblingNode);
siblingNode = parent.left;
}
//对父节点进行右旋转
rotateRight(parent);
}
//旋转以后中心节点的颜色为parent的颜色，新的子节点颜色为黑色
changeColor(siblingNode,colorOf(parent));
changeBlack(siblingNode.left);
changeBlack(siblingNode.right);
}
}
@Override protected Node<E> createNode(E element,Node<E> parent){
return new RedBlackNode<>(element,parent);
}
/**
* 节点染色
* @param node 传入节点值
* @param color 颜色
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<E>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<E> changeColor(Node<E> node,boolean color){
if (node == null) {
return node;
}
//节点染色
((RedBlackNode<E>)node).color = color;
return node;
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<E>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<E> changeRed(Node<E> node){
return changeColor(node,RED);
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<E>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<E> changeBlack(Node<E> node){
return changeColor(node,BLACK);
}
/**
* 获取当前节点的颜色
* @param node 节点对象
* @return boolean
* @author lcy
* @date 2020/11/25 14:09
**/
private boolean colorOf(Node<E> node){
return node != null ? ((RedBlackNode<E>)node).color : BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isBlack(Node<E> node){
return colorOf(node) == BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isRed(Node<E> node){
return colorOf(node) == RED;
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class RedBlackNode<E> extends Node<E> {
/**
* 节点颜色，红色为true，黑色为false。新添加的默认为红色节点
*/
boolean color = RED;
public RedBlackNode(E element,Node<E> parent){
super(element,parent);
}
@Override public String toString(){
return element.toString() + "(" + (color ? "red" : "black") + ")";
}
}
public static void main(String[] args){
int[] ageArray = {44,31,3,2,6,88,34,13,32,77,74,35,89,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5,7,9,45,33,8};
int[] weightArray = {144,131,103,102,106,188,134,113,132,177,174,135,189,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5
,7,9,45,33,8};
RedBlackTree<Person> redBlackTree = new RedBlackTree<>(Comparator.comparingInt(Person :: getAge));
for (int i = 0; i < ageArray.length; i++) {
redBlackTree.add(new Person(ageArray[i],weightArray[i],String.valueOf(i)));
}
System.out.println("-------------print-------------");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(new Person(8,2,""));
System.out.println("删除8！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(new Person(35,2,""));
System.out.println("删除35！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(new Person(90,2,""));
System.out.println("删除90！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(new Person(97,2,""));
System.out.println("删除97！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(new Person(74,2,""));
System.out.println("删除74！");
BinaryTrees.print(redBlackTree);
System.out.println();
System.out.println("-------------print-------------");
}
}