ツリーのテンプレート クラス (RedBlack または BinarySearch Tree のようなもの) から始まるプライオリティ キューを実装する必要があるため、結果が少し難しくなる演習を解決しようとしています。
次のようなテンプレートを使用する
class Node
int key
Node left
Node right
Node parent
int leftNodes
int rightNodes
最初に、新しい要素を挿入する必要があったとき、ツリーのレベルを完全に埋めようとしました。次に、InOrderTreeTRAversal/Sort アルゴリズムを使用して配列を埋め、その配列から BinarySearch ツリーを生成し、元のルート要素を新しいルート要素に置き換えました。その結果、バランスの取れたツリーになると仮定します。
残念ながら、ツリーはmaxheap プロパティをエミュレートして、挿入/削除ごとにツリーのバランスを維持する必要があるため、このアプローチは不適切に見えます (そして、私のコードはツリー レベルを完全に埋めるのにうまく機能しませんでした)。ヒープ機能を備えたツリーを実装することは可能ですか? つまり、各要素がその子より大きいか等しいツリーであり、挿入後にバランスが保たれ、ルート ノード (より大きなキー要素) が削除されたときに自動バランス機能を備えているということですか?