我在 Kotlin 中编写了红黑树。 Fun insertFixup 在插入新元素后恢复平衡(z: Node? 是新元素)。树平衡算法取自here (第 2-3 页)。 问题是 Kotlin 不允许我重新分配 z 到 z.parent 和 z。父.父。我希望 z 成为 指针。问题是如何让 Kotlin 明白我想从他那里得到什么?
class Node(key: Int) {...}
class BinarySearchTree {
var root: Node? = null
fun insert(newNode: Node) {...}
fun RotateLeft(x: Node?) {...}
fun RotateRight(x: Node?) {...}
fun insertFixup(z: Node?) {
var y: Node?
while (z?.parent?.color == "RED") {
if (z?.parent == z?.parent?.parent?.left) {
y = z?.parent?.parent?.right
if (y?.color == "RED") {
z?.parent?.color = "BLACK"
y?.color = "BLACK"
z?.parent?.parent?.color = "RED"
z = z?.parent?.parent
}
if (z == z?.parent?.right) {
z = z?.parent
RotateLeft(z)
z?.parent?.color = "BLACK"
z?.parent?.parent?.color = "RED"
RotateRight(z?.parent?.parent)
}
} else {
y = z?.parent?.parent?.left
if (y?.color == "RED") {
z?.parent?.color = "BLACK"
y?.color = "BLACK"
z?.parent?.parent?.color = "RED"
z = z?.parent?.parent
}
if (z != z?.parent?.left) {
z = z?.parent
RotateLeft(z)
z?.parent?.color = "BLACK"
z?.parent?.parent?.color = "RED"
RotateRight(z?.parent?.parent)
}
}
}
root?.color = "BLACK"
}
}
fun main(args: Array<String>) {
val bst = BinarySearchTree()
while (true) {
var newNode = Node(readLine()!!.toInt())
bst.insert(newNode)
bst.insertFixup(newNode)
}
}
UPD:谢谢大家!所有答案都很有帮助,我在您的回复中找到了解决方案。
最佳答案
Kotlin中的函数参数基本上都是只读的val
在函数内部,所以这里的z
会一直引用原来传入的对象。
如果您需要在函数运行时修改它所指向的内容,则必须在函数的开头制作它的本地副本,然后您可以将其设为 var
.
例如,您可以像这样启动您的函数,这样您就可以稍后重新分配这个本地 var
:
fun insertFixup(_z: Node?) {
var z = _z
// ...
z = z.parent
// ...
}
关于pointers - Kotlin函数参数: Val cannot be reassigned,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42540035/