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.
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.