「こんにちは、アミーゴ！」
「こんにちは、リシ！」
「そこで私の古いメモを見つけて、あなたのために興味深い資料を用意しました。聞いてみたいと思うでしょう。」
「聞いてみましょう。いつも面白いことを見つけて、後でとても役立つことがわかります。」
「わかりました。今日は木について話したいので、グラフから始めます。」
"グラフは、点とそれらを接続する線のシステムです。点はグラフの頂点と呼ばれ、線はグラフのエッジと呼ばれます。例:"
「グラフは、現実世界のさまざまなプロセスやタスクの数学的モデルとして使用すると非常に便利です。グラフ用にさまざまなタスクやアルゴリズムが発明されているため、かなり頻繁に使用されています。」
「たとえば、頂点が都市、エッジが道路であると仮定します。その場合、都市間の最短道路を検索することは、次のようになります。«与えられたグラフで、2 つの頂点間の最短経路を見つける»。」
「しかし、A から B へのパスは、B から A へのパスと常に同じとは限りません。そのため、場合によっては 2 つの異なる線を使用することが好ましい場合があります。これを行うには、線 (グラフの端) が矢印に置き換えられます。言い換えれば、グラフには 2 つの矢印、つまり A から B への矢印と、B から A への矢印を含めることができます。」
「グラフに矢印が使用されている場合、それは有向グラフと呼ばれます。グラフに線だけが含まれている場合、それは無向グラフと呼ばれます。」
「各頂点は独自の数のエッジを持つことができます。頂点にエッジをまったく持たないこともできます。逆に、頂点はエッジによって他のすべての頂点に接続できます。グラフ内の頂点の各ペアがエッジによって接続されている場合 、それは完全なグラフと呼ばれます。」
「エッジを使用してグラフ内のすべての頂点に到達できる場合、それは接続されたグラフと呼ばれます。3 つの別々の頂点があり、エッジがないグラフもグラフですが、私たちはそれを非接続グラフと呼びます。」
「N 個の頂点から接続されたグラフを形成するには、少なくとも N-1 個のエッジが必要です。このタイプのグラフはツリーと呼ばれます。」
「さらに、通常、1 つの頂点が木のルートとして選択され、残りは枝であると宣言されます。独自の枝を持たない木の枝は葉と呼ばれます。例:」
「ツリーの各要素に 2 つの子がある場合、それは 2 分木と呼ばれます。言い換えると、0 または 2 つの分岐が存在する可能性があります。右上に2 分木が表示されます。」
「各枝に 2 つの子があり、すべての葉 (子のない頂点) が同じ行にある場合、ツリーは完全な二分木と呼ばれます。」
"例えば："
「なぜこれらの木が必要なのでしょうか？」
「ああ、ツリーはさまざまな場所で使用されます。一般に、バイナリ ツリーはソートされた構造化データです。」
"あれは何でしょう？"
「はい、とても簡単です。各頂点に特定の値を格納します。そして、各要素はルールに従います。右側の子に格納される値は頂点に格納される値より大きくなければならず、左側の子に格納される値は次のとおりです。」頂点に格納されている値よりも小さい必要があります。 この順序により、必要なツリーの要素をすばやく見つけることができます。」
「それが何を意味するのか、説明してもらえますか？」
「ツリー要素は通常、加算によってソートされます。要素が 13、5、4、16、8、11、10 の 7 つあるとします。」
「ツリーに要素を追加する方法は次のとおりです。」
「この木で数字の 7 を探す場合、検索は次のようになります。」
「0) ルートから開始します。」
「1a) 7 は 13 に等しいですか? いいえ」
「1b) 7 は 13 より大きいですか? いいえ、それでは左側のサブツリーに移動します。」
「2a) 7 は 5 に等しいですか? いいえ。」
「2b) 7 は 5 より大きいですか? はい、それでは右のサブツリーに移動します。」
「3a) 7 は 8 に等しいですか? いいえ」
「3b) 7 は 8 より大きいですか? いいえ、それでは左側のサブツリーに移動します。」
「4a) 左側のサブツリーはありません。これは、数字の 7 がツリーにないことを意味します。」
「ああ。言い換えれば、ルートから目的の番号が存在するであろう位置までのパス上の頂点をチェックするだけで済みます。ええ、本当に速いです。」
「さらに、ツリーのバランスが取れていれば、100 万個の要素を検索するのに約 20 個の頂点を通過するだけで済みます。」
「私もその通りです。それはそれほど多くはありません。」
「バランスのとれた木とはどういう意味ですか？」
「歪んでいない木、つまり長い枝がない木。たとえば、木を作成するときに要素がすでにソートされていた場合、1 本の枝からなる非常に長い木が作成されるでしょう。」
「うーん、その通りです。それで、どうしましょうか？」
「おそらくすでにご想像のとおり、最も効率的なツリーにはほぼ同じ長さの枝があります。その後、各比較で残りのサブツリーの最大部分が破棄されます。」
「では、ツリーを再構築する必要があるのでしょうか？」
「そうです。完全な二分木にできるだけ近づけるためには、«バランス» が必要です。」
「この問題を解決するために、自己バランス ツリーが発明されました。 要素を追加した後にツリーが歪んだ場合は、要素の順序を少し変更してすべてを正常にします。 バランスの例は次のとおりです。」
「これらの木のいくつかは赤黒木として知られています。」
「なぜ赤黒と呼ばれるのですか？」
「彼らの発明者は 2 色を使用してすべての頂点を描画しました。1 つの色は赤で、もう 1 つは黒でした。異なる頂点は異なるルールに従います。これがバランス調整手順の全体的な基礎を形成します。」
"例えば："
「それで、これらのルールは何ですか？」
「1) 赤い頂点を赤い頂点の子にすることはできません。」
「2) すべての葉の黒の深さは同じです (黒の深さは、ルートからのパス上の黒い頂点の数を指します)。」
「3) 木の根元は黒いです。」
「これがどのように機能するかについては説明しません。おそらくあなたの頭はすでに爆発しているでしょう。」
「はい。プロセッサーから少し煙が出ています。」
「ここにリンクがあります。必要に応じて、ここで詳細を読むことができます。」
「それでは、休みましょう。」
GO TO FULL VERSION