問題タブ [tree-rotation]

この質問は、 BST 配列表現を完成させるためのソート済みリストに似ていますが、おそらくより具体的に焦点を当てています。この質問は、完全な二分探索ツリーで動的にノードを挿入することを解決するために使用できます。

メモリ内で要素がツリーのルートである連続配列として表される完全なバイナリ ツリーを考えてみましょう。任意のノードに対して、左の子と右の子があります (これらのインデックスが より小さい場合)。a[0..n)a[0]a[i]a[2*i+1]a[2*i+2]n

で使用されるため、C++ プログラマーはこの表現に精通していstd::make_heapます。std::make_heap(a, a+n)ソートされていない配列 (ソートされていない完全なバイナリ ツリーと見なすことができます) を取り、その要素を並べ替えて (ツリーの回転と見なすことができます)、ツリーを完全なバイナリヒープに変換します。ここで、各ノードの値はその子のいずれよりも大きくなります。結果の配列は「最大ヒープ順」であると言います。

一方、各ノードの値が左の子よりも大きく、右の子よりも小さい場合、完全な二分木は完全な二分探索木であると言います。この場合、結果の配列が「レベル順」であるとしましょう。^[1]

特定の要素セットに対して許容される「最大ヒープ順序」は多数ありますが、各要素セットには一意の「レベル順序」が 1 つしかありません。

次のベクトルはレベル順です。

私が探しているのは、次の効率的なアルゴリズムのファミリーです。

1. ソートされていないシーケンスをレベル順に並べ替える
2. ソートされたシーケンスをレベル順に並べ替える
3. レベル順シーケンスをソート順に並べ替える

私が「効率的」と言うとき、深い再帰、動的メモリ割り当て、および一時配列なしで機能するアルゴリズムを意味します。順列が特に迅速に実行できないことは既にわかっています。私はO（n lg n）を望んでいます。

パート 2 とパート 3 では、基本的にマッピングを作成するよう求めていることに注意してくださいOldIndex -> NewIndex。このような関数を作成したら、これらのアルゴリズムのいずれかを使用して順列をインプレースで実行できます。

nonstd::make_searchtree第 1 部では、 との類推によるの実装を求めていstd::make_heapます。nonstd::sort_searchtreeパート 3 では、 の類推によっての実装を求めていstd::sort_heapます。

[1] — 基本的に、この用語「レベル順」は私が作りました。この順序について、より広く認知されている学術用語を知っている場合は、コメントを残してください。