java基础-红黑树详解

红黑树

特点：

1.每一个节点要么是红色，要么是黑色；
2.根节点必须是黑色；
3.每个叶子节点【NIL】是黑色；
4.每个红色节点的两个子节点必须是黑色；
5.任意节点到每个叶子节点的路径包含相同数量的黑节点；

红黑树场景，图片：

详解

1.红黑树为空

• 把插入节点作为根节点，并把节点设置为黑色；

2.插入节点的父节点为黑节点，

• 直接插入；

3.插入的节点的父节点为红节点

• 叔叔节点存在且为红节点
  • 
    1.将p和S设置为黑色；
    2.将pp设置为红色；
    3.将pp设置为当前插入节点（再套一次规则）
  • 1.加一个5，在10左边，然后叔叔节点是存在的，并且叔叔节点是红节点，所以，父亲节点，叔叔节点全部变成黑色；
  • 2.再将祖父节点设置为红色

• 这个时候了，将祖父节点设为当前插入节点，它就是根节点，默认是黑色，又变成了黑色；

• 

• 叔叔节点不存在/ 或是黑节点
• p是pp的左节点
  • 1.插入节点是p的左节点

  • 

    加一个8，即，1.父节点是红，2.叔叔节点没有，3.当前节点是祖父节点的左节点，4.插入节点是父节点的左节点 ， 即：父节点为红，叔叔没有，在祖父左边，在父节点左边
  • 操作：
  • 1.将p设置为黑；
  • 2.将pp设置为红；
  • 3.对pp进行右旋:

• 

• 1.插入节点是p的右节点

根据规则：

• 插入节点父节点为红色
• 叔叔节点不存在或为黑节点
• 父节点是祖父节点左节点
• 插入节点是父节点的右节点

操作：

• 对父节点进行左旋；
• 把父节点设置为插入节点
• 再来一次右旋

        进行左旋

        进行右旋

• P是PP的右节点
• 根据规则：
  • 插入节点父节点为红色
  • 叔叔节点不存在或为黑节点
  • 父节点是祖父节点右节点
  • 插入节点是父节点的左节点

                加28

                右旋

                左旋

• 根据规则：

• 插入节点父节点为红色
• 叔叔节点不存在或为黑节点
• 父节点是祖父节点右节点
• 插入节点是父节点的右节点

加入一个35；

22左旋

r