0

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 の構造のようなバイナリ検索ツリーに違反しないことを期待しています。

4

1 に答える 1