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

Question

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

这是左旋的代码

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，这是不正确的。

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

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

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

c++

treap

data-structures