В інформатиці k-d дерево (англ. k-d tree, скорочення від k-вимірне дерево) — це структура даних з поділом простору для упорядкування точок в k-вимірному просторі. K-d дерева використовуються для деяких застосувань, таких як пошук у багатовимірному просторі ключів ([en] і пошук найближчого сусіда). 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) пошук найближчих елементів в заданому діапазоні.
Дано дерево . Ми спускаємося по дереву до його листа за умовою і визначаємо ймовірний найближчий елемент за умовою . Після цього від кореня дерева запускається алгоритм пошуку найближчого елемента в заданому діапазоні, який визначається радіусом .
Радіус пошуку коригується при знаходженні найближчого елемента.
- Алгоритм
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 — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це , тобто перегляд всіх вузлів. Залишається порахувати середню кількість переглянутих елементів.
— заданий елемент, щодо якого потрібно знайти найближчий. Це завдання розділяється на дві підзадачі: знаходження найближчого елемента у вузлі й знаходження найближчого елемента в заданому діапазоні. Для вирішення першої підзадачі потрібен один спуск по дереву, тобто .
Для другої підзадачі, як ми вже вирахували, пошук елементів в заданому діапазоні виконується за . Щоб дізнатися середнє, досить просто скласти ці дві величини:
.
Див. також
Посилання
- (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.
- ; ; Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. . 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, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
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 en i poshuk najblizhchogo susida K d dereva osoblivij vid derev dvijkovogo podilu prostoru Trivimirne k d derevo Matematichnij opisK vimirne derevo ce nezbalansovane derevo poshuku dlya zberigannya tochok z Rk displaystyle mathbb R k Vono proponuye shozhu na R derevo mozhlivist poshuku v zadanomu diapazoni klyuchiv Na shkodu prostoti zapitiv vimogi do pam yati O kn displaystyle O kn zamist O log n k 1 displaystyle O log n k 1 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 Hi t x1 x2 xi 1 t xi 1 xk displaystyle H i t x 1 x 2 ldots x i 1 t x i 1 ldots x k pri 1 i k displaystyle 1 leq i leq k paralelno osi k 1 displaystyle k 1 mirnoyi giperploshini v tochci t displaystyle t Dlya korenya potribno rozdiliti tochki cherez giperploshinu H1 t displaystyle H 1 t na dvi po mozhlivosti odnakovo veliki bezlichi tochok i zapisati t displaystyle t v korin livoruch vid cogo zberigayutsya vsi tochki u yakih x1 lt t displaystyle x 1 lt t pravoruch ti u yakih x1 gt t displaystyle x 1 gt t Dlya livogo piddereva potribno rozdiliti tochki znovu na novu rozdilenu ploshinu H2 t displaystyle H 2 t a t displaystyle t zberigayetsya u vnutrishnomu vuzli Zliva vid cogo zberigayutsya vsi tochki u yakih x2 lt t displaystyle x 2 lt t 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 Poshuk diapazonu mozhna vikonati za O n1 1k a displaystyle O n 1 frac 1 k a pri comu a displaystyle a poznachaye rozmir vidpovidi Vimogu do pam yati dlya samogo dereva obmezheno O kn displaystyle O kn Operaciyi z k d derevamiStruktura 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 elementa Ochevidno sho minimalna kilkist pereglyanutih elementiv dorivnyuye 1 displaystyle 1 a maksimalna kilkist pereglyanutih elementiv O h displaystyle O h de h displaystyle h ce visota dereva Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv An displaystyle A n x0 x1 x2 xn displaystyle x 0 x 1 x 2 x n zadanij element Rozglyanemo vipadok h 3 displaystyle h 3 Znajdenimi elementami mozhut buti find t1 x0 t1 A 1 displaystyle find t 1 x 0 t 1 A 1 find t2 x0 lt t1 x0 t2 A 2 displaystyle find t 2 x 0 lt t 1 land x 0 t 2 A 2 find t3 x0 gt t1 x0 t3 A 2 displaystyle find t 3 x 0 gt t 1 land x 0 t 3 A 2 find t4 x0 lt t1 x0 lt t2 x0 t4 A 3 displaystyle find t 4 x 0 lt t 1 land x 0 lt t 2 land x 0 t 4 A 3 find t5 x0 lt X1 x0 gt t2 x0 t5 A 3 displaystyle find t 5 x 0 lt X 1 land x 0 gt t 2 land x 0 t 5 A 3 find t6 x0 lt t1 x0 lt t3 x0 t6 A 3 displaystyle find t 6 x 0 lt t 1 land x 0 lt t 3 land x 0 t 6 A 3 find t7 x0 lt t1 x0 gt t3 x0 t7 A 3 displaystyle find t 7 x 0 lt t 1 land x 0 gt t 3 land x 0 t 7 A 3 i tak dlya kozhnogo prostoru klyuchiv Pri comu serednya dovzhina poshuku v odnomu prostori stanovit A 1 2 2 3 3 3 37 177 2 4 displaystyle A frac 1 2 2 3 3 3 3 7 frac 17 7 approx 2 4 Serednya velichina rozrahovuyetsya za formuloyu An k 1nkpn k displaystyle A n sum k 1 n kp n k Zalishayetsya znajti jmovirnist pn k displaystyle p n k Vona dorivnyuye pn k pA kpn displaystyle p n k frac p A k p n de pA k displaystyle p A k chislo vipadkiv koli A k displaystyle A k i pn displaystyle p n zagalne chislo vipadkiv Ne skladno zdogadatis sho pn k 2k 12n 1 displaystyle p n k frac 2 k 1 2 n 1 Pidstavlyayemo ce v formulu dlya serednoyi velichini An k 1nkpn k k 1nk2k 12n 1 12n 1 k 1nk2k 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 12n 1 k 1 1n k 1 2k 12n 1 k 1 1nk2k k 1 1n2k 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 12n 1 k 1nk2k k 1n2k 2n n2n displaystyle frac 1 2 n 1 left sum k 1 n k2 k sum k 1 n 2 k 2 n n2 n right 12n 1 n2n 2 n 1 2n 1 2 2n 23 1 n2n 2n n 1 12n 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 tobto Ah 2h h 1 12h 1 displaystyle A h frac 2 h h 1 1 2 h 1 de h displaystyle h visota dereva Yaksho perejti vid visoti dereva do kilkosti elementiv to An O 2h h 1 12h 1 O h2h2h 1 1 O log nN 1 2log nN 1 2log nN 1 1 1 O log nN 1 n Nn 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 O log nN 1 n Nn 1 displaystyle O left log left frac n N 1 right frac n N n 1 right de N displaystyle N 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 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 de h displaystyle h visota dereva Vidalennya elementiv Pri vidalenni elementiv dereva mozhe viniknuti dekilka situacij Vidalennya lista dereva dosit proste vidalennya koli vidalyayetsya odin vuzol i pokazhchik vuzla predka prosto obnulyayetsya 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 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 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 Analiz Ochevidno sho minimalna kilkist pereglyanutih elementiv ce O h displaystyle O h de h displaystyle h visota dereva Tak samo ochevidno sho maksimalna kilkist pereglyanutih elementiv ce O 2h 1 displaystyle O 2 h 1 tobto pereglyad vsih elementiv dereva Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv An displaystyle A n x0min x1min x2min xnmin x0max x1max x2max xnmax 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 zadanij diapazon Originalna stattya pro k d dereva daye taku harakteristiku An O h log h displaystyle A n O h cdot log h dlya fiksovanogo diapazonu Yaksho perejti vid visoti dereva do kilkosti elementiv to ce bude An O log log n 1 log n 1 displaystyle A n O log log n 1 log n 1 Poshuk najblizhchogo susida Poshuk najblizhchogo elementa rozdilyayetsya na dvi pidzadachi 1 viznachennya mozhlivogo najblizhchogo elementa 2 poshuk najblizhchih elementiv v zadanomu diapazoni Animaciya NN poshuka s a k d dereva v dvoh masivah Dano derevo tree displaystyle tree Mi spuskayemosya po derevu do jogo lista za umovoyu tree x i lt gt tree t displaystyle tree to x i lt gt tree to t i viznachayemo jmovirnij najblizhchij element za umovoyu lmin x0 x i 0 2 x1 x i 1 2 xn 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 Pislya cogo vid korenya dereva zapuskayetsya algoritm poshuku najblizhchogo elementa v zadanomu diapazoni yakij viznachayetsya radiusom R lmin x0 x i 0 2 x1 x i 1 2 xn 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 Radius poshuku koriguyetsya pri znahodzhenni najblizhchogo elementa 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 Analiz Ochevidno sho minimalna kilkist pereglyanutih elementiv ce O h displaystyle O h de h visota dereva Tak samo ochevidno sho maksimalna kilkist pereglyanutih elementiv ce O 2h 1 displaystyle O 2 h 1 tobto pereglyad vsih vuzliv Zalishayetsya porahuvati serednyu kilkist pereglyanutih elementiv x0 x1 x2 xn displaystyle x 0 x 1 x 2 x n 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 Dlya drugoyi pidzadachi yak mi vzhe virahuvali poshuk elementiv v zadanomu diapazoni vikonuyetsya za O h log h displaystyle O h cdot log h 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 Div takozhR derevo en Poshuk najblizhchogo susida Pershij zasik lipshijPosilannya 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 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 Finkel R A 1977 An Algorithm for Finding Best Matches in Logarithmic Expected Time 3 3 209 doi 10 1145 355744 355745 Zovnishni posilannya an open source STL like implementation of k d trees in C and its fork nanoflann 28 grudnya 2014 u Wayback Machine efficient C implementations of k d tree algorithms kdtree 9 sichnya 2015 u Wayback Machine A simple C library for working with KD Trees KD Tree Demo Java applet 29 chervnya 2020 u Wayback Machine libANN 15 sichnya 2021 u 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 listopada 2016 u Wayback Machine pp 11 and after contains open source implementations of exact and approximate k NN search methods using k d trees in C