红黑树算法

重磅干货，第一时间送达

本文转自：机器学习算法工程师

对于第五种情况：我们如果按照三四两种情况的修复方式是无法满足性质的，我们就考虑旋转后将新的根节点染红，未插入之前的父节点的兄弟节点染红，新根节点的孩子节点染黑。这样出现的问题是新根节点的父节点可能是红的。此时，我们只能向着根的方向逐步过滤这种情况，不再有连续的两个红色节点或遇到根节点为止（把根重染成黑色）。这种策略自底向上，逐步递归完成，见下面的“图4”。

       我们还有一种策略是自顶向下，如果遇到一个黑色节点有两个红色节点，我们将进行颜色翻转（如果节点X有两个红色孩子，我们将X染成红色，将它的两个孩子染成黑色），如果X的父节点也是红色的呢？我们这又归于3、4两种情况。X的父节点的兄弟节点会不会是红色的呢？答案是不会，应为我们自顶向下已经排除了这种情况。此时我们可以排除情况5，将所有情况都转换为情况一到四的处理，除了特殊情况，就剩下情况三和情况四了。

下边是Java代码具体实现：

public void insert(E item){
    current = parent = grand = header;
    nullNode.element = item;
    //当未找到正确插入位置时，一直向下查找,
    //并对树中一个黑节点有两个红节点的情况进行调整  
    while(compare(item,current)!=0){
        great = grand;
        grand = parent;
        parent = current;
        current = compare(item,current)<0?current.left:current.right;
        if(current.left.color==RED&t.right.color==RED)
        handleReorient(item);
    }

    if(current!=nullNode){
        System.out.println("该项已存在");
        return;
    }
    //创建节点并插入修复  
    current = new RedBlackNode<E>(item, nullNode, nullNode);
    if(compare(item,parent)<0){
        parent.left = current;
    }
    else{
        parent.right = current;
    }
    current.parent = parent;
    handleReorient(item);
    nullNode.element = null;
}

//对要插入的节点的链进行调整修复  
private void handleReorient(E item){
    current.color = RED;
    current.left.color = BLACK;
    current.right.color = BLACK;
    if(parent.color == RED){
        grand.color = RED;//先把要旋转的树的根节点染红  
        // 如果不是外节点，则需要旋转两次，
        // 第一次旋转以parent为根，这里传过去的参数树根的父节点  
        if((compare(item,parent)<0)!=(compare(item,grand)<0))
        parent = rotate(item,grand);
        current = rotate(item,great);
        current.color = BLACK;//将新的根节点染黑  
    }
    header.right.color = BLACK;//将整棵树的根节点染黑  
}

/**
 * 明确旋转树在根的左边还是右边后，
 * 我们将旋转树父节点指向根，如果
 * 最终项在左边就右旋，在右边就左旋 
 * @param item 最终项  
 * @param parent 旋转树的根的父节点  
 * @return 旋转树的根节点
 */
private RedBlackNode<E> rotate(E item,RedBlackNode<E> parent){
    if(compare(item,parent)<0){
        parent.left = compare(item,parent.left)<0?
                rotateWithLeftChild(parent.left):rotateWithRightChild(parent.left);
        parent.left.parent = parent;
        return parent.left;
    }
    else{
        parent.right = compare(item,parent.right)<0?
                rotateWithLeftChild(parent.right):
                rotateWithRightChild(parent.right);
        parent.right.parent = parent;
        return parent.right;
    }
}
//以左孩子为支点旋转，即我们所说的右旋（形象理解
//为以支点为中心向右旋转），t1为旋转树的根.返回新根  
private RedBlackNode<E> rotateWithLeftChild(RedBlackNode t1){

    RedBlackNode<E> t2 = t1.left;//得到左孩子  
    t1.left = t2.right;//将左孩子的右子树作为原根的左子树  
    t2.right = t1;//此时t2作为新根  
    t1.parent = t2;
    t2.left.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}
//以右孩子为支点旋转，即左旋  
private RedBlackNode<E> rotateWithRightChild(RedBlackNode t1){
    RedBlackNode<E> t2 = t1.right;
    t1.right = t2.left;
    t2.left = t1;
    t1.parent = t2;
    t2.right.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}

/**
 * 1.没有孩子节点：直接删掉该节点 
 * 2.只有一个孩子节点：将要删除节点的
      父节点直接与该孩子节点相链 
 * 3.有两个孩子节点：将中序遍历的后继，即待删除节点的右
     子树中的最小节点赋给待删除节点，然后将该后继删掉。
 * @param e 要删除的元素 
 * @param t 删除元素的树的根节点 
 * @return  被删除的节点
 */
private RedBlackNode<E> remove(E e,RedBlackNode<E> t){
    if(t==nullNode)
        return null;
    //找到要删除的节点  
    while(compare(e,t)!=0){
        if(compare(e,t)<0&&t.left!=nullNode)
            t = t.left;
        else if(compare(e,t)>0&&t.right!=nullNode)
            t = t.right;
        else
            return null;
    }
    RedBlackNode<E> x;//当前节点  
    RedBlackNode<E> y;//要删除的节点  
    //如果待删除节点只有一个孩子或没有孩子，则实际删除的节点
      //就是所指节点，如果有两个孩子则实际删除节点是右子树的最小项  
    //先确定删除节点  
    if(t.left==nullNode||t.right==nullNode)
        y = t;
    else
        y = findMin(t.right);
     //再确定当前节点，如果实际删除节点的左节点不为nullNode，
      //则当前节点为左节点，如果删除节点只有右节点或没有孩子  
    //我们都将右孩子赋给他，因为没有孩子时右节点为nullNode  
    if(y.left!=nullNode)
        x = y.left;
    else
        x = y.right;
    //当前节点的父亲指向删除节点的父亲  
    x.parent = y.parent;
    //我们根据删除节点在其父节点的子树方向，将父节点直接链接到当前节点  
   //需要注意的是我们引用的伪根节点就是为了减少对特殊情况的讨论，
    //不然有这行代码if(y.parent==header)header.right = x;  
    if(y==y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;
    //如果实际删除的节点不是我们找到的具有该键的节点，它属于有两个
     //孩子的情况，我们将实际删除的节点的值赋给它  
    if(y!=t)
        t.element = y.element;
    if(y.color==BLACK)
        removeFixUp(x);
    return y;
}

/**
 * 删除修复方法 
 * @param x 当前节点 
 */
private void removeFixUp(RedBlackNode<E> x){
    RedBlackNode<E> w;
    while(x!=header.right&&x.color==BLACK){
            //当前节点是父节点的左节点  
    if(x==x.parent.left){
          w = x.parent.right;
          //case1，如上详细分析，如果x的兄弟节点为红色，
          //调整后是兄弟节点为黑后再往下走  
       if(w.color==RED){
          x.parent.color = RED;
          w.color = BLACK;
          rightRotate(x.parent,x.parent.parent);
          w = x.parent.right;
       }
          //case2，新的x如果为红色，循环终止，否则继续循环  
    if(w.left.color==BLACK&&w.right.color==BLACK){
           w.color = RED;
           x = x.parent;
       }else {
          //case3,兄弟节点的右孩子是黑色的，
          //左孩子时红色的，调整后进入case4  
       if(w.right.color==BLACK){
           w.left.color = BLACK;
           w.color = RED;
           rightRotate(w, w.parent);
           w = x.parent.right;
       }
          //case4，调整完成，满足红黑性质  
           w.color = x.parent.color;
           x.parent.color = BLACK;
           w.right.color = BLACK;
      leftRotate(x.parent, x.parent.parent);
           x = header.right;
        }
        }else{
        //对称  
        }
        x.color = BLACK;
    }
}