1

バランスの取れた二分木に必要なアイテムのセットがあります。各項目は の形式(data,parent)でdata、有用な情報でありparent、バイナリ ツリー内の親ノードのインデックスです。

ツリー内のノードには、次のように、左から右、行ごとに番号が付けられます。

           1
       ___/ \___
      /         \
     2           3
   _/\_        _/\_
  4    5      6    7

これらの要素は、リンクされたリストに格納されます。ツリーを構築しやすいように、このリストをどのように順序付ければよいでしょうか? 各親ノードは、正確に 2 つの子ノードによって (インデックスによって) 参照されます。これらを親インデックスで並べ替える場合、並べ替えは安定している必要があります。

4

3 に答える 3

0

私はあなたが何を達成しようとしているのか正確には理解していないと思います。ツリーにアイテムを挿入する関数を作成する必要があります。たとえば、赤黒木は、入力データがどのようにソートされていても、挿入に関して同じ複雑さO（log n）を持ちます。使用する必要のある特定の実装、または挿入のために到達する必要のある特定の速度目標はありますか？

PS：私には宿題のように聞こえます:)

于 2012-04-29T20:15:54.073 に答える
0

フィールドに従って昇順で、任意の安定した並べ替えでリストを並べ替えることができます。parent

結果は次のようなリストになります。

[(d_1,nil), (d_2,1), (d_3,1) , (d_4,2), (d_5,2), ...(d_i,x), (d_i+1,x) ]
     ^ 
   the root has no parent...

このリストでは、安定した並べ替えを使用しているため、並べ替えられた(d_i,x), (d_i+1,x)リストの2 つのペアごとd_iに、左の葉になることに注意してください。

これで、幅優先トラバーサルでツリーを作成できます。

宿題なので、自分で全部理解しておいてほしいです。だから私は「答えをフィード」したくありません。特定の質問がある場合は、コメントしてください。関連する部分を編集して詳細を説明します。

ボーナス: この編成の結果は、完全なバイナリ ツリーであるバイナリ ヒープ構造を実装するための非常に一般的な方法ですが、パフォーマンスのために、通常は配列として格納します。これは、このアプローチによって生成される出力と非常によく似ています。

于 2012-04-29T21:08:13.713 に答える
0

配列を使用して、リーフ ノードからその祖先に移動できるバイナリ ツリーが必要なようです。

通常、treap やその他の O(logn) データ構造を使用しない限り、リストを二分木に入れる前に並べ替えると、二分木がアンバランスになります。

(完全な) バイナリ ツリーを配列に格納する通常の方法は、ノード i に 2 つの子 2i と 2i+1 を持たせることです。

この編成 (ソートではなく編成) を考えると、分数を切り捨てる整数演算を使用して配列インデックスを 2 で除算することにより、リーフ ノードから親ノードに移動できます。

バイナリ ツリーが常に完全であるとは限らない場合は、配列の使用を忘れて、代わりにポインター/参照を使用した従来のツリー構造を使用することで、おそらくより適切なサービスが提供されるでしょう。

于 2012-04-29T21:18:26.143 に答える