k-вимірне дерево

В інформатиці k-d дерево (англ. k-d tree, скорочення від k-вимірне дерево) — це структура даних з поділом простору для упорядкування точок в k-вимірному просторі. K-d дерева використовуються для деяких застосувань, таких як пошук у багатовимірному просторі ключів (пошук діапазонів^[en] і пошук найближчого сусіда). 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)$ . ^[1]

Операції з 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}}\left(\sum _{k=1}^{n}{k2^{k}}+\sum _{k=1}^{n}{2^{k}}-2^{n}-n2^{n}\right)=

={\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\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({\frac {n}{N}}+1)}}{2^{\log({\frac {n}{N}}+1)}-1}}-1\right)=~O\left(\log \left({\frac {n}{N}}+1\right){\frac {n+N}{n}}-1\right)=

$=~O\left(\log \left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)$ , де $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$ — висота дерева.

Видалення елементів

При видаленні елементів дерева може виникнути декілька ситуацій.

Видалення листа дерева — досить просте видалення, коли видаляється один вузол, і покажчик вузла-предка просто обнуляється.^[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; // Ліве піддерево
}
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)})$

Пошук найближчого сусіда

Пошук найближчого елемента розділяється на дві підзадачі:

1) визначення можливого найближчого елемента;

2) пошук найближчих елементів в заданому діапазоні.

Анімація NN пошука с a k-d дерева в двох масивах

Дано дерево $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})}}$ .

Радіус пошуку коригується при знаходженні найближчого елемента.^[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); // Додати новий елемент у список
      }
      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}))$ .

Див. також

Посилання

↑ Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM. 18 (9): 509. doi:10.1145/361002.361007.
↑ Chandran, Sharat. Introduction to kd-trees [Архівовано 23 вересня 2015 у Wayback Machine.]. University of Maryland Department of Computer Science.
↑ 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.
↑ Freidman, J. H.; Bentley, J. L.; Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software. 3 (3): 209. doi:10.1145/355744.355745.

Зовнішні посилання

libkdtree ++, an open-source STL-like implementation of k — d trees in C ++.
A tutorial on KD Trees
FLANN and its fork nanoflann [Архівовано 28 грудня 2014 у Wayback Machine.], efficient C ++ implementations of k — d tree algorithms.
kdtree [Архівовано 9 січня 2015 у Wayback Machine.] A simple C library for working with KD-Trees
KD Tree Demo, Java applet [Архівовано 29 червня 2020 у Wayback Machine.]
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.
Heuristic Ray Shooting Algorithms [Архівовано 11 листопада 2016 у Wayback Machine.], pp. 11 and after
Into contains open source implementations of exact and approximate (k) NN search methods using k — d trees in C ++.

[1] Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM. 18 (9): 509. doi:10.1145/361002.361007.

[2] Chandran, Sharat. Introduction to kd-trees [Архівовано 23 вересня 2015 у Wayback Machine.]. University of Maryland Department of Computer Science.

[Lee1977-3] 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.

[Friedman:1977:AFB:355744.355745-4] Freidman, J. H.; Bentley, J. L.; Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software. 3 (3): 209. doi:10.1145/355744.355745.

[1]

[2]

[3]

[4]

п о р Деревні структури даних
Дерева пошуку (динамічні множини/асоціативні масиви)	2–3^[en] 2–3–4^[en] АА^[en] (a,b)^[en] АВЛ Б Б+ Б*^[en] Б^x^[en] (Оптимальний^[en]) Двійковий пошук Збалансоване за вагою^[en] Інтервальне^[en] Порядкова статистика^[en] Рандомізований двійковий пошук^[en] Розширюване Т^[en] Танцювальне^[en] ХДерево^[en] Цап-відбувайло^[en] (Лівобічне^[en]) Червоно-чорне UB
Купи	Біноміальна Ван Емде Боаса Двійкова Лівацька^[en] Скошена^[en] Спарена^[en] Фібоначчієва
Префіксні дерева	Базисне Суфіксне Тернарного пошуку Хеш^[en] X-швидке^[en] Y-швидке^[en]
Дерева просторового розбиття даних	БВП^[en] БК^[en] БРП Відрізків ВП^[en] Гільбертове R^[en] Декартове k-вимірне (неявне k-вимірне^[en]) Дерево квадрантів М^[en] Метричне^[en] Октодерево Пріоритетизоване R^[en] R R+^[en] R* X^[en]
Інші дерева	Двозв'язкове^[en] Динамічне^[en] Діапазонне^[en] Експоненційне^[en] Злиття^[en] iDistance^[en] k-арне^[en] LSM Дерево Меркла Над^[en] Некореневе двійкове Пальцеве^[en] PQ Покриттів^[en] SPQR^[en] Фенвіка Хеш-календар^[en]