ベストアンサー
グラフとツリーのデータ構造の違い：
グラフ
- グラフには複数のパスが存在する可能性があります。つまり、グラフはノード間に単方向または双方向のパスを持つことができます。
- グラフには、そのようなルートノード。
- グラフにはループや回路を含めることができ、自己ループを含めることもできます。
- グラフにはそのようなものはありません。親子関係。
- グラフは、サイクルやループなどを持つ可能性があるため、ツリーと比較してより複雑です。
- グラフは DFS ：深さ優先検索および BFS ：幅優先検索アルゴリズム。
- グラフは循環または非循環にすることができます。
- グラフには主に、有向グラフと無向グラフの2種類があります。
- グラフアプリlications：マップの色付け、アルゴリズム、グラフの色付け、ジョブのスケジューリングなど。
- グラフでは、いいえ。エッジの数はグラフによって異なります。
- グラフはネットワークモデルです。
ツリー
- ツリーは特殊な形式のグラフです。つまり、最小限に接続されたグラフであり、任意の2つの頂点間に1つのパスしかありません。
- ツリーは、ループ、回路、自己ループがないグラフの特殊なケースです。
- ツリーには、ルートが1つだけありますノードとすべての子には親が1つしかありません。
- ツリーには親子関係があるため、流れは方向性を持って存在できます上から下、またはその逆。
- ツリーは、サイクルがなく、自己ループがなく、接続されたままであるため、グラフよりも複雑ではありません。
- ツリートラバーサルは、トラバーサルの一種の特殊なケースです。グラフの。ツリーは、事前注文、注文、および注文後（ DFS または BFS <の3つすべて/ span>アルゴリズム）
- ツリーはDAGのカテゴリに分類されます：Directed Acyclic Graphsは、サイクルのない一種の有向グラフです。
- ツリーの種類は次のとおりです：バイナリツリー、バイナリ検索ツリー、AVLツリー、ヒープ。
- ツリーアプリケーション：ツリートラバーサルやバイナリ検索のように並べ替えて検索します。
- ツリーには常に n-1 のエッジがあります。
- ツリーは階層モデルです。
回答
したがって、kdツリーは、一見すると、実際よりも理論的であるように見える場合があります。しかし、実際にはそうではありません。
kdツリーにはさまざまな重要なアプリケーションがあり、その中には次のものが含まれます：
1 。最近傍検索
ソーシャル警官。 Social Copは、人々が犯罪を最寄りの警察署にリアルタイムで報告するのに役立ちます。
では、ここで何が問題になっているように思われますか？
はい、あなたはそれを正しく推測しました。何かを報告する前に、犯罪現場に最も近い警察署を探す必要があります。
どうすればよいですか すばやく ？
k-d木は、都市の2次元地図上の点に最も近い隣人を見つけるのに役立つようです。あなたがしなければならないのは、あなたの街のすべての警察署の場所から2次元のkdツリーを構築し、次にkdツリーにクエリを実行して、街の任意の場所に最も近い警察署を見つけることです。
わかりました、彼らができることはわかりました。しかし、どのようにそれを行うのでしょうか？
二分探索木がどのように機能するかをすでに知っている場合、kd木がどのように機能するかを理解すると何も新しいことではありません。 k-dツリーは、バイナリ検索ツリーが実数直線の分割に役立つのと同じようにスペースの分割に役立ちます。 k-dツリーは、空間の領域を再帰的に分割し、ツリーの各レベルにバイナリ空間分割を作成します。
これは、3次元のkdツリーで分割された空間の3次元領域がどのように見えるかです[1]：
3次元のkdツリー。最初の分割（赤）は、ルートセル（白）を2つのサブセルに分割し、各サブセルは次に2つのサブセルに分割（緑）します。最後に、これら4つのそれぞれが2つのサブセルに分割されます（青）。分割がなくなるため、最後の8つはリーフセルと呼ばれます。
そして、ツリーはどのように構築されますか？
まず、k次元空間に一連の点があります。2次元kdツリーの例を見てみましょう：
入力：（2,3）、（5,4）、（9,6）、（4,7）、（8、 1）、（7,2）
出力：2次元kdツリー[2]：
二分探索木の場合、各内部ノードでの実数直線のバイナリパーティションは、 ポイント<で表されます。実数直線上の/ span> 。同様に、2次元kdツリーの場合、各内部ノードでの2次元カルテシアン平面のバイナリパーティションは line 。
つまり、二分探索木の場合、内部ノードによって表される点は、実数直線を分割するために使用される点として機能します。2次元kd木の場合、分割線を選択するにはどうすればよいですか？
基本的に、内部ノードによって表される点を通過する任意の線を選択できます2次元デカルト平面を分割します。
上記のkdツリー出力は、ツリーの各内部ノードで分割線を選択するための簡単な方法を使用して構築されています：-
レベル 0 ：-最初の次元に垂直な分割線を選択します（ X この場合）そして問題のノードによって表されるポイントを通過します。
レベル 1 ：-分割線を選択します第2次元（この場合は Y ）に垂直で、で表される点を通過します。問題のノード。
： ： ：
レベル k-1 ：-<に垂直な分割線を選択しますdiv id = "870698b623">
k番目の次元と表されたポイントを通過する問題のノードによって。レベル k ：-最初の次元に垂直な分割線を選択します（ X この場合）そして問題のノードによって表されるポイントを通過します。
したがって、基本的に、各レベルでX次元とY次元を交互に切り替えます。 kdツリーの各内部ノードで分割線を選択するため。
kdツリーの各ノードの横に表示されるラベル[2]は、そのレベルのノードでの分割線の寸法の選択を表しています。
Let “ここで、2次元kdツリーが2次元平面をどのように分割するかを確認します[3]：
わかりました。検索を実行するにはどうすればよいですか？
「それはあなたに任せますが、あなたに任せます」とは言いません。それを完全に理解するために、他のいくつかのリソースの助けを借りる必要があります。ただし、kdツリーによるこの空間分割は、空間内の特定のポイントに最も近い隣接点を見つけるのに役立つと言えます 必要なすべてのパーティションを探索する必要なしに 、SocialCopのリアルタイムレポートを実行します。
kdツリーの最近傍アルゴリズムを理解するための優れたリソースは次のとおりです： http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
kdツリーの背景のほとんどは最初のアプリケーションの説明ですでに説明されているので、kdツリーの他のアプリケーションのいくつかを簡単に説明します。
2。多次元検索キーを含むデータベースクエリ
（40、50）の年齢層のすべての従業員を求め、月額（15000、20000）の範囲の給与を稼ぐクエリは、年齢がx軸に沿ってプロットされる幾何学的問題に変換できます。給与はy軸に沿ってプロットされます[4]
[4] x軸はの年齢を示します年の従業員。y軸は千ルピーの月給を示します。
（年齢、給与）の複合インデックス上の2次元kdツリーは、上記のクエリで定義された直交領域のスペースに含まれるすべての従業員を効率的に検索するのに役立ちます。
3。多体問題[5]
相互の重力引力の下で動く物体の集まりの動きを効率的にシミュレートするにはどうすればよいですか？
素朴な方法では、重力による引力の下での動きをシミュレートするために、他のすべてのオブジェクトによるオブジェクト間の重力を計算します。さらに、O（n ^ 2）時間かかるすべてのオブジェクトに対してそれを行う必要があります。
ただし、k-dツリーを使用すると、スペースを分割でき、スペースの細分化ごとに、残りのスペースへの全体的な影響を把握できます。以下は、アルゴリズムの擬似コード[6]です。
オブジェクトをツリーに配置します。ツリーの最下層から開始します。ツリー内の深さ d のすべての領域について：子が葉である場合は、相互作用を直接計算します。 多重極展開 “これを親ノードのローカル展開に変換して渡します。レベルd-1に進みます。ツリーの最上部に到達したら、ローカル展開を合計して、ツリーを下に戻ります。
4。減色[7]
とはフルカラー画像を表すために256色を選択するインテリジェントな方法？
素朴な方法は、最も頻繁に使用される色を選択することです。
ただし、より効率的な方法は、 RGB 値を設定し、画像のすべての色を含む空間を分割するために3次元のkdツリーを構築します。リーフノードの数が256に等しくなると、k-dツリーの構築は停止します。次に、256個のパーティションのそれぞれのRGB値の平均を使用して、フルカラー画像の256色パレットを取得できます。
参照： [1]、[2]、[3]： http://en.wikipedia.org/wiki/Kd-tree [4]：最近傍を使用した分類 [5]、[6]、[7] ： kDツリー