最近読んだいくつかの本で二分木と二分探索について言及されているのを見てきましたが、私はまだコンピュータ サイエンスの研究を始めたばかりなので、アルゴリズムとデータを実際に扱うクラスをまだ受講していません。深刻な方法で構造。
典型的な情報源 (ウィキペディア、Google) を確認しましたが、(特に) 赤黒木の有用性と実装に関するほとんどの説明は、密集していて理解しにくいものでした。必要なバックグラウンドを持っている人にとっては完全に理にかなっていると思いますが、現時点ではほとんど外国語のように読めます.
では、プログラミング中に自分が行っている一般的なタスクのいくつかで、二分木が役立つのはなぜでしょうか? それ以外に、どのツリーを使用することを好みますか (サンプル実装を含めてください)、その理由は何ですか?
赤黒木はバランスの良い木を作るのに適しています。二分探索木の主な問題は、非常に簡単にバランスを崩してしまうことです。最初の数字が 15 だと想像してください。その後の数字はすべて 15 よりも小さくなります。左側が非常に重く、右側には何もない木ができます。
Red Black trees は、挿入または削除するたびにツリーのバランスを強制することで、これを解決します。これは、祖先ノードと子ノードの間の一連のローテーションによって実現されます。このアルゴリズムは、少し長いですが、実際には非常に簡単です。CLRS (Cormen、Lieserson、Rivest、Stein) の教科書「Introduction to Algorithms」を手に取り、RB Trees を読むことをお勧めします。
実装もそれほど短くはないため、ここに含めるのはおそらく最善ではありません。それにもかかわらず、ツリーは、大量のデータにアクセスする必要がある高性能アプリに広く使用されています。これらは、挿入/削除のオーバーヘッドが比較的小さく、ノードを見つける非常に効率的な方法を提供します。繰り返しになりますが、CLRS を調べて、それらがどのように使用されているかを確認することをお勧めします。
BST を明示的に使用することはできませんが、一般的なツリーの使用例の 1 つは、ほぼすべての最新の RDBMS にあります。同様に、ファイル システムはほぼ確実にある種のツリー構造として表され、ファイルも同様にそのようにインデックス付けされます。木は Google を動かします。木は、インターネット上のほぼすべての Web サイトに力を与えています。
ここでは、「では、プログラミング中に自分で行っている一般的なタスクのいくつかで、バイナリ ツリーが役立つ理由は何ですか?」という質問だけを取り上げたいと思います。
これは、多くの人が同意しない大きなトピックです。二分探索木や有向グラフなど、CS の学位で教えられるアルゴリズムは、日常のプログラミングでは使用されないため、無関係であると言う人もいます。他の人は、これらのアルゴリズムとデータ構造がすべてのプログラミングの基礎であり、たとえ自分で書く必要がないとしても、それらを理解することが不可欠であると言って、反対します. これは、優れた面接と採用慣行に関する会話にフィルターをかけます。たとえば、Steve YeggeはGoogle でのインタビューに関する記事で、この質問に取り組んでいます。この議論を思い出してください。経験者は同意しません。
典型的なビジネス プログラミングでは、バイナリ ツリーやツリーを作成する必要はほとんどありません。ただし、ツリーを使用して内部的に動作する多くのクラスを使用します。すべての言語の主要な組織クラスの多くは、ツリーとハッシュを使用してデータを保存およびアクセスします。
ビジネスプログラミングの標準から少し外れている、より高性能な取り組みや状況に関与している場合は、ツリーがすぐに友達になることがわかります。別のポスターが言ったように、ツリーはあらゆる種類のデータベースとインデックスのコア データ構造です。これらは、データ マイニングと視覚化、高度なグラフィックス (2D と 3D)、およびその他の多くの計算問題に役立ちます。
3D グラフィックスでBSP (バイナリ スペース パーティショニング) ツリーの形式でバイナリ ツリーを使用しました。私は現在、Flash/Flex アプリケーションで情報を視覚化するために、大量のジオコーディングされたデータやその他のデータをソートするために、再びツリーを調べています。ハードウェアの限界を押し広げたり、より低いハードウェア仕様で実行したい場合はいつでも、最適なアルゴリズムを理解して選択することが、失敗と成功の違いを生む可能性があります。
BSTが正確に何に適しているかについて言及している回答はありません。
やりたいことが値によるルックアップだけである場合、ハッシュテーブルははるかに高速で、O(1) 挿入とルックアップ (償却された最良のケース) です。
BST は O(log N) ルックアップになります。ここで、N はツリー内のノードの数であり、挿入も O(log N) です。
RB および AVL ツリーは、このプロパティのために言及された別の回答のように重要です。プレーンな BST が順序どおりの値で作成された場合、ツリーは挿入された値の数と同じくらい高くなり、ルックアップのパフォーマンスが低下します。
RB ツリーと AVL ツリーの違いは、挿入または削除後のリバランスに必要なローテーションです。AVL ツリーはリバランスで O(log N) ですが、RB ツリーは O(1) です。この一定の複雑さの利点の例は、永続的なデータ ソースを保持している可能性がある場合です。ロールバックするために変更を追跡する必要がある場合は、AVL ツリーで O(log N) の可能な変更を追跡する必要があります。
ハッシュテーブルよりもツリーのコストを支払うことをいとわないのはなぜですか? 注文！ハッシュ テーブルには順序がありません。一方、BST は構造上、常に自然に順序付けられています。そのため、配列やその他のコンテナーに大量のデータを投げて、後で並べ替えることに気付いた場合は、BST がより良い解決策になる可能性があります。
ツリーの order プロパティは、順番、深さ優先、幅優先、前順、後順など、順序付けられた反復機能を多数提供します。これらの反復アルゴリズムは、調べたい場合にさまざまな状況で役立ちます。
レッド ブラック ツリーは、言語ライブラリ、C++ Set および Map、.NET SortedDictionary、Java TreeSet などのほぼすべての順序付きコンテナーで内部的に使用されます...
そのため、ツリーは非常に便利で、知らないうちに頻繁に使用している可能性があります。興味深いプログラミング演習として強くお勧めしますが、自分で作成する必要はほとんどないでしょう。
Red Black Tree と B-tree は、あらゆる種類の永続ストレージで使用されます。ツリーのバランスが取れているため、幅と深さのトラバーサルのパフォーマンスが軽減されます。
最新のデータベース システムのほぼすべてが、データ ストレージにツリーを使用しています。
私が見た赤黒木についての最良の説明は、Cormen、Leisersen、Rivest の「Introduction to Algorithms」にあるものです。部分的に実装するのに十分理解できました（挿入のみ）。また、さまざまな Web ページにThis Oneなどのかなりの数のアプレットがあり、プロセスをアニメーション化して、ツリー構造を構築するアルゴリズムのグラフィカルな表現を監視およびステップ実行できます。
マイケルが言ったように、BSTは世界を動かします。実装に適したツリーを探している場合は、AVL ツリー(Wikipedia) を参照してください。それらには平衡条件があるため、O(logn) であることが保証されています。この種の検索効率により、あらゆる種類のインデックス作成プロセスに組み込むことが論理的になります。より効率的な唯一のものはハッシュ関数ですが、それらは非常に速く、速く、急いでいます。また、誕生日のパラドックス(鳩の巣問題とも呼ばれます) に遭遇します。
教科書は何を使っていますか？Mark Allen WeissによるData Structures and Analysis in Javaを使用しました。これを入力している間、実際に膝の上で開いています。Red-Black ツリーに関する優れたセクションがあり、説明しているすべてのツリーを実装するために必要なコードも含まれています。
赤黒の木はバランスが取れているので、アイテムを取り出すために深くトラバースする必要はありません。節約された時間により、最悪のケースでは RB ツリーが O(log()n)) になりますが、不運なバイナリ ツリーは偏った構成になり、悪いケースでは O(n) の取得が発生する可能性があります。これは実際に、またはランダムなデータで発生します。したがって、タイム クリティカルなコード (データベースの取得、ネットワーク サーバーなど) が必要な場合は、RB ツリーを使用して、順序付きまたは順序なしのリスト/セットをサポートします。
しかし、RBTree は初心者向けです。AI を実行していて、検索を実行する必要がある場合、状態情報を大量にフォークしていることに気付くでしょう。永続的な赤黒を使用して、O(log(n)) で新しい状態をフォークできます。永続的な赤黒ツリーは、形態学的操作 (挿入/削除) の前後にツリーのコピーを保持しますが、ツリー全体をコピーすることはありません (通常および O(log(n)) 操作)。Java用の永続的な赤黒ツリーをオープンソース化しました
人々がどのツリーを使用するかを尋ねるので、赤黒木は基本的に2-3-4のBツリー（つまり、4次のBツリー）であることを知っておく必要があります。Bツリーは（あなたの質問で尋ねられたように）二分木と同等ではありません。
これは、後でRBTreeに進化した対称バイナリBツリーとして知られる初期の抽象化を説明する優れたリソースです。意味をなす前に、Bツリーをよく理解する必要があります。要約すると、赤黒木上の「赤」リンクは、Bツリーノード（キー範囲内の値）の一部であるノードを表す方法ですが、「黒」リンクは、Bで垂直に接続されているノードです。 -木。
したがって、赤黒木のルールをBツリーの観点から変換すると次のようになります（私は赤黒木ルール=> Bツリーに相当する形式を使用しています）：
1）ノードは赤または黒のいずれかです。=> bツリーのノードは、ノードの一部にすることも、新しいレベルのノードとして使用することもできます。
2）根は黒です。（このルールは分析に影響を与えないため、省略される場合があります）=>ルートノードは、仮想の親ノードの子としての内部ルートノードの一部と考えることができます。
3）すべての葉（NIL）は黒です。（すべての葉は根と同じ色です。）=> RBツリーを表す1つの方法は葉を省略することであるため、これを除外できます。
4）すべての赤いノードの子は両方とも黒です。=>Bツリーの内部ノードの子は常に別のレベルにあります。
5）特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれています。=> Bツリーは、すべてのリーフノードが同じ深さにある必要があるため、バランスが保たれます（したがって、Bツリーノードの高さは、赤黒木のルートからリーフまでの黒リンクの数で表されます。 ）。
また、Robert Sedgewickによるより単純な「非標準」実装がここにあります:(彼はWayneと一緒にAlgorithmsという本の著者です）
赤黒木がどのように見えるかをグラフィカルに確認したい場合は、ここからダウンロードできる赤黒木の実装をコード化しました。
木は速いかもしれません。平衡二分木に 100 万個のノードがある場合、1 つの項目を見つけるのに平均で 20 回の比較が必要です。リンクされたリストに 100 万のノードがある場合、同じアイテムを見つけるのに平均で 50 万回の比較が必要です。
ただし、ツリーが不均衡な場合、リストと同じくらい遅くなる可能性があり、保存により多くのメモリが必要になります。ほとんどのノードに右の子があり、左の子がないツリーを想像してください。これはリストですが、左側のノードが表示された場合に、左側のノードに配置するメモリ領域を保持する必要があります。
とにかく、AVL ツリーは最初のバランスの取れたバイナリ ツリー アルゴリズムであり、それに関するウィキペディアの記事は非常に明確です。赤黒木に関するウィキペディアの記事は、正直なところ泥のように澄んでいます。
B ツリーは、バイナリ ツリーを超えて、各ノードが多くの値を持つことができるツリーです。B-Tree はバイナリ ツリーではなく、たまたまその名前になっているだけです。それらはメモリを効率的に利用するのに非常に役立ちます。ツリーの各ノードは、メモリの 1 ブロックに収まるようにサイズを変更できるため、ディスクにページングされたメモリ内のさまざまなものを (ゆっくりと) 見つけてはいけません。B-Treeの驚異的な例を次に示します。