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-мерное дерево — это несбалансированное дерево поиска для хранения точек из . Оно предлагает похожую на R-дерево возможность поиска в заданном диапазоне ключей. В ущерб простоте запросов, требования к памяти вместо .

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

В неоднородном k-d дереве при параллельно оси -мерной гиперплоскости в точке . Для корня нужно разделить точки через гиперплоскость на два по возможности одинаково больших множества точек и записать в корень, слева от этого сохраняются все точки у которых , справа те у которых . Для левого поддерева нужно разделить точки опять на новую «разделенную плоскость» , а сохраняется во внутреннем узле. Слева от этого сохраняются все точки у которых . Это продолжается рекурсивно над всеми пространствами. Потом всё начинается снова с первого пространства до того, пока каждую точку можно будет ясно идентифицировать через гиперплоскость.

K-d дерево можно построить за . Поиск диапазона может быть выполнен за , при этом обозначает размер ответа. Требование к памяти для самого дерева ограничено .

Операции с k-d деревьями[править | править вики-текст]

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

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

const 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  минимальная длина

Функция 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; // правое поддерево			
}
}
Анализ

Очевидно, что минимальное количество просмотренных элементов это , где h — это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это , то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.

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

Для второй подзадачи, как мы уже вычислили, поиск элементов в заданном диапазоне выполняется за . Чтобы узнать среднее, достаточно просто сложить эти две величины:

.

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

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

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