1

二分木 ( BSTではない) にキーを挿入するにはどうすればよいですか? つまり、バイナリ ツリーには BST のようなノードのプロパティがないため、ツリーのどこにでもキーを挿入できるようです。 それにもかかわらず、キーを任意の場所に配置すると、バイナリ ツリーがそのプロパティを失う「リスト」に退化する可能性があります。 マージ スキームを使用したバイナリ ツリーの作成を見たことがありますが (サンプル アプリケーションは です)、バイナリ ツリーの挿入アプローチに遭遇したことはないようです。 二分木は多元木（2つの子ノード）の具体的な例になるので、この質問は多元木にも及ぶと思いますよね？

O(logN)
Huffman Tree

私はこれで間違っていますか？二分木に新しいキーを追加するための特定のアプローチはありますか、それとも二分木のアプリケーションは非常に特殊なので、マージ操作で十分であり、挿入方法は必要ありませんか? BT の使用用途や概念を完全に見逃してしまったのではないでしょうか?

注:二分木について質問しています。二分探索木 についてではありません。

更新:
挿入がどこにでもある場合、用語の意味は何ですか: Full Binary Tree?
これは、どこに挿入しても実現できないログ プロパティを意味します。「Full BT」も意味のない定義ですか？

4

3 に答える 3

2

二分木は特定の種類の木であり、各ノードが正確に 0、1、または 2 つの子を持つという条件を満たします。この条件を満たす木は、二分木と呼ばれます。

そのため、要素を二分木に挿入する「正しい」方法はありません。前が二分木で、後が二分木である限り、挿入は有効です。

二分木という用語は、何よりも分類のためのものです。純粋な「抽象」形式では、データ構造としてあまり役に立ちません。ただし、あなたが言及したように、ハフマン ツリーのような他のより具体的なタイプのツリーを特徴付ける場合に役立ちます。

于 2012-05-27T15:48:49.043 に答える
0

最も単純なスキームは、おそらく次のように完全なツリーを維持することです。最初に挿入されたノード 1、2 番目の 2、3 番目の 3 などを呼び出します。ノード i を挿入するとき、i が偶数の場合は i/2 のノードの左の子、i が奇数の場合は (i-1)/2 の右の子にします。たとえば、2 番目のノードの右側の子に挿入する 5 番目のノードを作成します。挿入する 6 番目のノードは、3 番目のノードの左側の子になります。ノードを削除する必要がある場合は、最初に番号の大きいノードと交換して、常に最後から削除するようにします。

このツリーは、バイナリ ヒープで一般的であるように、位置 1 から始まる配列にノードを配置するだけで表すことができます。ノード i の子は常に 2i と 2i+1 です。ただし、これらの数がノードの総数より大きくない場合は、ツリーの最下部になります。

于 2012-05-28T09:18:26.500 に答える
0

これがすべての意味です。BST では、要素のプロパティ (より大きい、より小さいなど) によって挿入がガイドされます。一般的な BT では、挿入プロセスを処理する必要があります。

BT を使用して順序付けられていないコレクションを実装するとします。各ノードに、それが運ぶデータ要素に加えて、左側のノードの量と右側の量という 2 つの追加の値をラベル付けするだけです。次に、これら 2 つのガイドに従って挿入し、ほぼ完璧なバランスを実現します。葉の場合、最初は子のないノードを使用し、新しい要素が到着したときに子として挿入できるようにします。

これで、O(log(n)) 時間で挿入でき、特定の順序でリストすることができない、順序付けられていないもののコレクションを実装する完全に自動バランスの BT ができました。これはほんの一例です。

于 2012-05-29T16:44:46.140 に答える