用於表示區域 - >州 - >國家關係的高效數據結構

我正在尋找一種有效的方式來表示和檢索地理關係，例如， districts->明─> USA。這應該適應任何層次的層次，例如。地區 - >地區 - >州 - >大區域（東/西/南/北） - >美國。用於表示區域 - >州 - >國家關係的高效數據結構

我的要求是

我大多控制在最低水平運行 - 因此讓所有的人快應該是第一優先。持續時間是首選。
然後，我想要在州級執行彙總eg.combine區數據（因此可以輕鬆獲得所有孩子的節點） - 這是第二個標準。
在一個級別的順序並不重要 - 例如。對於NC，我不介意我是否第一次得到羅利或法耶特維爾。

正如你幾乎已經猜到 - A 樹數據結構適合於邏輯上的問題。但我找不到能有效獲得所有葉子的方法。我可以檢查一個節點是否在O（log n）時間葉，但我已檢查每個節點。

我已經看過B，B +樹，但我不明白的是他們使用某種順序如升序或降序來維護它們的順序。

我的直覺是應該有效的解決方案，因爲 - windows或任何文件系統都這樣做。文件 - >文件夾 - >大文件夾 - > C - >我的電腦。同樣這種計算必須在數據挖掘中說可以用於聚類（我記得讀過這樣的東西）

任何在這方面的線索將不勝感激。

感謝

來源

2009-06-02 satyajit

您能更準確地描述您想要對結構做什麼嗎？你的＃1並不完全清楚;正如Welbog所說，你不能在恆定時間內檢索n個項目。而你的「檢查一個節點是否在O（log n）葉」似乎暗示你正在做一些事情，而不是從葉到根的直接聚合。 – 2009-06-02 14:47:55

如果n個項目已存儲在緩存集合中，那麼可以在恆定時間內檢索n個項目 - 這對於節點的所有子項的常見情況很有意義，例如，請參閱下面的答案。 – mikera 2010-06-15 16:28:41

你說的是（在層次結構的特定級別的給定節點下在這種情況下，一切）檢索n匹配給定條件的唯一項目。除非您已預先計算了所有可能的條件，否則您無法在一段時間內從數據結構中獲取唯一項目。至少你必須遍歷這些n項目。

有很多數據結構和數據結構的組合，您可以使用它們來使不同類型的用戶更有效。你說得對，B和B +樹在這種情況下工作得很好，這就是爲什麼我會建議你爲這個應用程序使用關係數據庫，因爲它們是最好的，最健壯的B樹實現，你可以找到。匹配葉節點和計算總量幾乎是他們的目的。除非你有一些特殊原因不使用RDBMS子系統，否則這可能是你最好的選擇。

來源

2009-06-02 14:10:16 Welbog

創建節點樹，其中每個節點包含：

子節點指向父節點（或者爲null，根節點）
集合（如HashMap中或在Java中的ArrayList）
與節點相關聯的任何數據有效載荷（例如地理座標，以便可以執行距離搜索）

如果你喜歡你可以用字符串的AA HashMap中基於索引擴大此 - > O（1）訪問節點的節點。但是對於這個問題，我不會擔心搜索樹的成本，因爲你最多不會超過5-10級。

來源

2010-06-15 16:20:11 mikera

用於表示區域 - >州 - >國家關係的高效數據結構

回答

相關問題