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

Тривимірне k-d дерево.

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

Математичний опис

[ред. | ред. код]

K-вимірне дерево — це незбалансоване дерево пошуку для зберігання точок з . Воно пропонує схожу на R-дерево можливість пошуку в заданому діапазоні ключів. На шкоду простоті запитів, вимоги до пам'яті замість .

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

У неоднорідному k-d дереві при паралельно осі -мірної гіперплощини в точці . Для кореня потрібно розділити точки через гіперплощину на дві по можливості однаково великі безлічі точок і записати в корінь, ліворуч від цього зберігаються всі точки, у яких , праворуч ті, у яких . Для лівого піддерева потрібно розділити точки знову на нову «розділену площину» , а зберігається у внутрішньому вузлі. Зліва від цього зберігаються всі точки, у яких . Це триває рекурсивно над усіма просторами. Потім все починається знову з першого простору, доки кожну точку можна буде ясно ідентифікувати через гіперплощину.

K-d дерево можна побудувати за . Пошук діапазону можна виконати за , при цьому позначає розмір відповіді. Вимогу до пам'яті для самого дерева обмежено . [1]

Операції з 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; // Переходимо в праве піддерево 

Додавання виконується за , де  — висота дерева.

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

[ред. | ред. код]

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

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

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

 — заданий діапазон.

Оригінальна стаття про k-d дерева дає таку характеристику: для фіксованого діапазону.

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

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

[ред. | ред. код]

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

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

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

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

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

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

Очевидно, що мінімальна кількість переглянутих елементів це , де 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.
  2. Chandran, Sharat. Introduction to kd-trees [Архівовано 23 вересня 2015 у Wayback Machine.]. University of Maryland Department of Computer Science.
  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.
  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.

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

[ред. | ред. код]