红黑树

1548402057925.png

对平衡树的改进.任意一个节点，他的左右子树的层次最多不超过一倍

应用

在jdk1.8之后为了处理大数据，将Hashtable，TreeSet，TreeMap都从以前的链表结构改成了现在的红黑树结构

插入节点

先按照二叉排序树的方式插入一个节点（红色）

1，插入的是根节点

  解决方式：直接将节点涂黑

2，插入的节点的父节点是黑色

    不违背任何性质，不用调整

3，插入的节点的父节点是红色

case 3.1：父节点是祖父节点的左孩子
    case 3.1.1:祖父节点的另一个子节点是红色
          操作：将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点重新开始循环

1548664718988.png

  case 3.1.2:祖父节点的另一个子节点是黑色
        case 3.1.2.1:当前节点是其父节点的右孩子
              操作：当前节点的父节点作为新的当前节点，以新当前节点为支点左旋

1548664833723.png

      case 3.1.2.2:当前节点是其父节点的左孩子
            操作：父节点变为黑色，祖父节点变红色，再祖父节点为支点进行右旋

1548664893169.png

   case 3.2：父节点是祖父节点的右孩子
           case 3.2.1:祖父节点的另一个子节点是红色
                 操作：将当前节点的父节点和叔叔节点涂黑，祖父节点   涂红，把当前节点指向祖父节点，从新的当前节点重新开始循环                                 
           case 3.2.2:祖父节点的另一个子节点是黑色
                  case 3.2.2.1:当前节点是其父节点的左孩子
                      操作：当前节点的父节点作为新的当前节点，以新当前节点为支点右旋
                  case 3.2.2.2:当前节点是其父节点的右孩子
                      操作：父节点变为黑色，祖父节点变红色，再祖父节点为支点进行左旋

删除节点

先进行二叉排序树的删除操作，然后以替换节点作为当前节点进行后面的平衡操作

1，当前节点是红色  
      操作：直接把当前节点染成黑色，结束
2，当前节点是黑色
    case a:被删除节点是父节点的左孩子
        case 2.1：当前节点是根节点
                操作：根节点置空
        case 2.2：当前节点X的兄弟节点是红色          
                操作：将父节点染成红色，兄弟节点染成黑色，对父节点进行左旋，重新设置X的兄弟节点

1548664986096.png

        case 2.3：当前节点X的兄弟节点是黑色
              case 2.3.1：兄弟节点的两个孩子都是黑色
                    操作：将X的兄弟节点设为红色，设置X的父节点为新的X节点

1548665009284.png

            case 2.3.2：兄弟的右孩子是黑色，左孩子是红色             
                  操作：将X兄弟节点的左孩子设为黑色，将X兄弟节点设为红色，将X的兄弟节点右旋，右旋后，重新设置X的兄弟节点

1548665024574.png

          case 2.3.3：兄弟节点的右孩子是红色
                操作：把兄弟节点染成当前节点父节点颜色，把当前节点父节点染成黑色，兄弟节点右孩子染成黑色，再以当前节点的父节点为支点进行左旋，算法结算 

1548665043170.png

  case b:被删除节点是父节点的右孩子  
        操作：把上面的左换成右即可

应用

HashTable

TreeSet

TressMap

参考项目地址