Пређи на садржај

Декартово дрво

С Википедије, слободне енциклопедије
Декартово дрво
ТипРандомизовано стабло бинарне претраге
Временска комплексност у великој О нотацији
Алгоритам Просек Најгори случај
Простор О(н) О(н)
Претрага О(лог н) О(н)
Уметање О(лог н) О(н)
Брисање О(лог н) О(н)

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

Опис

[уреди | уреди извор]
Декартово дрво са абецедним кључевима и бројчано максималним хип редоследом

Декартово дрво су први пут описали Цецилија Арагон и Рејмонд Сидел 1989. године.[1][2] То је Картезијанско стабло[3] у којем је сваком кључу дат (насумично изабран) бројчани приоритет. Као и код свих бинарно претрачивацких стабала, редослед обиласка чворова је исти као и сортирани поредак кључева. Структура стабла је одређена захтевом да оно има уређен хип: тј. приоритетни број за било којег чвора који није лист мора бити већи или једнак приоритетним бројевима његових потомака. Стога, као што је то генерално случај код Картезијанских стабала, коренски чвор има максимални приоритет, а њено лево и десно потстабло се формирају на исти начин из подсеквенци са сортираним редоследом лево и десно од тог чвора.

Еквивалентан начин описивања Декартовог дрвета је да оно може бити формирано уметањем чворова следећи опадајући редослед приоритета у бинарно претраживачко дрво без икаквог уравнотежавања. Дакле, уколико су приоритети независни случајни бројеви (из дистрибуције довољно великог простора могућих приоритета како би се осигурало да је веома мала вероватноћа да два чвора имају исти приоритет) онда је Декартово стабло има исту дистрибуцију вероватноће као и рандомно бинарно стабло, што је претраживачко стабло формирано уметањем чворова без уравнотежавања у случајно рандомно изабраном редоследу уметања. Пошто је за рандомно бинарно претраживачко дрво познато да има има логаритамску висину са високом вероватноћом, исто важи и за Декартова стабла.

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

Blelloch и Reid-Miller[4] описују апликацију Декартовог дрвета за проблеме одржавања скупа ставки и обављање операција скупа уније, скупа пресека, и скупа разлике, коришћењем Декартовог дрвета за приказ сваког скупа. Наор анд Ниссим[5] описују примену у одржавању ауторизације цертификата у криптосистемима с јавним кључем.

Операције

[уреди | уреди извор]

Конкретно, Декартово стабло подржава следеће операције:

  • Да бисте потражили задату вредност, примењује се стандардни алгоритам за бинарну претрагу у бинарном стаблу претраге, игноришући приоритете.
  • Да бисте уметнули нови кључ X у Декартово стабло, треба генерисати случајни приоритет Y за X. Бинарном претрагом за X у стаблу креирамо нови чвор на позицији листа, где бинарном претрагом одређујемо да чвор за X треба да постоји. Затим, док X није корен стабла и има већи приоритетни број од свог родитеља З, обављамо ротацију стабла која обрће родитељ-дете однос за X и З.
  • Да бисте избрисали чвор X из Декартовог стабла, ако је X лист стабла, једноствно га уклонити. Ако X има једно дете З, тада X уклонити са стабла тако да З буде родитељ X (или направити да је З корен стабла, ако је X имао родитеља). Коначно, ако X има двоје деце, тада он мења своју позицију у стаблу са положајем његовог непосредног наследника З у сортираном редоследу, што ће евентуално довести до неког од претходних случајева. У овом последњем случају, током замене може доћи до нарушавања Хипа, те ће онда можда морати да се врше неке додатне ротације како би се вратило у Хип стање стабла.
  • Да бисте поделили Декартово стабло на два мања Декартов стабла, на оне мање и оне веће од кључа X, X убаците у Декартово стабло са максималним приоритетом - већим приоритетом од било ког чвора у Декартовом стаблу. Након овог уметања, X ће бити корен Декартовог стабла, све вредности мање од X ће се наћи у левом подстаблу, а све вредности веће од X ће се наћи у десном подстаблу. Ова операција кошта колико и једно убацивање у Декартово стабло.
  • Спајање два Декартова стабла које су производ претходне поделе, можемо слободно да претпоставимо да је највећа вредност једног подстабл мања од најмање вредности другог. Убаците вредност X, тако да она буде веца од ове максималне вредности једног стабла и мања од минималне вредности другог, и доделите му минимални приоритет. Након убацивања биће чвор лист, па може лако бити обрисан. Резултат је једно Декартово стабло спојен од два оригинална стабла. Ово је практично "враћање" одвајања, а кошта исто.

Бинарно претраживачко дрво на случајан начин

[уреди | уреди извор]

Бинарно претраживачко дрво на случајан начин, представљено од стране Мартíнеза и Роура одмах након рада Арагона и Сеидела на Декартовим стаблима,[6] складишти исте чворове, са истом насумичном расподелом облика стабла, али задржава другачије информације у оквиру чворова стабла у циљу одржавања своје сучајне структуре.

Уместо складиштења насумичних приоритета на сваком чвору, Бинарно претраживачко дрво на случајан начин складишти мали цео број у сваком чвору, а то је број његових потомака (рачунајући и себе као један); ови бројеви се могу одржавати током операције ротације стабла у са константним додатним временом за сваку операцију ротације. Када треба да убацимо кључ X у стабло које већ садржи н чворова, алгоритам уметања бира са вероватнћом 1/(н   1) да постави X као нов корен стабла, а иначе се позива поступак за уметање рекурзивно у лево или десно подстабло (у зависности да ли је његов кључ мањи или већи од тренутног корена). Бројеви потомака се користе у алгоритму за израчунавање потребне вероватноће код случајног избора у сваком кораку. Постављање X у корен стабла се може вршити било као код Декартовог стабла, стављајући га на лист, а затим окретањем на горе, или по алтернативном алгоритму који су описали Мартíнез и Роура који дели подстабло на два дела, који се касније користе као леви и десни потомак новог чвора.

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

Поређење

[уреди | уреди извор]

Информација која је ускладиштена у чворовима у бинарно претраживачком стаблу на случајан начин је једноставнија него у Декартовом стаблу (мали цео број, а не високе прецизности случајних бројева), али захтева већи број позива генератора случајног броја (који има О(лог н) позива по операцији уметања или брисања, уместо само једног позива по уметању) и поступак убацивања је мало компликованији због потребе да се ажурира број потомака за сваки чвор. Мања техничка разлика је та што, у Декартовом стаблу, постоји мала вероватноћа судара (да ва кључа имају исти приоритет), а у оба случаја ће бити статистичке разлике између правог генератора случајних бројева и генератор псеудо-случајних бројева који се обично користе на дигиталним рачунарима. Међутим, у сваком случају је разлика између теоријског модела савршених случајних избора који се користе за дизајн алгоритама и могућности стварних генератора случајних бројева су занемарљиво мале.

Иако Декартово стабло и бинарно претраживачко стабло на случајан начин оба имају исту насумичну расподелу облика стабла након сваког ажурирања, историја, измена стабала које се обављају код ове две структуре података након низа операциа уметања или брисања, може бити различита. На пример, у Декартовом стаблу, ако се три броја 1,2 и 3 уметну у редоследу 1,3,2, азатим се број 2 избрише, преостала два чвора ће имати исту родитељ-потомак однос као и пре уметања средњег броја. У бинарно претраживачком стаблу на случајан начин, стабло након брисања је пођеднако вероватно да ће бити један од два могућа стабла на основу његова два чвора, независно од тога како је стабло изгледало пре убацивања средњег броја.

Референце

[уреди | уреди извор]
  1. ^ Арагон, Цецилиа Р.; Сеидел, Раимунд (1989), „Рандомизед Сеарцх Треес”, Проц. 30тх Сyмп. Фоундатионс оф Цомпутер Сциенце (ФОЦС 1989) (ПДФ), Wасхингтон, D.C.: ИЕЕЕ Цомпутер Социетy Пресс, стр. 540—545, ИСБН 0-8186-1982-1, дои:10.1109/СФЦС.1989.63531 
  2. ^ Сеидел, Раимунд; Арагон, Цецилиа Р. (1996), „Рандомизед Сеарцх Треес”, Алгоритхмица, 16 (4/5): 464—497, дои:10.1007/БФ01940876 
  3. ^ Вуиллемин, Јеан (1980), „А унифyинг лоок ат дата струцтурес”, Цоммун. АЦМ, Неw Yорк, НY, УСА: АЦМ, 23 (4): 229—239, дои:10.1145/358841.358852 
  4. ^ Блеллоцх, Гуy Е.; Реид-Миллер, Маргарет (1998), „Фаст сет оператионс усинг треапс”, Проц. 10тх АЦМ Сyмп. Параллел Алгоритхмс анд Арцхитецтурес (СПАА 1998), Неw Yорк, НY, УСА: АЦМ, стр. 16—26, ИСБН 978-0-89791-989-0, дои:10.1145/277651.277660 
  5. ^ Наор, M.; Ниссим, К. (2000), „Цертифицате ревоцатион анд цертифицате упдате”, ИЕЕЕ Јоурнал он Селецтед Ареас ин Цоммуницатионс, 18 (4): 561—570, дои:10.1109/49.839932 
  6. ^ Мартíнез, Цонрадо; Роура, Салвадор (1997), „Рандомизед бинарy сеарцх треес”, Јоурнал оф тхе АЦМ, 45 (2): 288—323, дои:10.1145/274787.274812 

Спољашње везе

[уреди | уреди извор]
Декартово дрво на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Dekartovo_drvo&oldid=28519536”