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