从零开始学golang-RedBlackTree-Delete-fix2

因为之前写的有点乱，回头自己想想有点问题，又重新撸了一边

//n = delete node n=black
//根据红黑树 特性 推论出 如下结构
//   n=b
//nil   nil
//在这种情况下，删除n 将使得 整个tree 不平衡 少了一个黑节点嘛
//所以思想是 从隔壁挪一个黑色过来 或者 重新染色
func (tree *Tree) fix2(n *node) {

    red := false
    black := true

    //          p
    //    n=b       s
    // nil  nil  sl    sr
    //case1 如果到了根节点 设置为黑色
    if n.p == nil {
        n.c = black
        return
    }

    //case2
    //          b
    //     n         r
    // nil  nil  b       b
    //        nil nil nil nil
    //我们希望兄弟节点变成黑色
    if n.br().c == red && n.p.c == black {
        n.p.c = red
        n.br().c = black
        if n == n.p.l {
            tree.rotateL(n.br())
        } else {
            tree.rotateR(n.br())
        }
        //            b=s
        //        r=p         b=sr
        //   b=n     b=sl   nil nil
        //nil nil nil nil
        //这种情况下删除 n 并不能保证平衡 所以要继续执行case 4 case5 case 6
    }

    //case3
    //          b
    //     b         b
    // nil  nil  nil   nil
    // 因为是全黑情况 只能将 修复节点上移，上移后 支路需要增加 一个红色节点
    if n.p.c == black && n.br().c == black && n.l == nil && n.r == nil {
        n.br().c = red //增加红色节点 （将黑色节点涂红）
        tree.fix2(n.p) //上移修复节点
        //ok
    }

    //case4
    //          r
    //     b         b
    // nil  nil  nil   nil
    // 减少右侧支路黑色节点，增加父节点为黑色
    if n.p.c == red && n.br().c == black && n.br().r == nil && n.br().l == nil {
        n.p.c = black
        n.br().c = red
        return
    }

    //case 5 转换成case6
    if n.br().c == black {
        //    p
        // n     s
        //     sl=r sr=b
        if n.br().l != nil && n.br().r == nil && n == n.p.l {
            n.br().c = red
            n.br().l.c = black
            tree.rotateR(n.br().l)
        }
        //镜像
        if n.br().r != nil && n.br().l == nil && n == n.p.r {
            n.br().c = red
            n.br().r.c = black
            tree.rotateL(n.br().r)
        }
    }

    //case 6
    //这种情况 你可以发现 可以忽略 SL颜色
    //      p
    //   n     s=b
    //           sr=r
    if n.br().c == black && b.br().r != nil && n == n.p.l {
        n.br().c = n.p.c     //保证颜色不变
        tree.rotateL(n.br()) //将兄弟节点成为父节点的父节点 ，使得兄弟路劲减少了一个黑色
        n.p.c = black        //增加 n 路径上 黑色节点
        n.getGp().r = black  //增加兄弟路径 黑色
        return
    }

    //case 6 镜像
    //      p
    //   s     n
    // sl=r
    if n.br().c == black && b.br().l != nil && n == n.p.r {
        n.br().c = n.p.c     //保证颜色不变
        tree.rotateR(n.br()) //将兄弟节点成为父节点的父节点 ，使得兄弟路劲减少了一个黑色
        n.p.c = black        //增加 n 路径上 黑色节点
        n.getGp().l = black  //增加兄弟路径 黑色
        return
    }
}

完整代码自己拉兄弟们

github:https://github.com/godla/golang-sort-data-structures-study

一起每天撸一点