www.wikidata.uk-ua.nina.az

k вимірне дерево В інформатиці k d дерево англ k d tree скорочення від це структура даних з поділом простору для упорядк

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

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

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

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

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

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

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

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

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

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

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

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

  • Видалення листа дерева — досить просте видалення, коли видаляється один вузол, і покажчик вузла-предка просто обнуляється.
  • Видалення вузла дерева (не листа) — дуже складна процедура, при якій доводиться перебудовувати все піддерево для даного вузла.

Іноді процес видалення вузла вирішується модифікаціями k-d дерева. Наприклад, якщо у нас у вузлі міститься масив елементів, то при видаленні всього масиву вузол дерева залишається, але нові елементи туди більше не записуються.

Пошук діапазону елементів ред.

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


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 дерева в двох масивах

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

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

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. 

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

  • , an open-source STL-like implementation of k — d trees in C ++.
  • 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
  • : 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
  • contains open source implementations of exact and approximate (k) NN search methods using k  — d trees in C ++.


Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V informatici k d derevo angl k d tree skorochennya vid k vimirne derevo ce struktura danih z podilom prostoru dlya uporyadkuvannya tochok v k vimirnomu prostori K d dereva vikoristovuyutsya dlya deyakih zastosuvan takih yak poshuk u bagatovimirnomu prostori klyuchiv poshuk diapazoniv en i poshuk najblizhchogo susida K d dereva osoblivij vid derev dvijkovogo podilu prostoru Trivimirne k d derevo Zmist 1 Matematichnij opis 2 Operaciyi z k d derevami 2 1 Struktura 2 2 Dodavannya elementiv 2 3 Vidalennya elementiv 2 4 Poshuk diapazonu elementiv 2 5 Poshuk najblizhchogo susida 3 Div takozh 4 Posilannya 5 Zovnishni posilannyaMatematichnij opis red K vimirne derevo ce nezbalansovane derevo poshuku dlya zberigannya tochok z R k displaystyle mathbb R k nbsp Vono proponuye shozhu na R derevo mozhlivist poshuku v zadanomu diapazoni klyuchiv Na shkodu prostoti zapitiv vimogi do pam yati O k n displaystyle O kn nbsp zamist O log n k 1 displaystyle O log n k 1 nbsp Isnuyut odnoridni j neodnoridni k d dereva V odnoridnih k d derev kozhen vuzol zberigaye zapis Pri neodnoridnomu varianti vnutrishni vuzli mistyat tilki klyuchi listya mistit posilannya na zapisi U neodnoridnomu k d derevi H i t x 1 x 2 x i 1 t x i 1 x k displaystyle H i t x 1 x 2 ldots x i 1 t x i 1 ldots x k nbsp pri 1 i k displaystyle 1 leq i leq k nbsp paralelno osi k 1 displaystyle k 1 nbsp mirnoyi giperploshini v tochci t displaystyle t nbsp Dlya korenya potribno rozdiliti tochki cherez giperploshinu H 1 t displaystyle H 1 t nbsp na dvi po mozhlivosti odnakovo veliki bezlichi tochok i zapisati t displaystyle t nbsp v korin livoruch vid cogo zberigayutsya vsi tochki u yakih x 1 lt t displaystyle x 1 lt t nbsp pravoruch ti u yakih x 1 gt t displaystyle x 1 gt t nbsp Dlya livogo piddereva potribno rozdiliti tochki znovu na novu rozdilenu ploshinu H 2 t displaystyle H 2 t nbsp a t displaystyle t nbsp zberigayetsya u vnutrishnomu vuzli Zliva vid cogo zberigayutsya vsi tochki u yakih x 2 lt t displaystyle x 2 lt t nbsp Ce trivaye rekursivno nad usima prostorami Potim vse pochinayetsya znovu z pershogo prostoru doki kozhnu tochku mozhna bude yasno identifikuvati cherez giperploshinu K d derevo mozhna pobuduvati za O n k log n displaystyle O n k log n nbsp Poshuk diapazonu mozhna vikonati za O n 1 1 k a displaystyle O n 1 frac 1 k a nbsp pri comu a displaystyle a nbsp poznachaye rozmir vidpovidi Vimogu do pam yati dlya samogo dereva obmezheno O k n displaystyle O kn nbsp 1 Operaciyi z k d derevami red Struktura red Struktura dereva opisana na movi C const N 10 Kilkist prostoriv klyuchiv struct Item struktura elementa int key N Masiv klyuchiv viznachaye element char info Informaciya elementa struct Node struktura vuzla dereva Item i Element Node left Live pidderevo Node right Prave pidderevo Struktura dereva mozhe zminyuvatis v zalezhnosti vid detalej realizaciyi algoritmu Napriklad u vuzli mozhe mistitisya ne odin element a masiv sho pidvishuye efektivnist poshuku Analiz poshuku elementaOchevidno sho minimalna kilkist pereglyanutih elementiv dorivnyuye 1 displaystyle 1 nbsp a maksimalna kilkist pereglyanutih elementiv O h displaystyle O h nbsp de h displaystyle h nbsp ce visota dereva Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv A n displaystyle A n nbsp x 0 x 1 x 2 x n displaystyle x 0 x 1 x 2 x n nbsp zadanij element Rozglyanemo vipadok h 3 displaystyle h 3 nbsp Znajdenimi elementami mozhut buti f i n d t 1 x 0 t 1 A 1 displaystyle find t 1 x 0 t 1 A 1 nbsp f i n d t 2 x 0 lt t 1 x 0 t 2 A 2 displaystyle find t 2 x 0 lt t 1 land x 0 t 2 A 2 nbsp f i n d t 3 x 0 gt t 1 x 0 t 3 A 2 displaystyle find t 3 x 0 gt t 1 land x 0 t 3 A 2 nbsp f i n d t 4 x 0 lt t 1 x 0 lt t 2 x 0 t 4 A 3 displaystyle find t 4 x 0 lt t 1 land x 0 lt t 2 land x 0 t 4 A 3 nbsp f i n d t 5 x 0 lt X 1 x 0 gt t 2 x 0 t 5 A 3 displaystyle find t 5 x 0 lt X 1 land x 0 gt t 2 land x 0 t 5 A 3 nbsp f i n d t 6 x 0 lt t 1 x 0 lt t 3 x 0 t 6 A 3 displaystyle find t 6 x 0 lt t 1 land x 0 lt t 3 land x 0 t 6 A 3 nbsp f i n d t 7 x 0 lt t 1 x 0 gt t 3 x 0 t 7 A 3 displaystyle find t 7 x 0 lt t 1 land x 0 gt t 3 land x 0 t 7 A 3 nbsp i tak dlya kozhnogo prostoru klyuchiv Pri comu serednya dovzhina poshuku v odnomu prostori stanovit A 1 2 2 3 3 3 3 7 17 7 2 4 displaystyle A frac 1 2 2 3 3 3 3 7 frac 17 7 approx 2 4 nbsp Serednya velichina rozrahovuyetsya za formuloyu A n k 1 n k p n k displaystyle A n sum k 1 n kp n k nbsp Zalishayetsya znajti jmovirnist p n k displaystyle p n k nbsp Vona dorivnyuye p n k p A k p n displaystyle p n k frac p A k p n nbsp de p A k displaystyle p A k nbsp chislo vipadkiv koli A k displaystyle A k nbsp i p n displaystyle p n nbsp zagalne chislo vipadkiv Ne skladno zdogadatis sho p n k 2 k 1 2 n 1 displaystyle p n k frac 2 k 1 2 n 1 nbsp Pidstavlyayemo ce v formulu dlya serednoyi velichini A n k 1 n k p n k k 1 n k 2 k 1 2 n 1 1 2 n 1 k 1 n k 2 k 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 nbsp 1 2 n 1 k 1 1 n k 1 2 k 1 2 n 1 k 1 1 n k 2 k k 1 1 n 2 k 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 nbsp 1 2 n 1 k 1 n k 2 k k 1 n 2 k 2 n n 2 n displaystyle frac 1 2 n 1 left sum k 1 n k2 k sum k 1 n 2 k 2 n n2 n right nbsp 1 2 n 1 n 2 n 2 n 1 2 n 1 2 2 n 2 3 1 n 2 n 2 n n 1 1 2 n 1 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 nbsp tobto A h 2 h h 1 1 2 h 1 displaystyle A h frac 2 h h 1 1 2 h 1 nbsp de h displaystyle h nbsp visota dereva Yaksho perejti vid visoti dereva do kilkosti elementiv to A n O 2 h h 1 1 2 h 1 O h 2 h 2 h 1 1 O log n N 1 2 log n N 1 2 log n N 1 1 1 O log n N 1 n N n 1 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 nbsp O log n N 1 n N n 1 displaystyle O left log left frac n N 1 right frac n N n 1 right nbsp de N displaystyle N nbsp kilkist elementiv u vuzli Z cogo mozhna zrobiti visnovok sho chim bilshe elementiv bude mistitis u vuzli tim shvidshe bude prohoditi poshuk po derevu oskilki visota dereva zalishatimetsya minimalnoyu prote ne slid zberigati velicheznu kilkist elementiv u vuzli oskilki pri takomu sposobi vse derevo mozhe degeneruvati u zvichajnij masiv abo spisok Dodavannya elementiv red Dodavannya elementiv vidbuvayetsya tochno tak samo yak i v zvichajnomu dvijkovomu derevi poshuku z tiyeyu lishe rizniceyu sho kozhen riven dereva bude viznachatisya she j prostorom do yakogo vin vidnositsya Algoritm prosuvannya po derevu for int i 0 tree i i ce nomer prostoru if tree gt x i lt tree gt t t mediana tree tree gt left Perehodimo v live pidderevo else tree tree gt right Perehodimo v prave pidderevo Dodavannya vikonuyetsya za O h displaystyle O h nbsp de h displaystyle h nbsp visota dereva Vidalennya elementiv red Pri vidalenni elementiv dereva mozhe viniknuti dekilka situacij Vidalennya lista dereva dosit proste vidalennya koli vidalyayetsya odin vuzol i pokazhchik vuzla predka prosto obnulyayetsya 2 Vidalennya vuzla dereva ne lista duzhe skladna procedura pri yakij dovoditsya perebudovuvati vse pidderevo dlya danogo vuzla Inodi proces vidalennya vuzla virishuyetsya modifikaciyami k d dereva Napriklad yaksho u nas u vuzli mistitsya masiv elementiv to pri vidalenni vsogo masivu vuzol dereva zalishayetsya ale novi elementi tudi bilshe ne zapisuyutsya Poshuk diapazonu elementiv red Poshuk zasnovanij na zvichajnomu spusku po derevu koli kozhen vuzol pereviryayetsya na diapazon Yaksho mediani vuzla menshe abo bilshe zadanogo diapazonu v danomu prostori to obhid jde dali po odnij z gilok dereva Yaksho zh mediana vuzla vhodit povnistyu v zadanij diapazon to potribno vidvidati obidva piddereva 3 AlgoritmZ vuzol dereva X 0 min x 1 min x 2 min x n min x 0 max x 1 max x 2 max x n max zadanij diapazon Funkciya Array Node amp Z If x 0 min x 1 min x 2 min x n min lt Z Z Z gt left Live pidderevo else If x 0 max x 1 max x 2 max x n max gt Z Z Z gt right Prave pidderevo Else pereglyanuti obidva piddereva Array Z gt right Zapustiti funkciyu dlya pravogo piddereva Z Z gt left Pereglyanuti live pidderevo AnalizOchevidno sho minimalna kilkist pereglyanutih elementiv ce O h displaystyle O h nbsp de h displaystyle h nbsp visota dereva Tak samo ochevidno sho maksimalna kilkist pereglyanutih elementiv ce O 2 h 1 displaystyle O 2 h 1 nbsp tobto pereglyad vsih elementiv dereva Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv A n displaystyle A n nbsp x 0 m i n x 1 m i n x 2 m i n x n m i n x 0 m a x x 1 m a x x 2 m a x x n m a x 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 nbsp zadanij diapazon Originalna stattya pro k d dereva daye taku harakteristiku A n O h log h displaystyle A n O h cdot log h nbsp dlya fiksovanogo diapazonu Yaksho perejti vid visoti dereva do kilkosti elementiv to ce bude A n O log log n 1 log n 1 displaystyle A n O log log n 1 log n 1 nbsp Poshuk najblizhchogo susida red Poshuk najblizhchogo elementa rozdilyayetsya na dvi pidzadachi 1 viznachennya mozhlivogo najblizhchogo elementa 2 poshuk najblizhchih elementiv v zadanomu diapazoni nbsp Animaciya NN poshuka s a k d dereva v dvoh masivahDano derevo t r e e displaystyle tree nbsp Mi spuskayemosya po derevu do jogo lista za umovoyu t r e e x i lt gt t r e e t displaystyle tree to x i lt gt tree to t nbsp i viznachayemo jmovirnij najblizhchij element za umovoyu l m i n x 0 x i 0 2 x 1 x i 1 2 x n x i n 2 displaystyle l min sqrt x 0 x i 0 2 x 1 x i 1 2 x n x i n 2 nbsp Pislya cogo vid korenya dereva zapuskayetsya algoritm poshuku najblizhchogo elementa v zadanomu diapazoni yakij viznachayetsya radiusom R l m i n 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 nbsp Radius poshuku koriguyetsya pri znahodzhenni najblizhchogo elementa 4 AlgoritmZ korin dereva List spisok najblizhchih elementiv X 0 x 1 x 2 x n element dlya yakogo shukayutsya najblizhchi Len minimalna dovzhina Funkciya Maybe Near Node amp Z poshuk najblizhchogo mozhlivogo elementa While Z Perevirka elementiv u vuzli for i 0 i lt N i len cur sqrt x 0 x i 0 2 x 1 x i 1 2 x n x i n 2 Dovzhina potochnogo elementa if Len gt dovzhini potochnogo elementa Len len cur Vstanovlennya novoyi dovzhini Delete List Ochishennya spisku Add List Dodati novij element u spisok Else if dovzhini rivni Add List Dodati novij element u spisok If x 0 x i 0 amp amp x 1 x i 1 amp amp amp amp x n x i n Return 1 If x 0 x 1 x 2 x n lt Z Z Z gt left Live pidderevo If x 0 x 1 x 2 x n gt Z Z Z gt right Prave pidderevo Funkciya Near Node amp Z poshuk najblizhchogo elementa v zadanomu diapazoni While Z Perevirka elementiv u vuzli for i 0 i lt N i len cur sqrt x 0 x i 0 2 x 1 x i 1 2 x n x i n 2 Dovzhina potochnogo elementa if Len gt dovzhini potochnogo elementa Len len cur Vstanovlennya novoyi dovzhini Delete List Ochistka spisku Add List Dodati novij element u spisok Else if dovzhini rivni Add List Dodati novij element u spisok If x 0 x 1 x 2 x n len gt Z yaksho diapazon bilshe mediani Near Z gt right Pereglyanuti obidva dereva Z Z gt left If x 0 x 1 x 2 x n lt Z Z Z gt left Live pidderevo If x 0 x 1 x 2 x n gt Z Z Z gt right Prave pidderevo AnalizOchevidno sho minimalna kilkist pereglyanutih elementiv ce O h displaystyle O h nbsp de h visota dereva Tak samo ochevidno sho maksimalna kilkist pereglyanutih elementiv ce O 2 h 1 displaystyle O 2 h 1 nbsp tobto pereglyad vsih vuzliv Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv x 0 x 1 x 2 x n displaystyle x 0 x 1 x 2 x n nbsp zadanij element shodo yakogo potribno znajti najblizhchij Ce zavdannya rozdilyayetsya na dvi pidzadachi znahodzhennya najblizhchogo elementa u vuzli j znahodzhennya najblizhchogo elementa v zadanomu diapazoni Dlya virishennya pershoyi pidzadachi potriben odin spusk po derevu tobto O h displaystyle O h nbsp Dlya drugoyi pidzadachi yak mi vzhe virahuvali poshuk elementiv v zadanomu diapazoni vikonuyetsya za O h log h displaystyle O h cdot log h nbsp Shob diznatisya serednye dosit prosto sklasti ci dvi velichini O h O h log h O h O log h 1 displaystyle O h O h cdot log h O h cdot O log h 1 nbsp Div takozh red R derevo VP derevo en Poshuk najblizhchogo susida Pershij zasik lipshijPosilannya red 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 Arhivovano 23 veresnya 2015 u 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 Zovnishni posilannya red libkdtree an open source STL like implementation of k d trees in C A tutorial on KD Trees FLANN and its fork nanoflann Arhivovano 28 grudnya 2014 u Wayback Machine efficient C implementations of k d tree algorithms kdtree Arhivovano 9 sichnya 2015 u Wayback Machine A simple C library for working with KD Trees KD Tree Demo Java applet Arhivovano 29 chervnya 2020 u Wayback Machine libANN Arhivovano 15 sichnya 2021 u 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 Arhivovano 11 listopada 2016 u 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 Otrimano z https uk wikipedia org w index php title K vimirne derevo amp oldid 38113141