四叉树性能

Question

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

维基说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）：您必须遍历树的位置以找到插入位置，然后执行一些小的恒定工作量来分割该象限中的点。插入（n个点）：O（nlogn），每个点必须插入，导致nlogn。我希望这是你读的其他网站的意思是nlogn，否则他们会是非常错误的。

Finkel和Bentley将原始论文称为“Quad trees a composite structure for retrieval on composite keys”。