1

私が見たBSTのほとんどの例は、次の形式です

Class Node {
    Node left;
    Node right;
    Key key;
    Value value;
 }

ただし、BST は、追加の制約を伴う特定の形式のバイナリ ヒープのように見えます。つまり、左の子の値は、右のノードの値より小さくなければならない親の値より小さくなければなりません。

バイナリ ヒープは、配列を使用して簡単に実装できます。この特別な規則が確実に維持されるように、配列を使用して BST を作成してみませんか? そうすることの欠点は何ですか？

4

1 に答える 1

1

答えは簡単です。配列のサイズを動的に変更することはできません。

配列のサイズは、後で変更することはできません。配列を使用する場合は、追加または削除されたものに応じて拡大または縮小する必要があり、それを行うたびに古い配列から新しい配列にコンテンツをコピーする必要があるため、不要なオーバーヘッドが発生します。

参照またはポインターを使用するノードを使用すると、より動的な構造を提供する要素を削除する場合に、新しい要素を挿入または設定するたびに(または同様のものに)、それに応じて (再) 割り当てleftを行うことができます。rightnull

于 2015-01-25T01:26:08.500 に答える