0

要素のリストを取得し、それらをツリーの葉にある各要素を持つバランスの取れたバイナリ ツリーに変換することに興味があります。さらに、一度にリスト全体ではなく、一度に 1 つの要素のみを参照するアルゴリズムを使用してツリーを構築したいと考えています。最後に、このツリーには順序の制約がありません。つまり、検索ツリーではないため、ノードの順序は任意です。

私の質問は次のとおりです。二分探索木を段階的に構築するためのアルゴリズムはたくさんありますが、順序の制約なしでバランスの取れた二分木を構築するためのアルゴリズムは何ですか? ノード間の順序関係を維持することを心配する必要がないため、より効率的である必要があります。

4

1 に答える 1

1

線形時間で実行できます。2 つの要素ごとに、親が必要です。それらの2つごとに、別のものが必要です。しかし、それ以上のことはできません。

最初に、持っているデータ ポイントごとに N 個のノードを作成します。次に、元に戻るように作業を開始します。2 つのリーフをノードで接続し、次にそれらの親ノードを 2 つ接続し、ノードが 1 つになるまで続けます。

または、下に向かって作業することもできます。任意のレベル N で、2^N 個の子が得られます。 

nodes = [...data...]

root = data.first; <== returns first element without removing it from nodes
while data.size > 1
  a=data.pop_front
  b=data.pop_front

  root = new node(a,b) <== create new node with a and b as children
  data.push_back(root)

while ループを終了すると、ルートにはツリーの最上位が含まれます。

于 2013-06-11T05:45:36.637 に答える