K-d-дерево

K-мерное дерево
Тип	Многомерное дерево Двоичное дерево поиска
Год изобретения	1975
Автор	Йон Бентли
Сложность в О-символике
В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(n) Вставка O(log n) O(n) Удаление O(log n) O(n)

Трёхмерное дерево.

k-d-дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d-деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d-деревья — особый вид двоичных деревьев поиска.

Математическое описание

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

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

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

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

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

Структура

Структура дерева, описанная на языке C++:

constexpr int N=10; // количество пространств ключей

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

struct Node {   // структура узла дерева
  Item i;       // элемент
  Node *left;   // левое  поддерево
  Node *right;  // правое поддерево
}

Структура дерева может меняться в зависимости от деталей реализации алгоритма. Например, в узле может содержаться не один элемент, а массив, что повышает эффективность поиска.

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

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

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

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

$find(t_1):[(x_0=t_1)];A=1.$

$find(t_2):[(x_0<t_1)\wedge (x_0=t_2)];A=2.$

$find(t_3):[(x_0>t_1)\wedge (x_0=t_3)];A=2.$

$find(t_4):[(x_0<t_1)\wedge (x_0<t_2)\wedge (x_0=t_4)];A=3.$

$find(t_5):[(x_0<X_1)\wedge (x_0>t_2)\wedge (x_0=t_5)];A=3.$

$find(t_6):[(x_0<t_1)\wedge (x_0<t_3)\wedge (x_0=t_6)];A=3.$

$find(t_7):[(x_0<t_1)\wedge (x_0>t_3)\wedge (x_0=t_7)];A=3.$

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

$A=\frac{1+2+2+3+3+3+3}{7}=\frac{17}{7}\approx 2,4$.

Средняя величина считается по формуле: $A_n=\sum _{k=1}^{n}k{p}_{n,k}$

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

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

$A_n=\sum _{k=1}^{n}k{p}_{n,k}=\sum _{k=1}^{n}k\frac{2^{k-1}}{2^n-1}=\frac{1}{2^n-1}\sum _{k=1}^{n}k{2}^{k-1}=$

$=\frac{1}{2^n-1}\sum _{k+1=1}^n(k+1)2^k=\frac{1}{2^n-1}(\sum _{k+1=1}^{n}k{2}^k+\sum _{k+1=1}^n{2}^k)=$

$=\frac{1}{2^n-1}(\sum _{k=1}^{n}k{2}^k+\sum _{k=1}^n{2}^k-2^n-n{2}^n)=$

$=\frac{1}{2^n-1}(n{2}^{n+2}-(n+1)2^{n+1}+2-2^n+2^3-1-n{2}^n)=\frac{2^n(n-1)+1}{2^n-1}$,

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

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

$A_n=O\left(\frac{2^h(h-1)+1}{2^h-1}\right)=O(h\frac{2^h}{2^h-1}-1)=O(log(\frac{n}{N}+1)\frac{2^{log(\frac{n}{N}+1)}}{2^{log(\frac{n}{N}+1)}-1}-1)=O(log(\frac{n}{N}+1)\frac{n+N}{n}-1)=$

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

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

Добавление элементов

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

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

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

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

Удаление элементов

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

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

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

Иногда процесс удаления узла решается модификациями 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; // просмотреть левое поддерево
		}
}

Анализ

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

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

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

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

Поиск ближайшего соседа

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

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

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

Алгоритм

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

Анализ

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

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

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

$=O(h)+O(h\cdot log(h))=O(h)\cdot (O(log(h))+1))$.

См. также

• R-дерево
• VP-дерево
• Задача поиска ближайшего соседа

Ссылки

• 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++.