Rotation in treap while keeping track of parent nodes-CodePudding

My treap maintains both the heap and BST properties, but the parent nodes of each node in the treap isn't always correct, and I think it's because of how I'm rotating.

Here are my rotation functions:

    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

Here is an example of my treap showing correct heap (max at top) and BST, but not correct parents.

Format is [priority] <key value> 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_

As you can see the node at priority [14605] has an incorrect parent. What is wrong with my rotate functions to cause such behavior?

CodePudding user response：

Both functions have the same mistake, so I'll focus on left-rotate for now. There are two pointers not being set:

new_parent previously had parent as its child, but at the end should have child as its child, but you haven't changed any of new_parent's pointers
L previously had child as its parent, but at the end should have parent as its parent, but you haven't changed any of L's pointers

The corrected functions are then:

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

I'm not sure if you have other Tree attributes, like a root node, but the root of the tree might change during a rotate. Also, on a minor note, it's a tiny bit odd that the rotate function has a return value.