java - 四叉树性能

Question

任何人都知道我在哪里可以找到一些文档，或者知道四叉树中有多少操作插入和查询？

wiki 说 O(logn) 但我发现另一个来源说 O(nlogn) 我需要知道哪个是真的。

我正在使用点四叉树

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C http://en.wikipedia.org/wiki/Quadtree

Answer 1

搜索：O(logn)：它必须遍历整个树才能找到元素。具体来说，这种情况下的日志是 log_4，因为有 4 个孩子。

插入（单点）：O（logn）：您必须遍历树位置以找到插入位置，然后进行一些小的恒定工作量来分割该象限中的点。

Insert(n points)：O(nlogn)，每个点都必须插入，导致 nlogn。我希望这就是您阅读的其他站点的意思，否则它们将是非常错误的。

最初的论文被 Finkel 和 Bentley 称为“四叉树一种用于检索复合键的数据结构”。