Samobalansirajuće binarno stablo pretrage

U računarstvu, samo-balansirajuće binarno stablo pretrage je svako binarno stablo pretrage koje je zasnovano na čvorovima i koje automatski održava svoju visinu nakon novih umetanja i brisanja.^[1]

Isto stablo posle balansiranja po visini

Ova struktura efikasno omogućava implementaciju promenljivo raspoređenih lista, i može se koristiti za drugu apstraktnu strukturu podataka kao što je asocijativni niz, redni prioriteti i set.

Pregled uredi

Rotiranje stabla su vrlo česte unutrašnje operacije nad samo-balanisrajućim stablom binarne pretrage koje se koriste da bi stablo zadržalo savršen ili skoro savršen balans.

Većina operacija nad binarnim stablom pretrage(BSP) je vremenski direktno srazmerna visini stabla, tako da je poželjno visinu održavati što manjom. Binarno stablo sa visinom h može da sadrži najviše 2⁰+2¹+···+2^h = 2^h+1−1 čvorova. Sledi da za drvo sa n čvorova i h visina:

$n\leq 2^{h+1}-1$

Što podrazumeva:

$h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor$ .

Drugim rečima, najmanja visina drveta od n čvorova je log₂(n), spratne i ćelijske funkcije; koje su, $\lfloor \log _{2}n\rfloor$ :.^[1]

Inače, najjednostavniji algoritam BSP umetanjem podataka može da nosi stablo visine n u radije opštim situacijama. Na primer, kada su podaci umetani u srotirani primarni ključ, stablo se degeneriše u povezanu listu sa n čvorova. Razlika u preformansama između dve situacije može biti ogromna: za n=1,000,000, na primer, minimalna visina je $\lfloor \log _{2}(n)\rfloor =19$ .

Ako su podaci poznati pre vremena, visina se može održati malom, u prosečnom smislu, dodavanjem vrednosti u nasumičnom poretku, rezultujući u proizvoljno binarno stablo pretrage. Kako bilo, ima mnogo situacija(kao što su mrežni algoritmi) gde ova nasumičnost nije održiva.

Samo-balansirajuće binarno stablo rešava ovaj problem izvodeći transformacije nad stablom(kao što su rotacija stabla na knjičnim mestima) da bi zadržala proporcijonalnu visinu log₂(n).

Održavajuči visinu na najmanjoj vrednosti $\lfloor \log _{2}(n)\rfloor$ nije uvek moguće; može biti dokazano da svaki algoritam umetanja koji to radi bi imao prekomerno računanje. Time, većina samo-balansirajućih BSP algoritama održava visinu u okviru konstantnog faktora donje granice.

U asimptotskom smislu (Veliko O), samo-balansirajuće BSP struktura sadržavajući n podataka dozvoljava pronalaženja, umetanja, i uklanjanja podataka O(log n), najgori slučaj, i obilazak stabla svih članova O(n) vremena. Za neke implementacije ovo je granica pre-operacionog vremena, dok za neke su amortizacija granica preko niza operacija. Ova vremena su asimptotski optimalna među svim strukturama podataka koje manipulišu ključem kroz poređenja.

Implementacije uredi

Popularna struktura podataka koja implementira ovaj tip stabla uključuje:

Aplikacije uredi

Samo-balansirajuća binarna stabla pretrage mogu biti korišćena na prirodan način da konstrujiši i održavaju liste, kao što je redni prioritet. Takođe mogu biti korišćena za asocijativni niz, ključnim parovovima je da jednostavno budu umetnuti sa naručenjem zasnovano samo na ključu. U tom svojstvu, samo-balansirajuće BSP ima dosta vrlina i mana nad glavnim konkurentom, heš tabela. Jedna prednost samo-balansirajućeg BSP je ta da dozvoljava brzo (svakako, simptotski optimalno) enumeraciu podataka u ključnom poretku, što heš tabele ne pružaju. Jedna mana je ta da njihovi algoritmi pretrage biva dosta komplikovan kad postoji vise podataka sa istim ključem. Samo-balansirajuće BSP ima bolje gore-slučajeve preformanse pretrage nego heš tabela (O(log n) u odnosu na O(n)), ali ima gori prosečan-slučaj preformanse (O(log n) u odnosu na O(1)).

Samo-balansirajuće BSP može biti koripćeno da implementira bilo koji algoritam koji zahteva requires promenljive liste, da bi postigli optimalni najgori-slučaj asimptotske preformanse. Na primer, ako Sortiranje uz pomoć binarnog stabla je implementirano sa samo-balansirajućim BSP-om, imamo vrlo lako opisiv ipak asimptotski optimalan O(n log n) sortirajući algoritam. Slično, mnogi algoritmi u računarskoj geometriji iskorišćavaju varijacije nad samo-balansirajućim BSN-om da reše probleme kao što su raskrsnice duži problem i lokacije tačaka efikasno. (Za prosečan-slučaj preformansi, kako god, samo-balansirajuće BSP može da bude manje efikasno od ostalih solucija. Sortiranje binarnog stabla, u praksi, verovatno će biti sporije sortiranje spajanjem, kviksort, or hipsort, zbog stablo-balaansirajućeg računanja a takođe i zbog keš pristupa.

Samo-balansirajuća BSP su fleksibilne strukture podataka, u tome im je i lakse da se prošire na efikasnije snimanje podataka ili izvršavanje novih operacija. Na primer, jedan može da snimi određen broj čvorova u svakom podstablu imajući određene osobine, dozvoljavajući jednom da broji čvorove u određenom ključnom rastojanju sa tim osobinama u O(log n) vremenu. Ovi nastavci mogu biti korišćeni, na primer, da optimizuju upite baze podataka ili druge algoritme za obradu lista.

Vidi još uredi

Reference uredi

^ ^a ^b Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley. 1998. ISBN 978-0-201-89685-5. Section 6.2.3: Balanced Trees, pp. 458-481.

Spoljašnje veze uredi

Dictionary of Algorithms and Data Structures: Height-balanced binary search tree
GNU libavl, a LGPL-licensed library of binary tree implementations in C, with documentation

[knuth-1] Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley. 1998. ISBN 978-0-201-89685-5. Section 6.2.3: Balanced Trees, pp. 458-481.

[1]