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 je definisano kao fundamentalno stablo i skup od najviše dva čvora koja se nazivaju spoljašnji granični čvorovi.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Top_tree.jpg/250px-Top_tree.jpg)
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 se označava kao . Sa svakim jatom korisnik može povezati neke meta informacije i koristiti metode kako bi ga održao pod uticajem različitih unutršnjih operacija.
Jato putanje
Ako sadrži bar jednu ivicu, onda se naziva jato putanje.
Jato tačke
Videti jato lista
Jato lista
Ako ne sadrži ni jednu ivicu ili ima samo jedno granično teme onda se 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 \ se naziva unutrašnji čvor od
Putanja jata
Put izmedju graničnih temena od se naziva putanja jata od i označava se sa
Spojiva jata
Dva jata i su spojiva ako je jednostran skup(imaju tačno jedan zajednički čvor) i 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 logaritamskim rastom broja čvorova početnog stabla u vremenu); Top stablo u suštini predstavlja rekurzivnu podelu početnog stabla u jata.
U principu, stablo može imati težinu na svojim ivicama.
Postoji jedan na jedan korespondencija sa ivicama početnog stabla i listovima čvorova top stabla i svaki unutrašnji čvor od predstavlja jato koje je formirano unijom jata njegove dece.
Top stablo može biti inicijalizovano u vremenu.
Stoga je top stablo po ( ) binarno stablo za koje važi
- Čvorovi od su jata od ( );
- Listovi od su ivice od
- Jata rodjaci su komšije u smislu da se seku u jednom temenu i da ih spaja jato, koje je njihov roditelj.
- Koren od je stablo 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 i temena u različitim stablima 1 i 2. Operacija vraća jedno top stablo koje predstavlja vw
- Presecanje(v, w): Odvaja ivicu od stabla sa top stablom time ga pretvorivši u dva stabla v i w i vraća dva top stabla v i w.
- Otkrivanje(S): Zove se kao podrutina za sprovođenje najviše dva upita na top stablu. sadrži najviše dva temena. Prvobitna spoljašnja temnena postaju normalna temena, a temena od postaju nova spoljašnja granična temena top stabla. Ako nije prazno, operacija vraća novi koren jata sa 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 unutrašnjih operacija, sekvenca koja se računa u daljem 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.
se ažurira pozivanjem funkcije definisane od strane korisnika, povezane sa svakom unutrašnjom operacijom.
- Spajanje Ovde su i integrisana jata, operacija vraća kao roditeljsko jato od i sa graničnim temenima kao graničnim temenima od računa koristeći i
- Razdvajanje Ovde je jato korena Dopunjava i koristeći i onda briše jato iz .
Razdvajanje se obično sprovodi korišćenjem čistih metoda koje pozivaju korisničke metode za ažuriranje od i koristeći i ažuriranje tako da se zna da nema dalje potrebe za ažuriranjem njegove dece. Onda je 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 pravi jato za ivicu postavlja se računa od nule.
- Iskoreni je ivično jato Korisnički definisana funkcija se zove za obradu i onda je jato obrisno iz top stabla.
Nelokalna pretraga
Korisnik može da definiše Izaberi operacije koje za jato korena (bez listova) bira jato jednog njegovog deteta. Crna kutija top stabla omogućava Traži 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 , ivica se traži samo na putanji . 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 do može da se postigne kao =Otkrivanje({v,w}) praćeno sa Traži() i sa odgovarajućom operacijom izaberi. Za sprovođenje operacije izaberi koristimo globalnu promenljivu koja predstavlja i globalnu promenljivu koja predstavlja Operacija izaberi bira jato sa ako i samo ako je dužina od najmanje . Kako bi podržala operaciju dužina se mora održavati u .
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 bi u tom slučaju zahtevalo i održavanje jediničnih dužina u .
Pronalaženje centra stabla koje sadrži teme 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 =Otkrivanje({v}) praćeno sa Traži() i pogodnom operacijom izaberi. Operacija izaberi bira između dece sa dete sa većom maksimalnom distancom. Kako bi podržala operaciju maksimalna distanca u podstablu jata sa graničnim temenom treba da bude održavana u . 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 vremenu po spajanju i razdvajanju, koji podržavaju upite o maksimalnoj težini ivice između bilo koja dva temena u vremenu.
- Dokaz konture: Uključuje održavanje maksimalne težine putanje jata na svakom čvoru, ako je jato tačke onda je maks_tež() inicijalizovano kao Kad je jato unija dva jata onda je to maksimalna vrednost dva spojena jata. Ukoliko moramo naći maks_tež između i onda radimo Otkrivanje i prijavimo maks_tež
- ([SLEATOR I TARJAN 1983]). U slučaju gore navedene aplikacije takođe možemo dodati zajedničku težinu svim ivicama na datoj putanji · · · u vremenu.
- Dokaz konture: Uvodimo težinu koja se naziva posebnom() kako bi bila dodana svim ivicama u Što se adekvatno održava ; razdvajanje() zahteva da za svako dete putanje od postavimo maks_tež(A) := maks_tež() + posebna() i posebna() := posebna() + posebna(). Za := pridružiti( ), postavimo maks_tež() := maks {max_wt(), maks_tež()} i posebna() := 0. Konačno, da bi našli maksimalnu težinu na putanji · · · postavimo := Otkrivanje i vraćamo maks_tež().
- ([GOLDBERG ET AL. 1991]). Možemo tražiti maksimalnu težinu u fundamentalnim stablima koja sadrže dato teme u 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 i može biti pronađena u vremenu kao dužina(Otkriti).
- Dokaz konture: Održavaćemo dužinu () putanje jata. Dužina se održava kao maksimalna težina sa tim da ako je kreirano spajanjem, dužina() je zbir dužina čuvan u putanjama njegove dece.
- Upiti vezani za prečnik stabla i održavanje njegovih sledbenika zahtevaju vreme.
- Centar i središnja linija mogu da se održavaju pod operacijama spajanja i razdvajanja i ispitivani nelokalnom pretragom u 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 . Upiti mogu biti sprovedeni još brže. Algoritam nije trivijalan, koristi 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 . Upiti mogu biti sprovedeni još brže. Algoritam nije trivijalan, koristi 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 može biti predstavljena kao jato particije stabla(JPS) zamenom svakog jata u drvetu sa ivicom. Ako koristimo strategiju P za particionisanje , onda će JPS biti JPSP. Ovaj postupak se ponavlja rekurzivno sve dok ne ostane samo jedna ivica.
Možemo primetiti da su svi čvorovi odgovarajućeg top stabla 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.
Strategija podele je važna dok delimo stablo na jata. Samo pažljiva strategija garantuje da ćemo završiti u jednoj 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 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. Недостаје или је празан параметар
|title=
(помоћ). 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. Недостаје или је празан параметар
|title=
(помоћ). 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
Проверите вредност параметра
|arxiv=
(помоћ).
Spoljašnje veze
- Self Adjusting Top Trees. Tarjan and Werneck
- Self-Adjusting Top Trees. Tarjan and Werneck, Proc. 16th SoDA, 2005
Шаблон:CS-Stabla