私は計算幾何学についてのすてきな小さな本を買いました。あちこちで読んでいるうちに、この特殊な種類の二分探索木の使用法に出くわすことがよくありました。これらのツリーはバランスが取れており、葉ノードにのみデータを格納する必要がありますが、内部ノードは検索を葉に導くための値のみを格納する必要があります。
次の図は、このツリーの例を示しています (葉は長方形で、内側のノードは円です)。
2 つの質問があります。
内部ノードにデータを保存しない利点は何ですか?
学習の目的で、そのようなツリーを実装したいと思います。そのため、AVL ツリーをベースに使用するのがよいのではないかと思いましたが、それでよいのでしょうか。
どんな種類の役立つリソースも大歓迎です。
内部ノードにデータを保存しない利点は何ですか?
ハフマン コード ツリーやB+ ツリーなど、内部ノードにデータを格納しないように設計されているツリー データ構造がいくつかあります。ハフマン ツリーの場合、2 つのリーフが同じプレフィックスを持たないことが要件です (つまり、ノード 'A' へのパスは 101 で、ノード 'B' へのパスは 10 です)。B+ ツリーの場合、ブロック検索用に最適化されているという事実に由来します (これは、すべての内部ノードに多くの子があり、通常、ツリーの深さがわずか数レベルであることも意味します)。
学習の目的で、そのようなツリーを実装したいと思います。そのため、AVL ツリーをベースに使用するのがよいのではないかと思いましたが、それでよいのでしょうか。
もちろん！AVL ツリーはそれほど複雑ではないため、学習に適しています。
内部ノードの代わりに葉にデータを持つ他の種類のバイナリ ツリーを持つことは一般的ですが、バイナリ SEARCH ツリーではかなり一般的ではありません。
これを行う理由の 1 つは教育的なものです。通常、この方法でバイナリ サーチ ツリーを実装する方が、従来の方法よりも簡単です。なんで？ほぼ完全に削除が原因です。通常、葉の削除は非常に簡単ですが、内部ノードの削除はより困難/面倒です。データが葉だけにある場合は、常に簡単なケースです!
内部ノードのキーがどこから来るのかを考える価値があります。多くの場合、それらは葉にもある (データを含む) キーの複製です。後で、リーフのキーが削除された場合、内部ノードのキーがまだぶら下がっている可能性があります。
内部ノードにデータを保存しない利点は何ですか?
一般に、内部ノードにデータを格納しないことに利点はありません。たとえば、赤黒木はバランスの取れた木であり、そのデータを内部ノードと葉ノードに格納します。
学習の目的で、そのようなツリーを実装したいと思います。そのため、AVL ツリーをベースに使用するのがよいのではないかと思いましたが、それでよいのでしょうか。
私の意見では、そうです。
データをリーフ ノード (B+ ツリーなど) にのみ保持する利点の 1 つは、データのスキャン/読み取りが非常に簡単になることです。リーフ ノードは相互にリンクされています。したがって、特定のリーフ ノード内のデータの「最後」(右または左) にいるときに次の項目を読み取るには、次の (または前の) ノードへのリンク/ポインターを読み取り、次のリーフ ページにジャンプするだけです。 .
データがすべてのノードにある B ツリーでは、ツリーを走査してデータを順番に読み取る必要があります。これは確かに明確に定義されたプロセスですが、間違いなくより複雑であり、通常はより多くの状態情報が必要です。