c++ - treap 中的旋转是否会违反它的堆排序或二叉搜索树的顺序？

Question

我不确定我是否可以违反treap 的堆排序，或者它是具有左和/或右旋转方法的二叉搜索树结构。

这是左旋转的代码

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);
        }

和右旋转

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);
        }

我希望这些轮换不会违反堆排序和二叉搜索树的结构。

Answer 1

堆排序将被旋转破坏，因为给定一个根节点（X0，Y0），其中一个子节点（X1，Y1）在旋转之后，（X1，Y1）将成为根节点。由于根的 Y 值必须大于子节点的 Y 值，因此我们知道 Y0 > Y1 最初。旋转后，Y1 为根要求 Y1 > Y0，这是不正确的。

但是，二叉搜索树的属性不会被旋转破坏。