Танго стабло

Tango stablo (енгл. tango tree) је врста бинарног стабла претраживања којег су направили Erik D. Demaine, Dion Harmon, John Iacono и Mihai Patrascu 2004. године. То је online бинарно претраживачко стабло које постиже временску сложеност $O(\log \log n)$ у конкурентном односу према одговарајућем offline алгоритму и користи само $O(\log \log n)$ битова додатног простора меморије по чвору. Ово је напредак у односу на претходни најбољи конкурентни однос који је био $O(\log n)$.

Структура

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

Референцно стабло

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

Пожељне стазе

Прво за сваки чвор дефинишемо приоритетно дете које је неформално најскорије 'додирнуто' дете од стране класичне бинарне претраге стабла. Формалније, посматрамо подсабло Т са кореном к и децом тог корена л (леви) и д (десни). Одређујемо да је д приоритетно дете корена к ако је најскорије посећен чвор стабла Т у подстаблу које као корен има вредност д, а л ће постати приоритетно дете ако то није случај. Приметимо да ако је најскорије посећен чвор стабла Т сам корен к, онда л постаје приоритетно дете по дефиницији.

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

Помоћна стабла

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

Алгоритам

Претрага

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

Ажурирање

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

Споји

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

Исеци

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

Конкурентни однос

Танго стабла су $O(\log \log n)$-конкурентна јер посао који одради оптималан оффлине бинарно претраживачко стабло је макар линеарно у к (укупан број мењања приоритетне деце) и посао који уради танго стабло је у најгорем случају $(k+1)O(\log \log n)$

Види још

• Splay stablo
• Бинарно стабло претраге
• Црвено-црно стабла
• Бинарно стабло