1. 概要

このチュートリアルでは、ツリー構造の実際の例について説明します。

具体的には、ゲーム開発、データベース、機械学習の分野で発生する問題について説明し、ツリー構造がこれらの問題の解決にどのように役立つかを説明します。

2. 序章

ツリーは、広く使用されている抽象データ型であり、リンクされたノードのセットとして表される、ルート値と親ノードを持つ子のサブツリーを持つ階層ツリー構造をシミュレートします。

ツリー構造は、ほぼすべてのコンピュータサイエンスのチュートリアルのかけがえのない部分であり、ツリーを利用するアルゴリズムは、対数計算の複雑さに関連付けられているため、非常に高速で効率的です。

3. ゲーム開発

私たちのほとんどは、誰かが3Dビデオゲームをプレイするか、プレイするのを見たことがあります。 典型的なシナリオでは、プレイヤーが仮想環境をさまよって周囲と対話することでアバターを制御します。 このようなゲームには通常、さまざまなオブジェクトを表す多くの仮想エンティティが含まれています。 ある程度のリアリズムを持たせるために、ユーザーのアバターは、少なくともこれらのエンティティを（通過するのではなく）固体のオブジェクトであるかのように操作する必要があります。

この目的のために、衝突検出が必要です。 エンティティの数が増えると、すべてのオブジェクトとの衝突を素朴にチェックすることが計算上実行不可能になることが簡単にわかります。 実際のところ、オブジェクトとアバターが遠すぎるため、これらのチェックのほとんどは冗長です。

スペース分割ツリーは、特定のセルサイズに達するまで、スペースを再帰的に小さなセルに分割します。リーフノードは仮想環境の領域に対応し、現在その中にあるオブジェクトを含みます。 したがって、衝突のチェックは、アバターが現在いるセルを見つけ、隣接するセル内のオブジェクトとの衝突のみをチェックすることになります。

このプロセスにより、計算数が大幅に削減され、リアルタイムの衝突検出が可能になります。スペース分割ツリーの例には、 quadtrees （2Dスペースの分割用）やoctreesがあります。 （3Dスペースの場合）：

4. データベース

データベースはあらゆるアプリケーションの不可欠な部分です。時間が経つにつれて、アプリケーションはデータを大量に消費するようになり、データを保存するための便利で簡単にアクセスできる場所を持つことが非常に重要になります。

残念ながら、ストレージデバイスは一般に低速であり、従来の磁気ハードドライブの場合のように、それらにアクセスするために機械部品を移動する必要があることがよくあります。 そのため、特定の情報を見つけるためにデータベース内で徹底的な検索を行うのは非常に不便です。 そのため、データエントリが存在する正確なメモリブロックを見つけて、直接アクセスできるようにします。

幸いなことに、データベースにはインデックスと呼ばれるアクセス構造が内部に含まれています。

データベースインデックスは通常、B +ツリーと呼ばれる特別なツリー構造に基づいています。クエリキーが与えられた場合、クエリを満たすデータエントリを含むメモリブロックにアクセスします。 B +ツリーは、可能なキー値を間隔に分割します。ツリーを下に移動すると、間隔はますます小さくなります。

リーフノードには、間隔内のデータエントリを含むメモリブロックへのポインタが含まれています。 前の葉と次の葉へのポインタも、それらの間の簡単なアクセスを保証します。

クエリを満たすデータエントリにアクセスするために、ツリーをトラバースして、間隔にクエリキーが含まれているリーフノードを見つけます。 次に、そのリーフノードのポインタをたどり、ストレージデバイスから適切なメモリブロックを取得します。

もちろん、これはプロセスの過度に単純化されたバージョンです。 データベースインデックスには、対応しなければならない他のニーズがあり、問題の複雑さが増します。 ただし、B +ツリーが基盤を形成し、その上にこのメカニズムが構築されます。

5. 機械学習

これまで、複雑さを軽減し、より高速な操作を可能にするために、便利なメカニズムとしてツリーを使用する問題について説明してきました。 しかし、木自体が目玉となる方法はどうでしょうか。

デシジョンツリーは、シンプルでありながら効果的な機械学習ツールであり、複数の要因を考慮しながら問題の最適なアクションを決定しようとする意思決定分析で一般的に使用されます。

デシジョンツリーには、属性のセットとして表される「状態」が必要であり、「デシジョン」を出力します。 各ノードは、属性の1つに対する値チェックを記述し、可能な値と同じ数の新しいノードに分岐します。

一方、リーフノードは決定に対応します。 特定の問題に適用される一連の属性が与えられた場合、属性値に対応するブランチをたどってツリーをトラバースし、到達したリーフノードによって指定された決定を行います。

6. 結論

この記事では、ツリー構造のいくつかのユースケースシナリオについて説明し、それらの重要性を強調しました。 アプリケーションは上記のものに限定されるものではありませんが、読者がすでにそれらに精通している可能性が高いため、これらの特定のアプリケーションを選択しました。

この記事を通じて、私たちはこれらの構造への関心を刺激し、読者がそれらについてもっと学ぶように動機付けることを望んでいます。