K-вимірне дерево — це незбалансоване дерево пошуку для зберігання точок з . Воно пропонує схожу на R-дерево можливість пошуку в заданому діапазоні ключів. На шкоду простоті запитів, вимоги до пам'яті замість .
Існують однорідні й неоднорідні k-d дерева. В однорідних k-d дерев кожен вузол зберігає запис. При неоднорідному варіанті внутрішні вузли містять тільки ключі, листя містить посилання на записи.
У неоднорідному k-d дереві при паралельно осі -мірної гіперплощини в точці . Для кореня потрібно розділити точки через гіперплощину на дві по можливості однаково великі безлічі точок і записати в корінь, ліворуч від цього зберігаються всі точки, у яких , праворуч ті, у яких . Для лівого піддерева потрібно розділити точки знову на нову «розділену площину» , а зберігається у внутрішньому вузлі. Зліва від цього зберігаються всі точки, у яких . Це триває рекурсивно над усіма просторами. Потім все починається знову з першого простору, доки кожну точку можна буде ясно ідентифікувати через гіперплощину.
K-d дерево можна побудувати за . Пошук діапазону можна виконати за , при цьому позначає розмір відповіді. Вимогу до пам'яті для самого дерева обмежено .
[1]
Операції з k-d деревами
Структура
Структура дерева, описана на мові C ++:
constN=10;// Кількість просторів ключівstructItem{// структура елементаintkey[N];// Масив ключів визначає елементchar*info;// Інформація елемента};structNode{// структура вузла дереваItemi;// ЕлементNode*left;// Ліве піддеревоNode*right;// Праве піддерево}
Структура дерева може змінюватись в залежності від деталей реалізації алгоритму. Наприклад, у вузлі може міститися не один елемент, а масив, що підвищує ефективність пошуку.
Аналіз пошуку елемента
Очевидно, що мінімальна кількість переглянутих елементів дорівнює , а максимальна кількість переглянутих елементів — , де — це висота дерева. Залишається порахувати середню кількість переглянутих елементів .
— заданий елемент.
Розглянемо випадок . Знайденими елементами можуть бути:
і так для кожного простору ключів. При цьому середня довжина пошуку в одному просторі становить:
.
Середня величина розраховується за формулою:
Залишається знайти ймовірність . Вона дорівнює , де — число випадків, коли , і — загальне число випадків.
Не складно здогадатись, що
Підставляємо це в формулу для середньої величини:
тобто, , де — висота дерева.
Якщо перейти від висоти дерева до кількості елементів, то:
, де — кількість елементів у вузлі.
З цього можна зробити висновок, що чим більше елементів буде міститись у вузлі, тим швидше буде проходити пошук по дереву, оскільки висота дерева залишатиметься мінімальною, проте не слід зберігати величезну кількість елементів у вузлі, оскільки при такому способі все дерево може дегенерувати у звичайний масив або список.
Додавання елементів
Додавання елементів відбувається точно так само, як і в звичайному двійковому дереві пошуку, з тією лише різницею, що кожен рівень дерева буде визначатися ще й простором, до якого він відноситься.
Алгоритм просування по дереву:
for(inti=0;tree;i++)// i - це номер просторуif(tree->x[i]<tree->t)// t - медіанаtree=tree->left;// Переходимо в ліве піддеревоelsetree=tree->right;// Переходимо в праве піддерево
Додавання виконується за , де — висота дерева.
Видалення елементів
При видаленні елементів дерева може виникнути декілька ситуацій.
Видалення листа дерева — досить просте видалення, коли видаляється один вузол, і покажчик вузла-предка просто обнуляється.[2]
Видалення вузла дерева (не листа) — дуже складна процедура, при якій доводиться перебудовувати все піддерево для даного вузла.
Іноді процес видалення вузла вирішується модифікаціями k-d дерева. Наприклад, якщо у нас у вузлі міститься масив елементів, то при видаленні всього масиву вузол дерева залишається, але нові елементи туди більше не записуються.
Пошук діапазону елементів
Пошук заснований на звичайному спуску по дереву, коли кожен вузол перевіряється на діапазон. Якщо медіани вузла менше або більше заданого діапазону в даному просторі, то обхід йде далі по одній з гілок дерева. Якщо ж медіана вузла входить повністю в заданий діапазон, то потрібно відвідати обидва піддерева.[3]
Алгоритм
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;// Ліве піддерево}elseIf([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 дерева дає таку характеристику:
для фіксованого діапазону.
Якщо перейти від висоти дерева до кількості елементів, то це буде:
Пошук найближчого сусіда
Пошук найближчого елемента розділяється на дві підзадачі:
1) визначення можливого найближчого елемента;
2) пошук найближчих елементів в заданому діапазоні.
Дано дерево .
Ми спускаємося по дереву до його листа за умовою і визначаємо ймовірний найближчий елемент за умовою .
Після цього від кореня дерева запускається алгоритм пошуку найближчого елемента в заданому діапазоні, який визначається радіусом .
Радіус пошуку коригується при знаходженні найближчого елемента.[4]
Алгоритм
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);// Додати новий елемент у список}Elseif(довжинирівні)Add(List);// Додати новий елемент у списокIf((x_0=x[i]_0)&&(x_1=x[i]_1)&&...&&(x_n=x[i]_n))Return1;}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);// Додати новий елемент у список}Elseif(довжинирівні)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 — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це , тобто перегляд всіх вузлів. Залишається порахувати середню кількість переглянутих елементів.
— заданий елемент, щодо якого потрібно знайти найближчий.
Це завдання розділяється на дві підзадачі: знаходження найближчого елемента у вузлі й знаходження найближчого елемента в заданому діапазоні.
Для вирішення першої підзадачі потрібен один спуск по дереву, тобто .
Для другої підзадачі, як ми вже вирахували, пошук елементів в заданому діапазоні виконується за .
Щоб дізнатися середнє, досить просто скласти ці дві величини:
↑Lee, D. T.; Wong, C. K. (1977). Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica. 9. doi:10.1007/BF00263763.
libANN [Архівовано 15 січня 2021 у Wayback Machine.] 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.