どこでドキュメントを見つけることができるか、または四分木で挿入とクエリにかかる操作の数を知っている人はいますか?
wiki は 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 つの子があるためです。
Insert(single point): O(logn): ツリーの場所をトラバースして挿入場所を見つける必要があります。次に、その象限内のポイントを分割するための少量の一定量の作業が必要です。
Insert(n points): O(nlogn)、すべてのポイントを挿入する必要があり、nlogn につながります。これがあなたが読んだ他のサイトがnlognであることを意味していることを願っています。そうでなければ、それらは非常に間違っているでしょう.
元の論文は、Finkel と Bentley による「Quad trees a data structure for retrieve on composite keys」と呼ばれています。