Top stablo

Top stablo je struktura podataka zasnovana na binarnom stablu koja se primenjuje na dinamičkom stablu bez korena za razne operacije vezane za putanje. Dozvoljava jednostavne podeli pa vladaj algoritme. Održava dinamički različite osobine stabla, kao što su prečnik, centar i središnja linija.

Top stablo $\Re$ je definisano kao fundamentalno stablo ${\mathcal {T}}$ i skup $\partial {T}$ od najviše dva čvora koja se nazivaju spoljašnji granični čvorovi.

Slika prikazuje Top stablo izgrađeno od fundamentalnog stabla(crni čvorovi). Stablo je prema ivicama podeljeno na jata i na potpuno novo top-stablo za njih. Popunjeni čvorovi na vrhu top-stabla su jata putanja, dok mali kružni čvorovi predstavljaju jata listova. Veliki kružni čvor predstavlja koren. Velika slova označavaju jata, a mala slova označavaju čvorove.

Alfabetska lista tehničkih termina

Granični čvorovi

Videti #Granična temena

Granična temena

Teme u povezanom podstablu je granično teme ako je ivicom povezano sa najvišom tačkom izvan podstabla.

Spoljašnja granična temena

Par temena top stabla mogu da se nazivaju spoljašnja granična temena. Posmatraju se kao granična temena jata koja predstavljaju celo top stablo.

Jato

Jato je povezano podstablo sa najviše dva granična temena. Skup od graničnih temena datog jata ${\mathcal {C}}$ se označava kao $\partial {C}.$. Sa svakim jatom ${\mathcal {C}}$ korisnik može povezati neke meta informacije $I({\mathcal {C}}),$ i koristiti metode kako bi ga održao pod uticajem različitih unutršnjih operacija.

Jato putanje

Ako $\pi ({\mathcal {C}})$ sadrži bar jednu ivicu, onda se ${\mathcal {C}}$ naziva jato putanje.

Jato tačke

Videti jato lista

Jato lista

Ako $\pi ({\mathcal {C}})$ ne sadrži ni jednu ivicu ili ${\mathcal {C}}$ ima samo jedno granično teme onda se ${\mathcal {C}}$ zove jato lista.

Jato ivice

Jato koje sadrži samo jednu ivicu se naziva jato ivice.

List jata ivice

List u originalnom jatu koji je je predstavljen jatom sa samo jednim graničnim temenom naziva se list jata ivice

Putanja jata ivice

Ivica Jata sa dva granična temena se zove putanja jata ivice.

Unutrašnji čvor

Čvor u ${\mathcal {C}}$ \ $\partial {C}$ se naziva unutrašnji čvor od ${\mathcal {C}}.$

Putanja jata

Put izmedju graničnih temena od ${\mathcal {C}}$ se naziva putanja jata od ${\mathcal {C}}$ i označava se sa $\pi ({\mathcal {C}}).$

Spojiva jata

Dva jata ${\mathcal {A}}$ i ${\mathcal {B}}$ su spojiva ako je ${\mathcal {A}}\cap {\mathcal {B}}$ jednostran skup(imaju tačno jedan zajednički čvor) i ${\mathcal {A}}\cup {\mathcal {B}}$ je jato.

Uvod

Top Stabla se koriste za održavanje dinamičkog skupa stabala pod operacijama vezivanja i prekidanja.

Osnovna ideja je održavanje balansiranog binarnog stabla $\Re$ logaritamskim rastom broja čvorova početnog stabla ${\mathcal {T}}$ u ${\mathcal {O}}(\log n)$ vremenu); Top stablo u suštini predstavlja rekurzivnu podelu početnog stabla ${\mathcal {T}}$ u jata.

U principu, stablo ${\mathcal {T}}$ može imati težinu na svojim ivicama.

Postoji jedan na jedan korespondencija sa ivicama početnog stabla ${\mathcal {T}}$ i listovima čvorova top stabla $\Re$ i svaki unutrašnji čvor od $\Re$ predstavlja jato koje je formirano unijom jata njegove dece.

Top stablo može biti inicijalizovano u ${\mathcal {O}}(n)$ vremenu. ${\mathcal {T}}$

Stoga je top stablo $\Re$ po (${\mathcal {T}},$ $\partial {T}$) binarno stablo za koje važi

• Čvorovi od $\Re$ su jata od (${\mathcal {T}},$ $\partial {T}$ );
• Listovi od $\Re$ su ivice od ${\mathcal {T}};$
• Jata rodjaci su komšije u smislu da se seku u jednom temenu i da ih spaja jato, koje je njihov roditelj.
• Koren od $\Re$ je stablo ${\mathcal {T}}$ samo sebi, sa skupom od najviše dva spoljašnja granična temena.

Stablo sa samo jednim temenom ima prazno top stablo, a stablo sa samo jednom ivicom je samo pojedinačan čvor.

Ova stabla se lako uvećavaju, omogućavajući korisniku širok spektar fleksibilnosti i produktivnosti bez ulaženja u detalje funkcionisajna internih struktura podataka, što se često naziva crna kutija.

Dinamičke operacije

Sledeće tri operacije su dostupne korisniku.

• Povezivanje(v, w): Gde su $v$ i $w$ temena u različitim stablima ${\mathcal {T}}$₁ i ${\mathcal {T}}$₂. Operacija vraća jedno top stablo koje predstavlja $\Re$_v$\cup$$\Re$_w$\cup {(v,w)}$

• Presecanje(v, w): Odvaja ivicu ${(v,w)}$ od stabla ${\mathcal {T}}$ sa top stablom $\Re ,$ time ga pretvorivši u dva stabla ${\mathcal {T}}$_v i ${\mathcal {T}}$_w i vraća dva top stabla $\Re$_v i $\Re$_w.

• Otkrivanje(S): Zove se kao podrutina za sprovođenje najviše dva upita na top stablu. $S$ sadrži najviše dva temena. Prvobitna spoljašnja temnena postaju normalna temena, a temena od $S$ postaju nova spoljašnja granična temena top stabla. Ako $S$ nije prazno, operacija vraća novi koren jata ${\mathcal {C}}$ sa $\partial {C}=S.$ Otkrivanje({v,w}) je neuspešno ako su temena sa različitih stabala.

Unutrašnje operacije

Ažuriranje stabla se sprovodi sekvencom od najviše ${\mathcal {O}}(\log n)$ unutrašnjih operacija, sekvenca koja se računa u daljem ${\mathcal {O}}(\log n)$ vremenu. Može se desiti da se u toku ažuriranja stabla jato lista promeni u jato putanje i obratno. Dopune na top stablu se isključivo vrše ovim unutrašnjim operacijama.

$I({\mathcal {C}})$ se ažurira pozivanjem funkcije definisane od strane korisnika, povezane sa svakom unutrašnjom operacijom.

• Spajanje$({\mathcal {A}},{\mathcal {B}}){:}$ Ovde su ${\mathcal {A}}$ i ${\mathcal {B}}$ integrisana jata, operacija vraća ${\mathcal {C}}$ kao roditeljsko jato od ${\mathcal {A}}$ i ${\mathcal {B}}$ sa graničnim temenima kao graničnim temenima od ${\mathcal {A}}\cup {\mathcal {B}}.$ računa $I({\mathcal {C}})$ koristeći $I({\mathcal {A}})$ i $I({\mathcal {B}}).$

• Razdvajanje$({\mathcal {C}}){:}$ Ovde je ${\mathcal {C}}$ jato korena ${\mathcal {A}}\cup {\mathcal {B}}.$ Dopunjava $I({\mathcal {A}})$ i $I({\mathcal {B}})$ koristeći $I({\mathcal {C}})$ i onda briše jato ${\mathcal {C}}$ iz $\Re$.

Razdvajanje se obično sprovodi korišćenjem čistih$({\mathcal {C}})$ metoda koje pozivaju korisničke metode za ažuriranje od $I({\mathcal {A}})$ i $I({\mathcal {B}})$ koristeći $I({\mathcal {C}})$ i ažuriranje $I({\mathcal {C}})$ tako da se zna da nema dalje potrebe za ažuriranjem njegove dece. Onda je ${\mathcal {C}}$ odbačeno bez pozivanja korisnički definisanih funkcija. Čist metod se često koristi ze upite koji ne treba da se razdvajaju. Ako razdvajanje ne koristi podrutinu čistog metoda, a čist metod je potreban, njegov efekat bi mogao biti postignut kombinovanjem spajanja i razdvajanja.

Sledeće dve funkcije su analogne dvema prethodnima i koriste se za bazna jata.

• Napravi$(v,w){:}$ pravi jato ${\mathcal {C}}$ za ivicu $(v,w).$ postavlja $\partial {C}=\partial$$(v,w).$ $I({\mathcal {C}})$ se računa od nule.

• Iskoreni$({\mathcal {C}}){:}$ ${\mathcal {C}}$ je ivično jato $(v,w).$ Korisnički definisana funkcija se zove za obradu $I({\mathcal {C}})$ i onda je jato ${\mathcal {C}}$ obrisno iz top stabla.

Nelokalna pretraga

Korisnik može da definiše Izaberi$({\mathcal {C}}){:}$ operacije koje za jato korena (bez listova) bira jato jednog njegovog deteta. Crna kutija top stabla omogućava Traži$({\mathcal {C}}){:}$ rutinu, koja organizuje izaberi upite i reorganizuje top stablo(koristeći unutrašnje operacije) tako da pronalazi jedinu ivicu u raskrsnici svih odabranih jata. Ponekad bi pretraga trebala biti ograničena samo na putanju. Postoji varijanta nelokalne pretrage za ovu svrhu. Ako postoje dva spoljašnja granična temena u jatu korena ${\mathcal {C}}$, ivica se traži samo na putanji $\pi ({\mathcal {C}})$. Dozvoljeno je da se urade sledeće izmene: Ako je samo jedno dete jata korena jato putanje, bira se po difoltu bez poziva izaberi operacije.

Primeri nelokalne pretrage

Pronalaženje i-te ivice na dužem putu od $v$ do $w$ može da se postigne kao ${\mathcal {C}}$=Otkrivanje({v,w}) praćeno sa Traži(${\mathcal {C}}$) i sa odgovarajućom operacijom izaberi. Za sprovođenje operacije izaberi koristimo globalnu promenljivu koja predstavlja $v$ i globalnu promenljivu koja predstavlja $i.$ Operacija izaberi bira jato ${\mathcal {A}}$ sa $v\in \partial {A}$ ako i samo ako je dužina od $\pi ({\mathcal {A}})$ najmanje $i$. Kako bi podržala operaciju dužina se mora održavati u $I$.

Sličan zadatak može biti formulisan za graf sa ivicama nejedinične dužine. U tom slučaju daljina može da adresira ivicu ili teme između dve ivice. Mogli bi definisati operaciju izaberi tako da se ivica koja vodi do temena vraća u drugom slučaju. Tu bi se moglo definisati ažuriranje koje povećava dužinu svih ivica duž putanjom konstante. U tom slučaju ažuriranja su izvršena u konstantnom vremenu samo u jatu korena. Čist metod je potreban kako bi distribuirao odloženo ažuriranje dece. Čist metod bi trebao biti pozvan pre nego što je funkcija traži pozvana. Održavanje dužine u $I$ bi u tom slučaju zahtevalo i održavanje jediničnih dužina u $I$.

Pronalaženje centra stabla koje sadrži teme $v$ moglo bi da se postigne bilo pronalaženjem bicentralne ivice, bilo ivice sa centrom kao jednom krajnjom tačkom. Ivica bi mogla biti nađena kao ${\mathcal {C}}$=Otkrivanje({v}) praćeno sa Traži(${\mathcal {C}}$) i pogodnom operacijom izaberi. Operacija izaberi bira između dece ${\mathcal {A}},$ ${\mathcal {B}}$ sa $a\in \partial {A}\cap \partial {B}$ dete sa većom maksimalnom distancom$(a)$. Kako bi podržala operaciju maksimalna distanca u podstablu jata sa graničnim temenom treba da bude održavana u $I$. To takodje podrazumeva održavanje dužine putanje jata.

Zanimljivi rezultati i aplikacije

Broj zanimljivih aplikacija prvobitno sprovedenih drugim metodama su lako sprovedene korišćenjem interfejsa top stabla. Neke od njih su

• ([SLEATOR I TARJAN 1983]). Možemo održati dinamičku kolekciju otežanih stabala u ${\mathcal {O}}(\log n)$ vremenu po spajanju i razdvajanju, koji podržavaju upite o maksimalnoj težini ivice između bilo koja dva temena u $O(\log n)$ vremenu.
  • Dokaz konture: Uključuje održavanje maksimalne težine putanje jata na svakom čvoru, ako je jato tačke onda je maks_tež(${\mathcal {C}}$) inicijalizovano kao $-\infty .$ Kad je jato unija dva jata onda je to maksimalna vrednost dva spojena jata. Ukoliko moramo naći maks_tež između $v$ i $w$ onda radimo ${\mathcal {C}}=$ Otkrivanje$(v,w),$ i prijavimo maks_tež$({\mathcal {C}}).$

• ([SLEATOR I TARJAN 1983]). U slučaju gore navedene aplikacije takođe možemo dodati zajedničku težinu $x$ svim ivicama na datoj putanji $v$ · · ·$w$ u ${\mathcal {O}}(\log n)$ vremenu.
  • Dokaz konture: Uvodimo težinu koja se naziva posebnom(${\mathcal {C}}$) kako bi bila dodana svim ivicama u $\pi ({\mathcal {C}}).$ Što se adekvatno održava ; razdvajanje(${\mathcal {C}}$) zahteva da za svako dete putanje ${\mathcal {A}}$ od ${\mathcal {C}},$ postavimo maks_tež(A) := maks_tež(${\mathcal {A}}$) + posebna(${\mathcal {C}}$) i posebna(${\mathcal {A}}$) := posebna(${\mathcal {A}}$) + posebna(${\mathcal {C}}$). Za ${\mathcal {C}}$ := pridružiti(${\mathcal {A}},$ ${\mathcal {B}}$), postavimo maks_tež(${\mathcal {C}}$) := maks {max_wt(${\mathcal {A}}$), maks_tež(${\mathcal {B}}$)} i posebna(${\mathcal {C}}$) := 0. Konačno, da bi našli maksimalnu težinu na putanji $v$ · · ·$w,$ postavimo ${\mathcal {C}}$ := Otkrivanje$(v,w)$ i vraćamo maks_tež(${\mathcal {C}}$).

• ([GOLDBERG ET AL. 1991]). Možemo tražiti maksimalnu težinu u fundamentalnim stablima koja sadrže dato teme $v$ u ${\mathcal {O}}(\log n)$ vremenu.
  • Dokaz konture: Ovo zahteva održavanje dodatne informacije o maksimalnoj težini negrupisane putanje ivice u jatu pod operacijama spajanja i razdvajanja.

• Razdaljina između dva temena $v$ i $w$ može biti pronađena u ${\mathcal {O}}(\log n)$ vremenu kao dužina(Otkriti$(v,w)$).
  • Dokaz konture: Održavaćemo dužinu (${\mathcal {C}}$) putanje jata. Dužina se održava kao maksimalna težina sa tim da ako je ${\mathcal {C}}$ kreirano spajanjem, dužina(${\mathcal {C}}$) je zbir dužina čuvan u putanjama njegove dece.

• Upiti vezani za prečnik stabla i održavanje njegovih sledbenika zahtevaju ${\mathcal {O}}(\log n)$ vreme.

• Centar i središnja linija mogu da se održavaju pod operacijama spajanja i razdvajanja i ispitivani nelokalnom pretragom u ${\mathcal {O}}(\log n)$ vremenu.

• Graf bi mogao biti održavan dozvoljavajući ažuriranje skupa ivica i postavljanje upita na ivice sa dve veze. Amortizovana složenost ažuriranja je $O(\log ^{4}n)$. Upiti mogu biti sprovedeni još brže. Algoritam nije trivijalan, $I({\mathcal {C}})$ koristi $\Theta (\log ^{2}n)$ prostora ([HOLM, LICHTENBERG, THORUP 2000]).

• Graf bi mogao biti održavan dozvoljavajući ažuriranje skupa ivica i postavljanje upita na ivice sa dve veze. Amortizovana složenost ažuriranja je $O(\log ^{5}n)$. Upiti mogu biti sprovedeni još brže. Algoritam nije trivijalan, $I({\mathcal {C}})$ koristi $\Theta (\log ^{2}n)$ prostora ([HOLM, LICHTENBERG, THORUP 2001]).

Implementacija

Top stablo može biti implementirano na mnogo različitih načina. Neki od njih uključuju implementaciju koja koristi takozvanu "višestepenu podelu"(top stablo i dinamički algoritmi sa grafovima, Jakov Holm i Kristijan de Lihtenberg, tehnički izveštaj), ili čak koriste Sleator-Tarjan s-t stabla (tipično sa amortizovanim vremenskim okvirima).

Amortizovane implementacije su jednostavnije, ali sa malim multiplikativnim faktorima u vremenskoj složenosti. Nasuprot tome, najgori slučaj omogućava ubrzavanje upita, isključivanjem nepotrebnih informacija ažuriranja tokom upita. Nakon što je odgovoreno na upit, izvorno stanje stabla se koristi i verzija upita se odbacuje.

Korišćenje višespratne particije

Svaka podela jata stabla ${\mathcal {T}}$ može biti predstavljena kao jato particije stabla(JPS) $({\mathcal {T}}),$ zamenom svakog jata u drvetu ${\mathcal {T}}$ sa ivicom. Ako koristimo strategiju P za particionisanje ${\mathcal {T}}$, onda će JPS biti JPS_P${\mathcal {T}}.$. Ovaj postupak se ponavlja rekurzivno sve dok ne ostane samo jedna ivica.

Možemo primetiti da su svi čvorovi odgovarajućeg top stabla $\Re$ jedinstveno mapirani u ivicama ove podele na više nivoa. U ovoj podeli mogu postojati neke ivice koje ne odgovaraju nijednom čvoru u top stablu, i to su ivice koje predstavljaju jedino dete u nivou ispod. Samo ivice koje odgovaraju složenim jatima odgovaraju čvorovima u top stablu$\Re .$.

Strategija podele je važna dok delimo stablo ${\mathcal {T}}$ na jata. Samo pažljiva strategija garantuje da ćemo završiti u jednoj ${\mathcal {O}}(\log n)$ visini nivoa višestepenog particionisanja.

• Broj ivica u narednim nivoima treba smanjiti za konstantan faktor.
• Ukoliko je niži nivo izmenjen ažuriranjem, onda bi trebalo da bude u stanju da ažurira odmah nivo iznad njega, koristeći najveći konstantan broj umetanja i brisanja.

Prethodna strategija patricionisanja obezbedjuje odrzavanje Top stabla u ${\mathcal {O}}(\log n)$ vremenu.

Reference

• Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel (2005). „Maintaining information in fully dynamic trees with top trees”. ACM Transactions on Algorithms. 1 (2): 243—264. S2CID 1317. doi:10.1145/1103963.1103966. 
• Holm, Jacob; De Lichtenberg, Kristian; Thorup, Mikkel (2001). „Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity”. Journal of the ACM. 48 (4): 723—760. S2CID 7273552. doi:10.1145/502090.502095. 
• Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley. . 1997. ISBN 978-0-201-89683-1.  . Section 2.3: Trees, pp. 308-423.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. . 2001. ISBN 978-0-262-03293-3.  . Section 10.4: Representing rooted trees, pp. 214-217. Chapters 12-14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253-320.

Dodatna literatura

• „Maintaining Information in Fully Dynamic Trees with Top Trees. Alstrup et al”. arXiv:abs/cs.DS/0310065  . 

Spoljašnje veze

• Self Adjusting Top Trees. Tarjan and Werneck
• Self-Adjusting Top Trees. Tarjan and Werneck, Proc. 16th SoDA, 2005