K-d-дерево — Википедия
K-мерное дерево | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | Многомерное дерево Двоичное дерево поиска | |||||||||||||||
Год изобретения | 1975 | |||||||||||||||
Автор | Йон Бентли | |||||||||||||||
Сложность в О-символике | ||||||||||||||||
| ||||||||||||||||
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/250px-3dtree.png)
k-d-дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d-деревья — особый вид двоичных деревьев поиска.
Математическое описание
[править | править код]K-мерное дерево — это несбалансированное дерево поиска для хранения точек из . Оно предлагает похожую на R-дерево возможность поиска в заданном диапазоне ключей. В ущерб простоте запросов, требования к памяти вместо .
Существуют однородные и неоднородные k-d-деревья. У однородных k-d-деревьев каждый узел хранит запись. При неоднородном варианте внутренние узлы содержат только ключи, листья содержат ссылки на записи.
В неоднородном k-d-дереве при параллельно оси -мерной гиперплоскости в точке . Для корня нужно разделить точки через гиперплоскость на два по возможности одинаково больших множества точек и записать в корень, слева от этого сохраняются все точки у которых , справа те у которых . Для левого поддерева нужно разделить точки опять на новую «разделенную плоскость» , а сохраняется во внутреннем узле. Слева от этого сохраняются все точки у которых . Это продолжается рекурсивно над всеми пространствами. Потом всё начинается снова с первого пространства до того, пока каждую точку можно будет ясно идентифицировать через гиперплоскость.
k-d-дерево можно построить за . Поиск диапазона может быть выполнен за , при этом обозначает размер ответа. Требование к памяти для самого дерева ограничено .
Операции с k-d-деревьями
[править | править код]Структура
[править | править код]Структура дерева, описанная на языке C++:
constexpr int N=10; // количество пространств ключей struct Item { // структура элемента int key[N]; // массив ключей определяющих элемент char *info; // информация элемента }; struct Node { // структура узла дерева Item i; // элемент Node *left; // левое поддерево Node *right; // правое поддерево }
Структура дерева может меняться в зависимости от деталей реализации алгоритма. Например, в узле может содержаться не один элемент, а массив, что повышает эффективность поиска.
- Анализ поиска элемента
Очевидно, что минимальное количество просмотренных элементов равно , а максимальное количество просмотренных элементов — , где — это высота дерева. Остаётся посчитать среднее количество просмотренных элементов .
— заданный элемент.
Рассмотрим случай . Найденными элементами могут быть:
и так для каждого пространства ключей. При этом средняя длина поиска в одном пространстве составляет:
- .
Средняя величина считается по формуле:
Остаётся найти вероятность . Она равна , где — число случаев, когда и — общее число случаев. Не сложно догадаться, что .
Подставляем это в формулу для средней величины:
- ,
то есть , где — высота дерева.
Если перейти от высоты дерева к количеству элементов, то:
, где — количество элементов в узле.
Из этого можно сделать вывод, что чем больше элементов будет содержаться в узле, тем быстрее будет проходить поиск по дереву, так как высота дерева будет оставаться минимальной, однако не следует хранить огромное количество элементов в узле, так как при таком способе всё дерево может выродиться в обычный массив или список.
Добавление элементов
[править | править код]Добавление элементов происходит точно так же, как и в обычном двоичном дереве поиска, с той лишь разницей, что каждый уровень дерева будет определяться ещё и пространством к которому он относится.
Алгоритм продвижения по дереву:
for (int i = 0; tree; i++) // i - это номер пространства if (tree->x[i] < tree->t) // t - медиана tree = tree->left; // переходим в левое поддерево else tree = tree->right; // переходим в правое поддерево
Добавление выполняется за , где — высота дерева.
Удаление элементов
[править | править код]При удалении элементов дерева может возникнуть несколько ситуаций:
- Удаление листа дерева — довольно простое удаление, когда удаляется один узел и указатель узла-предка просто обнуляется.
- Удаление узла дерева (не листа) — очень сложная процедура, при которой приходится перестраивать всё поддерево для данного узла.
Иногда процесс удаления узла решается модификациями k-d-дерева. К примеру, если у нас в узле содержится массив элементов, то при удалении всего массива узел дерева остаётся, но новые элементы туда больше не записываются.
Поиск диапазона элементов
[править | править код]Поиск основан на обычном спуске по дереву, когда каждый узел проверяется на диапазон. Если медианы узла меньше или больше заданного диапазона в данном пространстве, то обход идет дальше по одной из ветвей дерева. Если же медиана узла входит полностью в заданный диапазон, то нужно посетить оба поддерева.
- Алгоритм
Z – узел дерева [(x_0_min, x_1_min, x_2_min,..., x_n_min),(x_0_max, x_1_max, x_2_max,..., x_n_max)] - заданный диапазон Функция Array(Node *&Z){ If ([x_0_min, x_1_min, x_2_min,..., x_n_min]<Z){ Z=Z->left; // левое поддерево } else If ([x_0_max, x_1_max, x_2_max,..., x_n_max]>Z){ Z=Z->right; // правое поддерево } Else{ // просмотреть оба поддерева Array(Z->right); // запустить функцию для правого поддерева Z=Z->left; // просмотреть левое поддерево } }
- Анализ
Очевидно, что минимальное количество просмотренных элементов это , где — высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это , то есть просмотр всех элементов дерева. Остаётся посчитать среднее количество просмотренных элементов .
— заданный диапазон.
Оригинальная статья про k-d-деревья даёт такую характеристику: для фиксированного диапазона.
Если перейти от высоты дерева к количеству элементов, то это будет:
Поиск ближайшего соседа
[править | править код]Поиск ближайшего элемента разделяется на две подзадачи: определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне.
Дано дерево . Мы спускаемся по дереву к его листьям по условию и определяем вероятный ближайший элемент по условию . После этого от корня дерева запускается алгоритм поиска ближайшего элемента в заданном диапазоне, который определяется радиусом .
Радиус поиска корректируется при нахождении более близкого элемента.
- Алгоритм
Z – корень дерева List – список для найденных ближайших элементов [x_0,x_1,x_2...,x_n] - координаты всех измерений нашего элемента, для которого и ищутся ближайшие Len – минимальная длина CHILDREN - максимальное число детей у каждого элемента Функция Maybe_Near(Node *&Z) { // поиск ближайшего возможного элемента while (Z) { for (i=0;i<N;i++) { // проверка элементов в узле len_cur = sqrt((x_0-x[i]_0)^2 + (x_1-x[i]_1)^2 + ... + (x_n-x[i]_n)^2); // длина текущего элемента if (Len > длины текущего элемента) { Len = len_cur; // установление новой длины Delete(List); // очистка списка Add(List); // добавить новый элемент в список } else if(длины равны) { Add(List); // добавить новый элемент в список } if ((x_0 == x[i]_0) && (x_1 == x[i]_1) && ... && (x_n == x[i]_n)) { return 1; } } if ([x_0,x_1,x_2...,x_n] < Z) Z = Z->left; // левое поддерево if ([x_0,x_1,x_2...,x_n] > Z) Z = Z->right; // правое поддерево } } Функция Near(Node *&Z) { // рекурсивный поиск ближайшего элемента в заданном диапазоне if (!Z) { return List; } len_cur = sqrt((x_0-x[i]_0)^2 + (x_1-x[i]_1)^2 + ... + (x_n-x[i]_n)^2); // расстояние от нашей точки до текущей if (len_cur < Len) { // нашли длину меньше минимальной Len = len_cur; // установление новой минимальной длины Delete(List); // очистка списка - ведь все найденные до этого элементы находятся дальше, чем текущий Add(List, Z); // добавить текущий элемент в список } else if (len_cur == Len) { // длина равна минимальной Add(List, Z); // просто добавить новый элемент в список } for (i = 0; i < CHILDREN; i++) { // для всех дочерних элементов выполним то же самое Near(Z->children[i]); // просмотреть все поддеревья } }
- Анализ
Очевидно, что минимальное количество просмотренных элементов это , где h — это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это , то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.
— заданный элемент, относительно которого нужно найти ближайший. Эта задача разделяется на две подзадачи: нахождение ближайшего элемента в узле и нахождение ближайшего элемента в заданном диапазоне. Для решения первой подзадачи потребуется один спуск по дереву, то есть .
Для второй подзадачи, как мы уже вычислили, поиск элементов в заданном диапазоне выполняется за . Чтобы узнать среднее, достаточно просто сложить эти две величины:
.
См. также
[править | править код]Примечания
[править | править код]Ссылки
[править | править код]- libkdtree++, an open-source STL-like implementation of k-d trees in C++.
- A tutorial on KD Trees
- FLANN and its fork nanoflann, efficient C++ implementations of k-d tree algorithms.
- kdtree A simple C library for working with KD-Trees
- K-D Tree Demo, Java applet Архивная копия от 29 июня 2020 на Wayback Machine
- libANN Approximate Nearest Neighbour Library includes a k-d tree implementation
- Caltech Large Scale Image Search Toolbox: a Matlab toolbox implementing randomized k-d tree for fast approximate nearest neighbour search, in addition to LSH, Hierarchical K-Means, and Inverted File search algorithms.
- Heuristic Ray Shooting Algorithms, pp. 11 and after
- Into contains open source implementations of exact and approximate (k)NN search methods using k-d trees in C++.
Для улучшения этой статьи желательно:
|