go - 修复红黑树删除修复中的无限循环
问题描述
我正在尝试实现一棵红黑树。我有插入工作,并且在过去的几天里一直试图让删除工作。我为糟糕的变量名称道歉;我将它们更改为通用的“x、y、w、z”名称,以适当地将我的代码与 CLRS 伪代码进行比较。到目前为止,这是我的代码:
// Delete takes a key, removes the node from the tree, and decrements the size of the tree.
// The function returns the key of the deleted node and an error, if there was one.
func (tree *RBT) Delete(key interface{}) (interface{}, error) {
z, err := tree.findNode(key)
// node with key does not exist
if err != nil {
return nil, err
}
nodeToDeleteKey := z.key()
y := z
originalColor := y.getColor()
var x *Node
if z.leftChild() == nil {
x = z.rightChild()
tree.replaceSubTree(z, z.rightChild())
} else if z.rightChild() == nil {
x = z.leftChild()
tree.replaceSubTree(z, z.leftChild())
} else {
y = z.rightChild().subtreeMin()
originalColor = y.getColor()
x = y.rightChild()
if y.getParent() == z {
x.setParent(y)
} else {
tree.replaceSubTree(y, y.rightChild())
y.setRightChild(z.rightChild())
y.rightChild().setParent(y)
}
tree.replaceSubTree(z, y)
y.setLeftChild(z.leftChild())
y.leftChild().setParent(y)
y.setColor(z.getColor())
}
if originalColor == BLACK {
tree.deleteFixup(x)
}
tree.setSize(tree.Size() - 1)
return nodeToDeleteKey, nil
}
// replaceSubTree replaces one subtree as a child of its parent with
// another subtree. When replaceSubTree replaces the subtree rooted at node u with
// the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s
// parent ends up having as its appropriate child.
func (tree *RBT) replaceSubTree(toDelete *Node, replacement *Node) {
switch {
case toDelete == tree.Root():
tree.setRoot(replacement)
case toDelete == toDelete.getParent().leftChild(): // node to delete is left child
toDelete.getParent().setLeftChild(replacement)
default: // node to delete is right child
toDelete.getParent().setRightChild(replacement)
}
replacement.setParent(toDelete.getParent())
}
// deleteFixup maintains the invariants of the red-black tree after deletion.
func (tree *RBT) deleteFixup(x *Node) {
for x != tree.Root() && x.getColor() == BLACK {
switch {
case x == x.getParent().leftChild():
w := x.getParent().rightChild()
if w.getColor() == RED {
w.recolor()
x.getParent().setColor(RED)
tree.leftRotate(x.getParent())
w = x.getParent().rightChild()
}
if w.leftChild().getColor() == BLACK && w.rightChild().getColor() == BLACK {
w.setColor(RED)
x = x.getParent()
} else {
if w.rightChild().getColor() == BLACK {
w.leftChild().setColor(BLACK)
w.setColor(RED)
tree.rightRotate(w)
w = x.getParent().rightChild()
}
w.setColor(x.getParent().getColor())
x.getParent().setColor(BLACK)
w.rightChild().setColor(BLACK)
tree.leftRotate(x.getParent())
x = tree.Root()
}
default:
w := x.getParent().leftChild()
if w.getColor() == RED {
w.recolor()
x.getParent().setColor(RED)
tree.rightRotate(x.getParent())
w = x.getParent().leftChild()
}
if w.rightChild().getColor() == BLACK && w.leftChild().getColor() == BLACK {
w.setColor(RED)
x = x.getParent()
} else {
if w.leftChild().getColor() == BLACK {
w.rightChild().setColor(BLACK)
w.setColor(RED)
tree.leftRotate(w)
w = x.getParent().leftChild()
}
w.setColor(x.getParent().getColor())
x.getParent().setColor(BLACK)
w.leftChild().setColor(BLACK)
tree.rightRotate(x.getParent())
x = tree.Root()
}
}
}
x.setColor(BLACK)
}
我遇到了一个问题,我在 deleteFixup() 中遇到了无限循环。我附上了一个调试屏幕截图,它显示了 deleteFixup 中的当前变量值。
当我将一个 nil 节点 (x) 传递给 deleteFixup() 时,就会出现问题......我相信它是在 Delete() 中的这个 if/else 条件下,其中 x 被分配给 nil:
if z.leftChild() == nil {
x = z.rightChild()
tree.replaceSubTree(z, z.rightChild())
} else if z.rightChild() == nil {
x = z.leftChild()
tree.replaceSubTree(z, z.leftChild())
}
if / else if 检查要删除的 (z) 左右子节点的节点以及它们是否为空。但有时,要删除的 (z) 左右子节点都为空,并且 x 无论如何都会设置为空值。因此,当我将 x 传递给 deleteFixup() 时,循环永远不会中断,我会陷入以下逻辑:
if w.leftChild().getColor() == BLACK && w.rightChild().getColor() == BLACK {
w.setColor(RED)
x = x.getParent()
}
谁能帮我弄清楚我的代码哪里出错了?谢谢!
解决方案
但有时,要删除的(z's)左右子节点都为空
你会期望的。如果要删除的节点是叶节点并且它是黑色的,则它不会有任何子节点。同样在这种情况下,虽然 w 存在(兄弟姐妹),但兄弟姐妹的孩子可能不存在。
推荐阅读
- angular - 删除 FormControl 上的所有验证
- matlab - 根据下标获取行平均值的快速方法
- dynamic - 使用 spring-cloud-config 时如何在没有任何配置文件的情况下动态加载配置?
- javascript - 实例变量与模块范围变量
- java - Java 8 过滤器映射
> - java - 何在 src/main/resources 中建立 Lucene 索引?
- android - 发送带有附件错误的电子邮件 - 无法附加文件
- c++ - 从标头开始读取串行数据
- android - RX Java & Retrofit 发生多个请求时如何等待服务器响应?
- javascript - for (... in ...) 在多次运行时会得到相同的随机结果吗?