Can rotations in treap violate it's heap-ordering or the binary search tree order?

137 Views Asked by At

I'm not sure if I can violate treap's heap-ordering or it's binary search tree like structure with left and/or right rotation methods.

This is the code for left rotation

typename BinarySearchTree<K, T>::BSTTreeNode* rightSon = (*node).getRightSon();
        if (rightSon != nullptr)
        {
            typename BinarySearchTree<K,T>::BSTTreeNode* leftGreatSon = (*rightSon).getLeftSon();
            (*node).setRightSon(leftGreatSon);
            (*rightSon).setLeftSon(node);
        }

and right rotation

typename BinarySearchTree<K,T>::BSTTreeNode* leftSon = (*node).getleftSon();
        if (leftSon != nullptr)
        {
            typename BinarySearchTree<K,T>::BSTTreeNode* rightGreatSon = (*leftSon).getRightSon();
            (*leftSon).setRightSon(node);
            (*node).setLeftSon(parent);
        }

I'd expect these rotations to not violate the heap-ordering and the binary search tree like structure of the treap.

1

There are 1 best solutions below

0
On BEST ANSWER

Heap-ordering will be destroyed by rotation, since given a root node (X0, Y0), which a child (X1, Y1), after the rotation, (X1, Y1) will be root. Since the Y-value of the root has to be greater than that of the child, we know that Y0 > Y1 initially. After the rotation, Y1 being root requires that Y1 > Y0, which is not true.

Binary search tree properties are not destroyed by rotation, though.