AVL樹的四叉樹相當於

Question

我正在尋找一種自平衡的四叉樹/八叉樹/ 2^n樹，因爲它接受新的觀察結果，而沒有其他所有點的知識，喵，它不能依賴於我寫的中位數在'流'的上下文中。 AVL樹平衡，因爲它通過pivoting，有更高維數據的另一個類似的數據結構？

Answer 1

AVL樹只返回一個結果，找到的元素。 但特別是基於ebucket的四叉樹返回查詢位置附近的對象列表。調用程序最後必須檢查結果中的所有對象，以完成填充應用程序任務的那些對象。

從這個角度來看，平衡沒有多大意義。更密集的地區（例如城市）具有更詳細的結構，因此具有更深的四叉樹。 這並不壞。我沒有看到任何四平衡的需要。

對於所有四叉樹類型（點，線，對象四叉樹），當四叉樹節點被拆分時，它總是分裂成4個相等大小的子矩形或二次子節點。這些類型被稱爲受限四叉樹。我在平衡四叉樹中找到的文獻中只有一個暗示（M.Bern，D-Eppstein和J.Gilbert：可能是好的網格生成，在Hanan Samet中引用：多維空間數據結構的基礎）。如果你有學術興趣，你可以閱讀論文，否則我懷疑它對你有價值。

否則它不是一個正常的（即受限制的）四叉樹。在R-Trees上閱讀更多關於sub dividinbg個別矩形空間的信息。 （R樹是四叉樹的競爭對手） 對應四叉樹的唯一四類型平衡可能是動態的桶大小。但爲此我沒有看到優勢。

關於garuantees： 最終建立的靜態四叉樹的最大深度，給出了一個上限。 （隨意測量平均深度）。最大桶大小也提供了一個上限。 （再次衡量平均桶大小）。

平衡： 四叉樹的結構取決於插入值的順序。 插入到四叉樹中的值通常是靜態的，因此可以預先訂購。有特定的預先安排可以帶來（稍微）更好的平衡。

請注意，四叉樹是一種空間索引，對於刪除操作並不是很好用。