K-мерное дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
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 дерево (англ. k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве. k-d деревья используются для некоторых приложений, таких как поиск в многомерном пространстве ключей (поиск диапазона и поиск ближайшего соседа). k-d деревья — особый вид двоичных деревьев поиска.

Математическое описание[править | править вики-текст]

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

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

В неоднородном k-d дереве H_i(t) = (x_1, x_2, \ldots , x_{i-1}, t , x_{i+1}, \ldots , x_k) при 1 \leq i \leq 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++:

const 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)\land(x_0=t_2)]; A=2.

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

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

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

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

find(t_7): [(x_0<t_1)\land(x_0>t_3)\land(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 kp_{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 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}}=

=\frac{1}{2^n-1}\sum_{k+1=1}^n {({k+1})2^k}=\frac{1}{2^n-1}(\sum_{k+1=1}^n {k2^k} + \sum_{k+1=1}^n {2^k}) =

=\frac{1}{2^n-1}(\sum_{k=1}^n {k2^k} + \sum_{k=1}^n {2^k} - 2^n - n2^n) =

=\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}

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

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

A_n=~O(\frac{2^h (h-1) +1}{2^h-1}) = ~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 – минимальная длина
 
Функция 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){ // поиск ближайшего элемента в заданном диапазоне
	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_1,x_2...,x_n]+len>Z){ // если диапазон больше медианы 
			Near(Z->right); // просмотреть оба дерева
			Z=Z->left;			
}
		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; // правое поддерево			
}
}
Анализ

Очевидно, что минимальное количество просмотренных элементов это ~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})).

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]