Просмотр кода страницы K-d-дерево

{{Структура_данных
|name= K-мерное дерево
|type= Многомерное дерево [[Двоичное дерево поиска]]
|invented_by= [[Бентли, Йон|Йон Бентли]]
|invented_year= 1975
|
|space_avg= O(''n'')
|space_worst= O(''n'')
|search_avg= O(log ''n'')
|search_worst= O(''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(''n'')
|delete_avg= O(log ''n'')
|delete_worst= O(''n'')
}}
[[Файл:3dtree.png|thumb|Трёхмерное дерево.|250px|right]]

'''''k''-d-дерево''' ({{lang-en|k-d tree}}, сокращение от ''k-мерное [[дерево (структура данных)|дерево]]'') — это [[структура данных]] с разбиением пространства для упорядочивания [[точка (геометрия)|точек]] в ''k''-мерном [[Евклидово пространство|пространстве]]. ''k''-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и [[Задача поиска ближайшего соседа|поиск ближайшего соседа]]). ''k''-d-деревья — особый вид [[двоичное дерево поиска|двоичных деревьев поиска]].

== Математическое описание ==
K-мерное дерево — это несбалансированное дерево поиска для хранения точек из <math>\mathbb{R}^k</math>. Оно предлагает похожую на [[R-дерево (структура данных)|R-дерево]] возможность поиска в заданном диапазоне ключей. В ущерб простоте запросов, требования к памяти <math>O(kn)</math> вместо <math>O((log(n))^{k-1})</math>.

Существуют однородные и неоднородные k-d-деревья. У однородных k-d-деревьев каждый узел хранит [[Запись (тип данных)|запись]]. При неоднородном варианте внутренние узлы содержат только ключи, листья содержат ссылки на записи.

В неоднородном k-d-дереве <math>H_i(t) = (x_1, x_2, \ldots , x_{i-1}, t , x_{i+1}, \ldots , x_k)</math> при <math>1 \leq i \leq k </math> параллельно оси <math>(k-1)</math>-мерной [[Гиперплоскость|гиперплоскости]] в точке <math>t</math>. Для корня нужно разделить точки через гиперплоскость <math>H_1(t)</math> на два по возможности одинаково больших множества точек и записать <math>t</math> в корень, слева от этого сохраняются все точки у которых <math>x_1<t</math>, справа те у которых <math>x_1>t</math>. Для левого поддерева нужно разделить точки опять на новую «разделенную плоскость» <math>H_2(t)</math>, а <math>t</math> сохраняется во внутреннем узле. Слева от этого сохраняются все точки у которых <math>x_2<t</math>. Это продолжается рекурсивно над всеми пространствами. Потом всё начинается снова с первого пространства до того, пока каждую точку можно будет ясно идентифицировать через гиперплоскость.

k-d-дерево можно построить за <math>O(n(k+log(n)))</math>. Поиск диапазона может быть выполнен за <math>O(n^{1-\frac{1}{k}}+a)</math>, при этом <math>a</math> обозначает размер ответа. Требование к памяти для самого дерева ограничено <math>O(kn)</math>.

== Операции с ''k''-d-деревьями ==

=== Структура ===
Структура дерева, описанная на языке [[C++]]:
<source lang="cpp">
constexpr int N=10; // количество пространств ключей

struct Item {   // структура элемента
  int key[N];   // массив ключей определяющих элемент
  char *info;   // информация элемента
};

struct Node {   // структура узла дерева
  Item i;       // элемент
  Node *left;   // левое  поддерево
  Node *right;  // правое поддерево
}
</source>
Структура дерева может меняться в зависимости от деталей реализации [[алгоритм]]а. Например, в узле может содержаться не один элемент, а [[Массив (программирование)|массив]], что повышает эффективность поиска.

; Анализ поиска элемента

Очевидно, что минимальное количество просмотренных элементов равно <math>1</math>, а максимальное количество просмотренных элементов — <math>O(h)</math>, где <math>h</math> — это высота дерева. Остаётся посчитать среднее количество просмотренных элементов <math>A_n</math>.

<math>[x_0,x_1,x_2,...,x_n]</math> — заданный элемент.

Рассмотрим случай <math>h=3</math>. Найденными элементами могут быть:

: <math>
find(t_1): [(x_0=t_1)]; A=1.
</math>

: <math>
find(t_2): [(x_0<t_1)\land(x_0=t_2)]; A=2.
</math>

: <math>
find(t_3): [(x_0>t_1)\land(x_0=t_3)]; A=2.
</math>

: <math>
find(t_4): [(x_0<t_1)\land(x_0<t_2)\land(x_0=t_4)]; A=3.
</math>

: <math>
find(t_5): [(x_0<X_1)\land(x_0>t_2)\land(x_0=t_5)]; A=3.
</math>

: <math>
find(t_6): [(x_0<t_1)\land(x_0<t_3)\land(x_0=t_6)]; A=3.
</math>

: <math>
find(t_7): [(x_0<t_1)\land(x_0>t_3)\land(x_0=t_7)]; A=3.
</math>

и так для каждого пространства ключей. При этом средняя длина поиска в одном пространстве составляет:

: <math>A=\frac{1+2+2+3+3+3+3}{7}=\frac{17}{7}\approx 2,4</math>.

Средняя величина считается по формуле: <math>A_n=\sum_{k=1}^n kp_{n,k}</math>

Остаётся найти вероятность <math>p_{n,k}</math>. Она равна <math>p_{n,k}=\frac{p_{A,k}}{p_{n}}</math>, где <math>p_{A,k}</math> — число случаев, когда <math>A=k</math> и <math>p_{n}</math> — общее число случаев.
Не сложно догадаться, что <math>p_{n,k}=\frac{2^{k-1}}{2^n-1}</math>.

Подставляем это в формулу для средней величины:

: <math>
A_n=\sum_{k=1}^n kp_{n,k}=\sum_{k=1}^n {k\frac{2^{k-1}}{2^n-1}}=\frac{1}{2^n-1}\sum_{k=1}^n {k2^{k-1}}=
</math>

: <math>
=\frac{1}{2^n-1}\sum_{k+1=1}^n {({k+1})2^k}=\frac{1}{2^n-1}\left(\sum_{k+1=1}^n {k2^k} + \sum_{k+1=1}^n {2^k}\right) = 
</math>

: <math>
=\frac{1}{2^n-1}\left(\sum_{k=1}^n {k2^k} + \sum_{k=1}^n {2^k} - 2^n - n2^n \right) = 
</math>

: <math>
=\frac{1}{2^n-1}(n2^{n+2} - (n+1)2^{n+1} +2 - 2^n + 2^3 -1 - n2^n) = \frac{2^n (n-1) +1}{2^n-1}
</math>,

то есть <math>A_h=\frac{2^h (h-1) +1}{2^h-1}</math>, где <math>h</math> — высота дерева.

Если перейти от высоты дерева к количеству элементов, то:

: <math>A_n=~O\left(\frac{2^h (h-1) +1}{2^h-1}\right) = ~O\left(h\frac{2^h}{2^h-1} - 1\right) = ~O\left(log\left(\frac{n}{N} +1\right)\frac{2^{log\left(\frac{n}{N} +1\right)}}{2^{log\left(\frac{n}{N} +1\right)}-1} - 1\right)=~O\left(log\left(\frac{n}{N} +1\right)\frac{n+N}{n}-1\right) =</math>

<math>
=~O\left(log \left(\frac{n}{N} +1\right)^{\frac{n+N}{n}}-1\right)</math>, где <math>N</math> — количество элементов в узле.

Из этого можно сделать вывод, что чем больше элементов будет содержаться в узле, тем быстрее будет проходить поиск по дереву, так как высота дерева будет оставаться минимальной, однако не следует хранить огромное количество элементов в узле, так как при таком способе всё дерево может выродиться в обычный массив или список.

=== Добавление элементов ===
Добавление элементов происходит точно так же, как и в обычном [[двоичное дерево поиска|двоичном дереве поиска]], с той лишь разницей, что каждый уровень дерева будет определяться ещё и пространством к которому он относится.

Алгоритм продвижения по дереву:

<source lang="cpp">
for (int i = 0; tree; i++) // i - это номер пространства
    if (tree->x[i] < tree->t)  // t - медиана
        tree = tree->left;     // переходим в левое поддерево
    else
        tree = tree->right;    // переходим в правое поддерево
</source>

Добавление выполняется за <math>O(h)</math>, где <math>h</math> — высота дерева.

=== Удаление элементов ===
При удалении элементов дерева может возникнуть несколько ситуаций:

* Удаление листа дерева — довольно простое удаление, когда удаляется один узел и указатель узла-предка просто обнуляется.

* Удаление узла дерева (не листа) — очень сложная процедура, при которой приходится перестраивать всё поддерево для данного узла.

Иногда процесс удаления узла решается модификациями k-d-дерева. К примеру, если у нас в узле содержится массив элементов, то при удалении всего массива узел дерева остаётся, но новые элементы туда больше не записываются.

=== Поиск диапазона элементов ===
Поиск основан на обычном спуске по дереву, когда каждый узел проверяется на диапазон. Если [[Медиана (статистика)|медианы]] узла меньше или больше заданного диапазона в данном пространстве, то обход идет дальше по одной из ветвей дерева. Если же медиана узла входит полностью в заданный диапазон, то нужно посетить оба поддерева.

; Алгоритм
<source lang="cpp">
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; // просмотреть левое поддерево
		}
}
</source>

; Анализ

Очевидно, что минимальное количество просмотренных элементов это <math>O(h)</math>, где <math>h</math> — высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это <math>O(2^h-1)</math>, то есть просмотр всех элементов дерева. Остаётся посчитать среднее количество просмотренных элементов <math>A_n</math>.

<math>[(x_{0_{min}}, x_{1_{min}}, x_{2_{min}},..., x_{n_{min}}),(x_{0_{max}}, x_{1_{max}}, x_{2_{max}},..., x_{n_{max}})]</math> — заданный диапазон.

Оригинальная статья про k-d-деревья даёт такую характеристику:
<math>A_n=~O(h \cdot log(h))</math> для фиксированного диапазона.

Если перейти от высоты дерева к количеству элементов, то это будет:
<math>A_n=~O(log(log(n-1))^{log(n-1)})</math>

=== Поиск ближайшего соседа ===
Поиск ближайшего элемента разделяется на две подзадачи: определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне.

Дано дерево <math>tree</math>.
Мы спускаемся по дереву к его листьям по условию <math>tree\to x[i](<,>=)tree\to t</math> и определяем вероятный ближайший элемент по условию <math>l_{min}=\sqrt{(({x_0-x[i]_0})^2 + ({x_1-x[i]_1})^2 + ... + ({x_n-x[i]_n})^2)}</math>.
После этого от корня дерева запускается алгоритм поиска ближайшего элемента в заданном диапазоне, который определяется радиусом <math>R=l_{min}=\sqrt{(({x_0-x[i]_0})^2 + ({x_1-x[i]_1})^2 + ... + ({x_n-x[i]_n})^2)}</math>.

Радиус поиска корректируется при нахождении более близкого элемента.

; Алгоритм

<source lang="cpp">
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]); // просмотреть все поддеревья
    }
}
</source>

; Анализ

Очевидно, что минимальное количество просмотренных элементов это <math>O(h)</math>, где h — это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это <math>O(2^h-1)</math>, то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.

<math>[(x_0, x_1, x_2,..., x_n)]</math> — заданный элемент, относительно которого нужно найти ближайший.
Эта задача разделяется на две подзадачи: нахождение ближайшего элемента в узле и нахождение ближайшего элемента в заданном диапазоне.
Для решения первой подзадачи потребуется один спуск по дереву, то есть <math>O(h)</math>.

Для второй подзадачи, как мы уже вычислили, поиск элементов в заданном диапазоне выполняется за <math>O(h \cdot log(h))</math>.
Чтобы узнать среднее, достаточно просто сложить эти две величины:

<math>=~O(h)+ ~O(h \cdot log(h)) = ~O(h) \cdot ({~O(log(h))+1}))</math>.

== См. также ==
* [[R-дерево (структура данных)|R-дерево]]
* [[VP-дерево]]
* [[Задача поиска ближайшего соседа]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://web.archive.org/web/20170617153811/http://libkdtree.alioth.debian.org/ libkdtree++], an open-source STL-like implementation of ''k''-d trees in C++.
* [https://web.archive.org/web/20110716085331/http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en A tutorial on KD Trees]
* [https://web.archive.org/web/20120820113314/http://people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN FLANN] and its fork [http://code.google.com/p/nanoflann/ nanoflann], efficient C++ implementations of ''k''-d tree algorithms.
* [http://code.google.com/p/kdtree/ kdtree] A simple C library for working with KD-Trees
* [http://donar.umiacs.umd.edu/quadtree/points/kdtree.html K-D Tree Demo, Java applet] {{Wayback|url=http://donar.umiacs.umd.edu/quadtree/points/kdtree.html |date=20200629192750 }}
* [http://www.cs.umd.edu/~mount/ANN/ libANN] Approximate Nearest Neighbour Library includes a ''k''-d tree implementation
* [https://web.archive.org/web/20101203074412/http://www.vision.caltech.edu/malaa/software/research/image-search/ Caltech Large Scale Image Search Toolbox]: a Matlab toolbox implementing randomized ''k''-d tree for fast approximate nearest neighbour search, in addition to [[Locality sensitive hashing|LSH]], Hierarchical K-Means, and [[Inverted file|Inverted File]] search algorithms.
* [http://dcgi.felk.cvut.cz/home/havran/phdthesis.html Heuristic Ray Shooting Algorithms], pp. 11 and after
* [https://web.archive.org/web/20100709025652/http://intopii.com/into/ Into] contains open source implementations of exact and approximate (k)NN search methods using ''k''-d trees in C++.

{{rq|style|sources|wikify}}

{{Деревья (структуры данных)}}
{{Структуры данных}}

[[Категория:Деревья (структуры данных)]]
[[Категория:Алгоритмы]]
[[Категория:Геометрические структуры данных]]