在跟踪父节点的同时在 treap 中旋转

Question

我的 treap 保留了堆和 BST 属性，但 treap 中每个节点的父节点并不总是正确的，我认为这是因为我的旋转方式。

这是我的旋转函数：

    def left_rotate(self, child, parent):
        L = child.left_child
        new_parent = parent.parent
        child.left_child = parent
        parent.right_child = L
        parent.parent = child
        child.parent = new_parent
        return child

    def right_rotate(self, child, parent):
        R = child.right_child
        new_parent = parent.parent
        child.right_child = parent
        parent.left_child = R
        parent.parent = child
        child.parent = new_parent
        return child

这是我的 treap 示例，显示了正确的堆（顶部最大）和 BST，但父代不正确。

格式为 [priority] position parent.

[62319] <3 c> root
        [14267] <1 e> left _3_
        [43408] <12 b> right _3_
                [14605] <4 f> left _3_
                        [7853] <6 a> right _4_
                [35669] <17 d> right _12_

如您所见，优先级为 [14605] 的节点的父节点不正确。我的旋转函数有什么问题会导致这种行为？

Answer 1

两个函数都有同样的错误，所以我现在将重点放在left-rotate上。有两个指针未设置：

new_parent 之前 parent 作为 child，但最后应该 child 作为 child，但你没有改变new_parent 的任何指针
L之前的parent是child，但是最后的parent应该是parent，但是你没变L 的任何指针

修正后的函数为：

def left_rotate(self, child, parent):
    L = child.left_child
    new_parent = parent.parent

    if L is not None:
        L.parent = parent

    child.left_child = parent
    parent.right_child = L
    parent.parent = child
    child.parent = new_parent
    if new_parent is not None:
        if new_parent.right_child == parent:
            new_parent.right_child = child
        else:
            new_parent.left_child = child

    return child

def right_rotate(self, child, parent):
    R = child.right_child
    new_parent = parent.parent

    if R is not None:
        R.parent = parent

    child.right_child = parent
    parent.left_child = R
    parent.parent = child
    child.parent = new_parent
    if new_parent is not None:
        if new_parent.right_child == parent:
            new_parent.right_child = child
        else:
            new_parent.left_child = child
    return child

我不确定您是否有其他树属性，例如 root 节点，但树的根可能会在旋转过程中发生变化。另外，在次要说明中，旋转函数具有 return 值有点奇怪。

在跟踪父节点的同时在 treap 中旋转

Rotation in treap while keeping track of parent nodes

python

algorithm

tree

avl-tree

treap