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

因为之前写的有点乱，回头自己想想有点问题，又重新撸了一边 ```go //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 一起每天撸一点