Rotation in treap while keeping track of parent nodes

Question

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?

score 1 · Accepted Answer · answered Apr 05 '22 at 00:14

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.

Rotation in treap while keeping track of parent nodes

1 Answers1