在trap中旋转，同时跟踪父节点

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

这是我的trap的一个示例，显示了正确的堆（顶部的最大值）和BST，但没有正确的父级。

格式为[优先级]<键值>位置父母。

[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

这两个函数都有相同的错误，所以我现在重点关注左旋转。有两个指针未设置：

1. new_parent 以前将 parent 作为其子级，但最后应该将 child 作为其子级，但是您没有更改 new_parent 的任何指针
2. L 以前将 child 作为其父级，但最后应该有 parent< /code> 作为其父级，但您没有更改任何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

我不确定您是否有其他 Tree 属性，例如 root 节点，但树的根可能会在一个旋转。另外，有一点需要注意的是，旋转函数有一个返回值，这有点奇怪。