四叉树范围搜索的复杂性
Complexity of quad tree's range search
我已经搜索过此信息。找到这个：
https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA
还有这个：
，但我认为它不能解决我的问题。也许是第一个，但我不明白解释。到此为止。
我在离散 space（实体的二维正方形 table 上）有一个四叉树。它是一个区域树，如英语维基百科页面 (https://en.wikipedia.org/wiki/Quadtree#Types) 中所述。每个区域只能容纳一个实体。每个实体都有其离散坐标。
我已经实现了一种方法来查找某些（离散的）AABB 中的所有实体，其工作方式与上述 Wiki 页面中的 queryRange() 功能完全相同。
我的问题是：这个 queryRange() 函数的时间复杂度是多少？
我已经尝试自己弄清楚了，但这似乎取决于许多不同的因素，例如：树的深度、树中元素的数量、给定 AABB 的大小。我认为它的核心是与 queryRange() 递归访问的子树数量有关。
此外，如果有任何可靠的消息来源，我将不胜感激。我正在写一篇硕士论文，我需要引用。不过，我似乎真的 google 对这个话题没有任何好处。
查询的时间复杂度取决于很多方面：
- 数据分布
- 插入顺序（除非你重新平衡树）
- 无论您存储点还是矩形（据我所知，点更常见）
- 您正在执行的查询类型
我不是复杂度计算方面的专家，所以可能有一些方法可以计算平均复杂度，但它可能对给定的真实场景没有用。
最大复杂度更容易一些。假设 n 是条目数，h 是树的高度。
一个大查询显然会return所有元素，所以复杂度是O(n)。一个非常狭窄的查询将不得不从根遍历到恰好一个叶子，因此 O(h)。这给出组合的 O(n+h)。
有一些边界情况：例如，如果数据的形状使得所有点都在一条线上 (0,1),(0,2),(0,3),(0,4 ),... 并且它们是按顺序插入的，那么树可能会退化为一个列表，使得 h=n，除非你执行一些重新平衡。
如果你对四叉树变体感兴趣，不妨看看最近的PH-Tree. The PDF contains some complexity calculations. The PH-Tree is a region quadtree (decomposition into quadrants) based on bit-level-trie decomposition. The maximum depth is therefore equal to the number of bits in the values, usually 32 or 64. The structure is independent of the insertion order, so there is no rebalancing (nor is it required, because depth is limited). Some technical updates can be found here。 （免责声明：这是基于我在大学期间的研究）。
我已经搜索过此信息。找到这个：
https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA
还有这个：
，但我认为它不能解决我的问题。也许是第一个，但我不明白解释。到此为止。
我在离散 space（实体的二维正方形 table 上）有一个四叉树。它是一个区域树，如英语维基百科页面 (https://en.wikipedia.org/wiki/Quadtree#Types) 中所述。每个区域只能容纳一个实体。每个实体都有其离散坐标。
我已经实现了一种方法来查找某些（离散的）AABB 中的所有实体，其工作方式与上述 Wiki 页面中的 queryRange() 功能完全相同。
我的问题是：这个 queryRange() 函数的时间复杂度是多少？
我已经尝试自己弄清楚了，但这似乎取决于许多不同的因素，例如：树的深度、树中元素的数量、给定 AABB 的大小。我认为它的核心是与 queryRange() 递归访问的子树数量有关。
此外，如果有任何可靠的消息来源，我将不胜感激。我正在写一篇硕士论文，我需要引用。不过，我似乎真的 google 对这个话题没有任何好处。
查询的时间复杂度取决于很多方面：
- 数据分布
- 插入顺序（除非你重新平衡树）
- 无论您存储点还是矩形（据我所知，点更常见）
- 您正在执行的查询类型
我不是复杂度计算方面的专家，所以可能有一些方法可以计算平均复杂度，但它可能对给定的真实场景没有用。
最大复杂度更容易一些。假设 n 是条目数，h 是树的高度。
一个大查询显然会return所有元素，所以复杂度是O(n)。一个非常狭窄的查询将不得不从根遍历到恰好一个叶子，因此 O(h)。这给出组合的 O(n+h)。
有一些边界情况：例如，如果数据的形状使得所有点都在一条线上 (0,1),(0,2),(0,3),(0,4 ),... 并且它们是按顺序插入的，那么树可能会退化为一个列表，使得 h=n，除非你执行一些重新平衡。
如果你对四叉树变体感兴趣，不妨看看最近的PH-Tree. The PDF contains some complexity calculations. The PH-Tree is a region quadtree (decomposition into quadrants) based on bit-level-trie decomposition. The maximum depth is therefore equal to the number of bits in the values, usually 32 or 64. The structure is independent of the insertion order, so there is no rebalancing (nor is it required, because depth is limited). Some technical updates can be found here。 （免责声明：这是基于我在大学期间的研究）。