[解決済み] 二分木の応用例にはどのようなものがありますか？

質問

二分木の具体的な用途が気になるのですが。 具体的な例を教えてください。

どのように解くのですか？

の性能について喧々諤々すること。 バイナリーツリー データ構造ではなく、データ構造のファミリーであり、すべて異なるパフォーマンス特性を持ちます。 確かに アンバランスバイナリーツリー よりもはるかに悪いパフォーマンスを発揮します。 セルフバランシングバイナリツリー を検索するために、多くのバイナリツリーが存在します。 (バイナリートライなど) に対して "バランシング"。 は意味を持ちません。

二分木の応用例

• バイナリサーチツリー - で使用されています。 多数 のように、常にデータが入ったり出たりするような検索アプリケーションの場合。 map と set オブジェクトを使用します。
• 二値空間パーティション - ほぼすべての3Dビデオゲームで、レンダリングが必要なオブジェクトを決定するために使用されます。
• バイナリー・トライ - ほぼすべての広帯域ルーターで、ルーターテーブルの保存に使用されています。
• ハッシュツリー - ハッシュを検証する必要があるが、ファイル全体を利用できないトレントや特殊な画像署名に使用されます。 また、Bitcoinなどのブロックチェーンにも使用される。
• ヒープ - 効率的なプライオリティ・キューの実装に使用され、多くのOSのプロセス・スケジューリング、ルータのQoS、A*に使用されている。 (ロボットやゲームなどのAIに使われる経路探索アルゴリズム）。 . また、ヒープソートにも使用されています。
• ハフマン符号化木 ( チップユニ ) - .jpegや.mp3ファイルフォーマットで使用される圧縮アルゴリズムで使用されます。
• GGMツリー - 暗号化アプリケーションで、擬似乱数のツリーを生成するために使用されます。
• 構文ツリー - コンパイラや（暗黙のうちに）計算機が式を解析するために構築するもの。
• ツリープ - ワイヤレスネットワークやメモリ割り当てに使用されるランダム化されたデータ構造。
• T-ツリー - ほとんどのデータベースでは、データをドライブに保存するために何らかの形のB-treeを使用しているが、すべての（ほとんどの）データをメモリに保存するデータベースでは、しばしばT-treeを使用して保存する。

検索にn進木よりも2進木がよく使われるのは、n進木はより複雑ですが、通常、実際の速度上の利点はないからです。

を持つ（バランスの取れた）2分木において m ノードは、あるレベルから次のレベルに移動するために1つの比較が必要で、そこには log_2(m) レベル、合計で log_2(m) を比較することができます。

これに対して、n進の木では log_2(n) 比較対象 (バイナリサーチを使用して) で次のレベルに移ります。 があるため log_n(m) が必要です。 log_2(n)*log_n(m) = log_2(m) の比較の合計です。 つまり、n-ary木はより複雑ですが、必要な比較の総量という点では何のメリットもありません。

(ただし、ニッチな状況ではN-ary木はまだ有効です。 すぐに思いつくのは次のような例である。 四分木 などの空間分割木では、1レベルあたり2つのノードだけで空間を分割すると、ロジックが不必要に複雑になります。 B-ツリー 多くのデータベースで使用され、各レベルで行われる比較の数ではなく、ハードドライブから一度にロードできるノードの数が制限要因となっています)