Quadtree Performance

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, иначе они были бы очень неправы.

Финкель и Бентли назвали оригинальную статью "Структура деревьев для поиска по составным ключам".