#Java

红黑树

是一种自平衡的平衡二叉树，是计算机科学中用到的一种数据结构。1972年，出现时，被称为平衡二叉B树，1978年被修改为如今的“红黑树”。

是一种特殊的二叉查找树，红黑树的每一个节点上都用存储位表示节点的颜色，每一个节点可以是红或黑；红黑树不是高度平衡的，他的平衡是通过“红黑规则”进行实现的。

红黑规则:

1. 每一个节点或者是红色的，或者是黑色的。
2. 根节点必须是黑色的
3. 如果每一个节点没有子节点或者父节点，则该节点响应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）都是黑色的。
4. 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
5. 对每一个节点，从该节点到其所有后代叶节点的简单路径（不能回头，只能往前）上，均包含相同数目的黑色节点。

添加节点:

• 添加节点的颜色，可以是红色的，也可以是黑色的。
• 添加三个元素，默认颜色为黑色，一共需要调整两次
• 添加三个元素，默认颜色为红色，一共需要调整一次。所以，添加节点时，默认为红色，效率高

添加节点的小结:

添加节点默认是红色的。

flowchart LR
    A(添加节点)-->B(根节点位置)-->C(直接变成黑色)
    A-->D(非根节点位置)-->E(父节点为黑色) & F(父节点为红色)
    E-->G(则不需要任何操作)
    F-->H(叔叔节点为红色) & I(叔叔节点为黑色)
    H-->H1(1.将父节点设为黑色, 将叔叔节点设为黑色)
    H-->H2(2.将祖父节点设为红色)
    H-->H3(3.如果祖父节点为根节点, 则将根节点再次变为红色)
    I-->I1(1.将父节点设为黑色)
    I-->I2(2.将祖父节点设为红色)
    I-->I3(3.以祖父节点为支点进行旋转)