k-вимірне дерево — Вікіпедія

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

K-вимірне дерево — це незбалансоване дерево пошуку для зберігання точок з ${\displaystyle \mathbb {R} ^{k}}$. Воно пропонує схожу на R-дерево можливість пошуку в заданому діапазоні ключів. На шкоду простоті запитів, вимоги до пам'яті ${\displaystyle ~O(kn)}$ замість ${\displaystyle ~O((\log(n))^{k-1})}$.

Існують однорідні й неоднорідні k-d дерева. В однорідних k-d дерев кожен вузол зберігає запис. При неоднорідному варіанті внутрішні вузли містять тільки ключі, листя містить посилання на записи.

У неоднорідному k-d дереві ${\displaystyle H_{i}(t)=(x_{1},x_{2},\ldots ,x_{i-1},t,x_{i+1},\ldots ,x_{k})}$ при ${\displaystyle 1\leq i\leq k}$ паралельно осі ${\displaystyle (k-1)}$ -мірної гіперплощини в точці ${\displaystyle t}$. Для кореня потрібно розділити точки через гіперплощину ${\displaystyle H_{1}(t)}$ на дві по можливості однаково великі безлічі точок і записати ${\displaystyle t}$ в корінь, ліворуч від цього зберігаються всі точки, у яких ${\displaystyle x_{1}<t}$, праворуч ті, у яких ${\displaystyle x_{1}>t}$. Для лівого піддерева потрібно розділити точки знову на нову «розділену площину» ${\displaystyle H_{2}(t)}$, а ${\displaystyle t}$ зберігається у внутрішньому вузлі. Зліва від цього зберігаються всі точки, у яких ${\displaystyle x_{2}<t}$. Це триває рекурсивно над усіма просторами. Потім все починається знову з першого простору, доки кожну точку можна буде ясно ідентифікувати через гіперплощину.

K-d дерево можна побудувати за ${\displaystyle ~O(n(k+\log(n)))}$. Пошук діапазону можна виконати за ${\displaystyle ~O(n^{1-{\frac {1}{k}}}+a)}$, при цьому ${\displaystyle a}$ позначає розмір відповіді. Вимогу до пам'яті для самого дерева обмежено ${\displaystyle ~O(kn)}$. ^[1]

Структура дерева, описана на мові C ++:

const N = 10; // Кількість просторів ключів  struct Item {// структура елемента   int key [N]; // Масив ключів визначає елемент   char * info; // Інформація елемента };  struct Node {// структура вузла дерева   Item i; // Елемент   Node * left; // Ліве піддерево   Node * right; // Праве піддерево } 

Структура дерева може змінюватись в залежності від деталей реалізації алгоритму. Наприклад, у вузлі може міститися не один елемент, а масив, що підвищує ефективність пошуку.

Аналіз пошуку елемента

Очевидно, що мінімальна кількість переглянутих елементів дорівнює ${\displaystyle 1}$, а максимальна кількість переглянутих елементів — ${\displaystyle ~O(h)}$, де ${\displaystyle h}$ — це висота дерева. Залишається порахувати середню кількість переглянутих елементів ${\displaystyle A_{n}}$.

${\displaystyle [x_{0},x_{1},x_{2},...,x_{n}]}$ — заданий елемент.

Розглянемо випадок ${\displaystyle h=3}$. Знайденими елементами можуть бути:

${\displaystyle find(t_{1}):[(x_{0}=t_{1})];A=1.}$

${\displaystyle find(t_{2}):[(x_{0}<t_{1})\land (x_{0}=t_{2})];A=2.}$

${\displaystyle find(t_{3}):[(x_{0}>t_{1})\land (x_{0}=t_{3})];A=2.}$

${\displaystyle find(t_{4}):[(x_{0}<t_{1})\land (x_{0}<t_{2})\land (x_{0}=t_{4})];A=3.}$

${\displaystyle find(t_{5}):[(x_{0}<X_{1})\land (x_{0}>t_{2})\land (x_{0}=t_{5})];A=3.}$

${\displaystyle find(t_{6}):[(x_{0}<t_{1})\land (x_{0}<t_{3})\land (x_{0}=t_{6})];A=3.}$

${\displaystyle find(t_{7}):[(x_{0}<t_{1})\land (x_{0}>t_{3})\land (x_{0}=t_{7})];A=3.}$

і так для кожного простору ключів. При цьому середня довжина пошуку в одному просторі становить:

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

Середня величина розраховується за формулою: ${\displaystyle A_{n}=\sum _{k=1}^{n}kp_{n,k}}$

Залишається знайти ймовірність ${\displaystyle p_{n,k}}$. Вона дорівнює ${\displaystyle p_{n,k}={\frac {p_{A,k}}{p_{n}}}}$, де ${\displaystyle p_{A,k}}$ — число випадків, коли ${\displaystyle A=k}$, і ${\displaystyle p_{n}}$ — загальне число випадків.

Не складно здогадатись, що ${\displaystyle p_{n,k}={\frac {2^{k-1}}{2^{n}-1}}}$

Підставляємо це в формулу для середньої величини:

${\displaystyle 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}}=}$

${\displaystyle ={\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}})=}$

${\displaystyle ={\frac {1}{2^{n}-1}}\left(\sum _{k=1}^{n}{k2^{k}}+\sum _{k=1}^{n}{2^{k}}-2^{n}-n2^{n}\right)=}$

${\displaystyle ={\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}}}$

тобто, ${\displaystyle A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1}}}$, де ${\displaystyle h}$ — висота дерева.

Якщо перейти від висоти дерева до кількості елементів, то:

${\displaystyle 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)=}$

${\displaystyle =~O\left(\log \left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)}$, де ${\displaystyle N}$ — кількість елементів у вузлі.

З цього можна зробити висновок, що чим більше елементів буде міститись у вузлі, тим швидше буде проходити пошук по дереву, оскільки висота дерева залишатиметься мінімальною, проте не слід зберігати величезну кількість елементів у вузлі, оскільки при такому способі все дерево може дегенерувати у звичайний масив або список.

Додавання елементів відбувається точно так само, як і в звичайному двійковому дереві пошуку, з тією лише різницею, що кожен рівень дерева буде визначатися ще й простором, до якого він відноситься.

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

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

Додавання виконується за ${\displaystyle ~O(h)}$, де ${\displaystyle 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; // Переглянути ліве піддерево } } 

Аналіз

Очевидно, що мінімальна кількість переглянутих елементів це ${\displaystyle ~O(h)}$, де ${\displaystyle h}$ — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це ${\displaystyle ~O(2^{h}-1)}$, тобто перегляд всіх елементів дерева. Залишається порахувати середню кількість переглянутих елементів ${\displaystyle A_{n}}$.

${\displaystyle [(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 дерева дає таку характеристику: ${\displaystyle A_{n}=~O(h\cdot \log(h))}$ для фіксованого діапазону.

Якщо перейти від висоти дерева до кількості елементів, то це буде: ${\displaystyle A_{n}=~O(\log(\log(n-1))^{\log(n-1)})}$

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

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

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

Дано дерево ${\displaystyle tree}$. Ми спускаємося по дереву до його листа за умовою ${\displaystyle tree\to x[i](<,>=)tree\to t}$ і визначаємо ймовірний найближчий елемент за умовою ${\displaystyle l_{min}={\sqrt {(({x_{0}-x[i]_{0}})^{2}+({x_{1}-x[i]_{1}})^{2}+...+({x_{n}-x[i]_{n}})^{2})}}}$. Після цього від кореня дерева запускається алгоритм пошуку найближчого елемента в заданому діапазоні, який визначається радіусом ${\displaystyle 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; // Праве піддерево } } 

Аналіз

Очевидно, що мінімальна кількість переглянутих елементів це ${\displaystyle ~O(h)}$, де h — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це ${\displaystyle ~O(2^{h}-1)}$, тобто перегляд всіх вузлів. Залишається порахувати середню кількість переглянутих елементів.

${\displaystyle [(x_{0},x_{1},x_{2},...,x_{n})]}$ — заданий елемент, щодо якого потрібно знайти найближчий. Це завдання розділяється на дві підзадачі: знаходження найближчого елемента у вузлі й знаходження найближчого елемента в заданому діапазоні. Для вирішення першої підзадачі потрібен один спуск по дереву, тобто ${\displaystyle ~O(h)}$.

Для другої підзадачі, як ми вже вирахували, пошук елементів в заданому діапазоні виконується за ${\displaystyle ~O(h\cdot \log(h))}$. Щоб дізнатися середнє, досить просто скласти ці дві величини:

${\displaystyle =~O(h)+~O(h\cdot \log(h))=~O(h)\cdot ({~O(\log(h))+1}))}$.

• R-дерево
• VP-дерево^[en]
• Пошук найближчого сусіда
• Перший засік ліпший

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