有人知道我在哪里可以找到一些文档，或者知道在四叉树中进行多少次插入和查询操作？
维基说O（logn），但是我发现另一个消息说O（nlogn），我需要知道哪个是真的。
我正在使用点四叉树
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
http://en.wikipedia.org/wiki/Quadtree
最佳答案
搜索：O（logn）：必须遍历整棵树才能找到元素。具体而言，这种情况下的日志为log_4，因为有4个子级。
插入（单点）：O（登录）：必须遍历树的位置以找到插入位置，然后进行少量的固定工作才能在该象限中分割点。
插入（n个点）：O（nlogn），必须插入每个点，从而导致nlogn。我希望这是您阅读过的其他网站所表示的意思，否则它们将是非常错误的。
原始论文被Finkel和Bentley称为“ Quad树，用于在复合键上检索的数据结构”。
关于java - 四叉树性能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16612932/