【零基础学java】(红黑树)

红黑树：是一个二叉查找树，但是不是高度平衡的，要满足特定的红黑规则。，红黑树的增删改查性能非常好

红黑规则：

1.每一个节点或是红色或是黑色

2.根节点必须是黑色

3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil视为叶节点，每个叶节点是黑色的

4.如果一个节点是红色，那么他的子节点必须是黑色（不能出现两个红色节点相连的情况）

5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

红黑树添加节点

根节点必须为黑色

添加非根节点时，

若父节点是黑色，则不需要做任何操作

若父节点是红色---------叔叔是红色时，将父节点设为黑色，叔叔设为黑色

将祖父设为红色

如果祖父为根，再将跟变为heise

如果祖父非根，将祖父设置为当前节点再进行其他判断！！！

-----------叔叔黑色，当前节点是父的右孩子，把父设置为当前节点并左旋，再进行判断

-----------叔叔黑色，当前节点是父的左孩子，将父设为黑色

将祖父变为红色

以祖父为支点进行右旋