К-D стабло

К-D стабло (скраценица за К-димензионо стабло) у информатици представља структуру података која дели простор и организује тацке у К-димензионом простору. К-D стабла су веома корисна структура података за многе апликације, као сто су претраживања која укљуцују вижедимензиону претрагу кључева (нпр. опсег претраживања и најближи сусед претраге). К-D стабло је посебна врста бинарног стабла.

Неформални опис уреди

К-D стабло је бинарно стабло у коме је сваки чвор К-димензионална тачка. Сваки не лист чвор може да се посматра као имплицитно генерисана подела хиперравни која дели простор на два дела, позната као полу-простор. Тачке са леве стране ове хиперравни престављају лево подстабло, а тачке са десне, десно подстабло К-D стабла. Правац хиперравни је изабран на следеци нацин: сваки чвор у стаблу је повезан са једном од К димензија, са хеперравни која је нормална на осу те димензије. Тако, на пример, ако је за одређену поделу узета оса "x", у левом подстаблу ће се налазити чворови са мањом вредношћу "x", а у десном подстаблу чворови са већом вредношћу "x". У том случају, хиперраван це бити постављана од стране x-вредности тачке, а њена нормала це бити x-оса.^[1]

Операције над К-D стаблом уреди

Конструкција уреди

Постоји много различитих начина на који се може направити К-D стабло. Канонски начин конструисања К-D стабла има следећа ограничења:

Како се крећемо низ дрво, једна петља се користи за одређивање равни. (Нпр. У тродимензионалном стаблу, корен ће имати раван поравнату по x-оси, његова деца це имати раван поравнату по y-оси, унуци ће имати раван поравнату по з-оси, пра-унуци ће имати раван поравнату по x-оси, пра-пра-унуци по y-оси и тако даље).
Чворови се убацују у стабло избором тачке средње вредности за корен, и затим се тачке убацују у лево, односно десно подстабло, узимајући у обзир њихове вредности. (Треба имати на уму претпоставку да треба сместити н тачака у алгоритму унапред.)

Овај метод доводи до стварања балансираног К-D стабла, у ком је сваки лист на истом растојању од корена. Међутим, избалансирано стабло не мора бити оптимално за све апликације.

Треба имати на уму да није потребно изабрати средњу тачку. У том случају нема гаранције да це резултат бити балансирано стабло. Најчешће се користи једноставан алгоритам сортирања (О(н логн)) ради налажења тачке са средњом вредности која ће служити за дељење равни. У пракси, ова техника често доводи до стварања лепо избалансираног стабла.

Следећи алгоритам користи одређивање тачке средње вредности за прављење балансираног К-D стабла. Као улаз прима листу од н тачака које би требало да се налазе у стаблу.

function kdtree (list of points pointList, int depth)
{
    // Odabir ose zasnovan na dubini, tako da osa prolazi kroz sve validne vrednosti 
    var int axis := depth mod k;
        
    //  Sortiranje tačaka i odabir medijana kao pivot element
    select median by axis from pointList;
        
    // Kreiranje čvora i konstrukcija podstabla
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

Додавање чворова уреди

Додавање нових елеманата у К-D стабло је идентично као и додавање елемената у било које друго стабло претраге. Прво се креће од корена и у зависности од тога да ли се тачка налази у левој и десној полуравни, кретање се обавља у лево, односно десно подстабло. Када се стигне до чвора ком би требало додати нови чвор као дете, поново у зависности од тога да ли је чвор у левој или десној полуравни, додаје се нови лист.

Додавање чворова на овакав нацин мозе да доведе до стварања неизбалансираног стабла, што доводи до смањења перформанси стабла. Брзина деградације перформанси стабла зависи од просторног распореда додатих чворова стабла, и броја додатих чворова у односу на величину стабла. Ако стабло постане превише неуравнотежено, онда је неопхотно урадити поновно уравнотеживање стабла како би се повратиле перформансе стабла за одређене операције, као сто је тражење најближег суседа.

Брисање чворова уреди

Да би се постојеци чвор уклонио из К-D дрвета, без разбијања инваријанти, најлакши начин је да се формира скуп свих чворова и листова циљаног чвора, и поново направити само дај део стабла.

Други приступ је налажење замене за цвор који треба уклонити^[2]. Прво се нађе чвор П који треба избрисати. У базном слуцају, ако је чвор П лист, не тражи се замена, вец се чвор директно брисе из стабла. У општем случају, налази се чвор замена (нпр. чвор Р) из подстабла ком је корен чвор П. Врси се замена Р и П, и затим се рекузивно брише чвор Р.

За тачку замене се најчешће узима или чвор са најмањом вредности из десног подстабла или чвор са највецом вредности из левог подстабла.

Балансирање К-D стабла уреди

Балансирање К-D стабла захтева пажњу јер су чворови сортирани у више димензија, тако да се ротација дрвета не може користити за балансирање, јер може изазвати пуцање инваријанте.

Постоји неколико начина балансирања К-D стабла. Она укључују подељено К-D стабло, псеудо К-D стабло, КДБ стабло, хБ стабло и БКД стабло. Многи од ових начина су адаптација К-D стабла.

Тражење најближег комшије уреди

Анимација претраге најближег комшије код К-D стабла са две димензије

Алгоритам тражења најближег комшије има за циљ да пронађе чвор у дрвету који је најближи датом чвору. Ова претрага се може ефикасно урадити уз помоћ особине стабла да брзо елиминише велике делове простора за претрагу.

Алгоритам се обавља на следећи начин:

Почевши од корена, алгоритам се помера на доле у стаблу рекурзивно, на исти начин као код претраге током уноса новог чвора у стабло (тј. иде се у лево или десно подстабло у зависности од тога да ли је вредност мања или већа у односу на тренутни чвор).
Када алгоритам достигне лист, памти тај лист као "тренутни најбољи".
Алгоритам се рекурзивно враћа кроз стабло извршавајући следеће кораке на сваком чвору:

1. Ако је тренутни чвор ближи задатом чвору од "тренутног најбољег", он постаје "тренутни најбољи".
2. Затим алгоритам проверава да ли постоји чвор ближи траженом чвору тако што формира сферу (полупречника једноког удаљености траженог чвора од тренутног чвора) око тренутног чвора. Ако постоји тачка у тој сфери, онда она постаје "тренутна најбоља".
Када се алгоритам заврши за корени чвор, процес претраге је готов.

Генерално овај алгоритам користи квадрат растојања за поређење, да би се избегло рачунање квадратног корена. Поред тога, може да се уштеди и чувајући квадратно растојање "тренутног најбољег", које се користи за поређење.

Проналажење најближег чвора има О(лог Н) операција у случају случајно распоређених тачака. Међутим тврди се да алгоритам даје сложеност О(лог Н) у било ком случају.^[3]

Опсег претраге уреди

Анализа бинарног стабла претраге је утврдила да је најгори случај времена опсега претраге у К-D стаблу које садржи Н чворова дат следећом једночином:^[4]

t_{najgore}=O(k\cdot N^{1-{\frac {1}{k}}})

Вишедимензионални подаци уреди

К-D стабло није погодно за ефикасно тражење најближег суседа у простору са много димензија. По правилу, уколико је простор К-димензионалан, а број чворова у стаблу Н, требало би да буде Н >> 2^к.

Сложеност уреди

Конструкција статичког К-D стабла са Н чворова је сложености:
- О(н лог² н), ако се користи алгоритам као што је Хип сорт, сложености О(н лог н), за тражење медијана.
- О(н лог н), ако се користи алгоритам линеарне сложености.
- О(кн лог н) + О([к-1]н лог н), ако је Н чворова слоритрано у К димензија применом алгоритма слозености О(н лог н) током изградње К-D стабла.
Убацивање новог чвора у балансирано стабло: О(лог н).
Брисање чвора из балансираног стабла: О(н лог н).
Тражење најближег комшије у балансираном стаблу, са случајно распоређеним чворовима: у просеку О(н лог н).

Извори уреди

^ Бентлеy, Јон Лоуис (1975). „Мултидименсионал бинарy сеарцх треес усед фор ассоциативе сеарцхинг”. Цоммуницатионс оф тхе АЦМ. 18 (9): 509—517. С2ЦИД 13091446. дои:10.1145/361002.361007.
^ Цхандран, Схарат. Интродуцтион то кд-треес Архивирано на сајту Wayback Machine (23. септембар 2015). University of Maryland Department of Computer Science.
^ Friedman, Jerome H., Bentley, Jon Louis, Finkel, Raphael Ari (1977). „An Algorithm for Finding Best Matches in Logarithmic Expected Time”. ACM Trans. Math. Softw. ACM. 3 (3): 209—226. ISSN 0098-3500. OSTI 1443274. S2CID 10811510. doi:10.1145/355744.355745. Приступљено 29 March, 2013. Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)
^ 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 (1): 23—29. S2CID 36580055. doi:10.1007/BF00263763.

Види још уреди

[1] Бентлеy, Јон Лоуис (1975). „Мултидименсионал бинарy сеарцх треес усед фор ассоциативе сеарцхинг”. Цоммуницатионс оф тхе АЦМ. 18 (9): 509—517. С2ЦИД 13091446. дои:10.1145/361002.361007.

[2] Цхандран, Схарат. Интродуцтион то кд-треес Архивирано на сајту Wayback Machine (23. септембар 2015). University of Maryland Department of Computer Science.

[Friedman:1977:AFB:355744.355745-3] Friedman, Jerome H., Bentley, Jon Louis, Finkel, Raphael Ari (1977). „An Algorithm for Finding Best Matches in Logarithmic Expected Time”. ACM Trans. Math. Softw. ACM. 3 (3): 209—226. ISSN 0098-3500. OSTI 1443274. S2CID 10811510. doi:10.1145/355744.355745. Приступљено 29 March, 2013. Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)

[Lee1977-4] 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 (1): 23—29. S2CID 36580055. doi:10.1007/BF00263763.

[1]

[2]

[3]

[4]