0

地理的な関係を表現および取得するための効率的な方法を探しています。地区->州->米国。これは、あらゆるレベルの階層に対応する必要があります。地区->地域->州->大きな地域（東/西/南/北）->米国。

私の要件は

  1. 私は主に最低レベルで運用しているので、すべてを高速化することが最優先事項です。一定の時間が望ましい。
  2. 次に、州レベルで地区データを結合するなどの集計を簡単に実行したいと思います（したがって、ノードのすべての子を取得します）。これは2番目の基準です。
  3. レベルでの順序は重要ではありません-例えば。ノースカロライナ州の場合、最初にローリーとフェイエットビルのどちらを取得してもかまいません。

ご想像のとおり、ツリーデータ構造は論理的に問題に役立ちます。しかし、私はすべての葉を効率的に得る方法を見つけることができませんでした。O（log n）時間でノードがリーフであるかどうかを確認できますが、各ノードでそのことを確認しています。

私はB、B +の木を見てきましたが、私が理解していなかったのは、それらが昇順や降順などの順序を使用して順序を維持していることです。

私の直感では、これには効率的な解決策があるはずです。なぜなら、Windowsやその他のファイルシステムがこれを行うからです。[ファイル]->[フォルダ]->[大きなフォルダ]->[C]->[マイコンピュータ]。また、この種の計算は、データマイニングで実行する必要があります。たとえば、クラスタリングの場合です（この種の何かを読んだことを覚えています）

この方向へのリードをいただければ幸いです。

ありがとう

4

2 に答える 2

1

特定の基準に一致する一意のアイテムを取得することについて話しているn(この場合、特定のノードの下の階層内の特定のレベルにあるすべてのもの)。n考えられるすべての基準を事前に計算していない限り、一定時間内にデータ構造から一意のアイテムを取得することはできません。少なくとも、これらのn項目を繰り返し処理する必要があります。

さまざまなタイプの使用をより効率的にするために使用できる、多くのデータ構造およびデータ構造の組み合わせがあります。B ツリーと B+ ツリーがこの状況でうまく機能することは間違いありません。そのため、このアプリケーションにリレーショナル データベースを使用することをお勧めします。リレーショナル データベースは、可能な限り最良かつ最も堅牢な B ツリーの実装だからです。見つけるには。葉ノードのマッチングと集計の計算は、まさにその目的です。RDBMS サブシステムを使用しない特別な理由がない限り、おそらくこれが最善の策です。

于 2009-06-02T14:10:16.750 に答える
0

各ノードが含まれるノードのツリーを作成します。

  • 親ノードへのポインター (またはルート ノードの場合は null)
  • 子ノードのコレクション (Java の HashMap または ArrayList など)
  • ノードに関連付けられたすべてのデータ ペイロード (たとえば、距離検索を行うための地理座標)

必要に応じて、ノードへの O(1) アクセス用の String -> Node の HashMap ベースのインデックスでこれを拡張できます。しかし、この問題については、最大 5 ～ 10 レベルを超える可能性は低いため、ツリー検索のコストについては心配しません。

于 2010-06-15T16:20:11.877 に答える