Блог

Главная - Вопросы по программированию - Могут ли вращения в treap нарушать порядок кучи или порядок двоичного дерева поиска?

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

#c #data-structures #treap

#c #структуры данных #treap

Вопрос:

Я не уверен, могу ли я нарушать порядок кучи 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);
        }

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

Комментарии:

1. просто любопытно; Почему вы делаете (*node).getRightSon() вместо node->getRightSon() ?

2. @Leonid проект предоставлен school, и Intellisense по какой-то причине в нем не работает. Проще ввести (* node).getRightSon(), чем node->getRightSon()

Ответ №1:

Порядок кучи будет уничтожен вращением, поскольку задан корневой узел (X0, Y0), дочерний узел (X1, Y1) которого после вращения (X1, Y1) будет корневым. Поскольку значение Y корня должно быть больше значения дочернего элемента, мы знаем, что изначально Y0 > Y1. После поворота Y1, являющийся root, требует, чтобы Y1 > Y0, что неверно.

Однако свойства двоичного дерева поиска не уничтожаются вращением.