Могут ли повороты в трепе нарушить порядок кучи или порядок бинарного дерева поиска?

Question

Я не уверен, смогу ли я нарушить упорядочение кучи трепа или его двоичное дерево поиска, подобное структуре с левым и / или правым методами вращения.

Это код для левого поворота

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-значение корня должно быть больше, чем у дочернего, мы знаем, что Y0> Y1 изначально. После поворота Y1 как корень требует Y1> Y0, что неверно.

Свойства бинарного дерева поиска не разрушаются при вращении.