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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Тривимірне 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. 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. 

Зовнішні посилання[ред.ред. код]