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 个 child 。

插入(单点):O(logn):您必须遍历树的位置以找到插入位置，然后进行一些小的常量工作来拆分该象限中的点。

Insert(n points):O(nlogn)，每个点都必须插入，导致nlogn。我希望这就是您阅读的其他站点的意思是 nlogn，否则他们就大错特错了。

Finkel 和 Bentley 的原始论文名为“四叉树一种用于检索复合键的数据结构”。