Картезијанско стабло

Секвенца бројева и Картезијанско стабло изведено од њих.

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

Дефиниција

Картезијанско стабло за секвенце различитих бројева може бити једнозначно дефинисано поштујући следеће карактеристике:

1. Картезијанско стабло за секвенце има један чвор за сваки број у секвенци. Сваки чвор је повезан са јединственом вредношћу.
2. Симетрична (ин-ордер) шетња стабла враћа као резултат првобитну секвенцу бројева. Лево под-дрво се састоји од вредности пре него вредност самог корена у секвенци, док се десно под-стабло састоји од вредности које се налазе након корена и сличан редослед се састоји на сваком доњем чвору стабла.
3. Стабло има хип-особину: отац сваког чвора (сем корена) има мању вредност него вредност самог чвора.

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

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

Ефикасна конструкција

Први метод

Картезијанско стабло може бити конструисано у линеарном времену од улазне секвенце. Један метод је да једноставно процесирамо вредности секвенце у лево-ка-десном поретку, одржавајући Картезијанско стабло од чвора које смо процесирали, у структури која нам дозвољава нагоре и надоле шетње по стаблу. Да би процесирали сваку нову вредност X, почнемо од чвора који представља вредност пре X-а у секвенци и пратимо пут од овог чвора до корена стабла док не нађемо вредност Y која је мања од вредности X-а.

Овај чвор Y је отац чвора X, и претходно десно дете Y-а постаје ново лево дете X-а. Укупно време за ову процедуру је линеарно, зато што време потрошено за тражење оца Y-а од сваког новог чвора X може бити наплаћено од стране броја чворова која су обрисана са десног дела пут у стаблу.

Други метод

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

Коришћење сортирања

Парови узастопних секвенцних вредности (приказани као дебеле црвене гране) које држе секвенцну вредност 'X' (тамно-плава тачка). Цена садржавања 'X'-а у сортираном редоследу као резултат Левцопоулос & Петерссон алгоритма је пропорционална логаритму од броја ових парова.

Левцопоулос & Петерссон (1989) су описали алгоритам за сортирање базиран на Картезијанским стаблима. Они су описали алгоритам базиран на стаблу са највећом вредношћу у корену, али се може модификовати са лакоћом да подржава и Картезијанско стабло са претпоставком да је најмања вредност у корену. Модификована верзија је описана испод.

Левцопоулос & Петерссон алгоритам може бити посматран као верзија селецтион сорта или хип сорта која одржава приоритет реда са кандидатом минима, и да у сваком кораку тражи и брише најмање вредности у овом реду, померајући вредности на крају излазног низа. У њиховом алгоритму, приоритет реда се састоји само од елемената чији је отац у Картезијанском стаблу већ био пронађен и обрисан. Тако се алгоритам састоји од следећих корака:

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

Како су Левцопоулос & Петерссон показали, за улазне секвенце које су већ скоро сортиране, величина реда са приоритетом ће остати мала што ће дозволити овом методу да искористи предност скоро сортираног улаза и да се изврши брже. Специфично, сложеност најгорег могућег сценарија овог алгоритма је О(н лог к), где је К просек свих вредности X у секвенци од броја конструисаних парова секвенцних вредности које држе вредност X.

Историја

Картезијанска стабла су представљена и именована од стране Вуиллемин-а (1980). Име потиче од Картезијанског координатног система за раван: У Вуиллеминовој верзији ове структуре, као у дво-димензионом алгоритму претраживања са опсегом продискутованим горе, Картезијанско стабло за сет тачки има сортиран редослед тачака по њиховим X-координатама као његова симетрична шетња по стаблу и има својство хипа према Y-координатама тачака. Габоw, Бентлеy & Тарјан (1984) и јос неки аутори су пратили ову дефиницију у којој је Картезијанско стабло изведено из секвенце. Ова промена генерализује геометрична подешавања да би дозволила секвенце осталих ствари сем сортираних X-координата и дозволила Картезијанским стаблима да буду примењена на проблеме које нема геометричну суштину.

Референце

• Vuillemin, J. (1980). "A unifying look at data structures", Commun. ACM(New York, NY, USA: ACM).