Težinski-balansirano stablo
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Težinski-balansirano binarno stablo je binarno stablo koje je balansirano na osnovu informacija koje ukazuju na verovatnoću traženja određenog čvora. Unutar svakog podstabla, čvor sa najvećom težinom se prikazuje kao koren. Ovo može rezultirati efikasnijim primenjivanjem pretrage.
Osobine
[уреди | уреди извор]Lema
[уреди | уреди извор]U težinski-balansiranom stablu za svaki proizvoljan čvor P važi da je |Tlp|≤3|Tdp|+1, i |Tdp|≤3|Tlp|+1, gde je |Tdp| kardinalnost desnog podstabla čvora P, a |Tlp| kardinalnost levog podstabla čvora P.
Dokaz leme
[уреди | уреди извор]Vrši se indukcijom po broju čvorova u stablu.
Teorema
[уреди | уреди извор]Maksimalna visina težinski-balansiranog stabla je O(log n), gde je n broj čvorova u stablu.
Dokaz teoreme
[уреди | уреди извор]Izvodi se iz leme.
Dijagram
[уреди | уреди извор]Na dijagramu 1 koji prikazuje težinski-balansirano stablo, slova predstavljaju vrednosti čvorova, a brojevi težine čvorova. Vrednosti se koriste kako bi se uredilo stablo, po istom principu kao i binarno stablo pretrage. Na težinu se može gledati kao na verovatnoću ili broj aktivnosti vezanih za određeni čvor. Na dijagramu, koren je G zato što je njegova težina najveća od svih čvorova u stablu. Levo podstablo čvora G počinje sa A zato što A ima najveću težinu od čvorova u tom podstablu. Isto važi i za desno podstablo čvora G, N je čvor sa najvećom težinom od svih čvorova koji dolaze posle G.
Složenost
[уреди | уреди извор]
Prosečno vreme pretrage
[уреди | уреди извор]Kao i za sve algoritme zasnovane na binarnom stablu pretrage, tako i težinski-balansirano stablo ima prosečno vreme pretrage O(log n). Na dijagramu 2 se može videti poređenje efikasnosti pretrage nad različitim strukturama podataka.
Prostorna složenost
[уреди | уреди извор]Količina prostora koja je neophodna je ekvivalentna kao i kod AVL stabla i većine stabala binarne pretrage odnosno O(n).
Vidi još
[уреди | уреди извор]Reference
[уреди | уреди извор]- Jean-Paul Tremblay and Grant A. Cheston. Data Structures and Software Development in an object-oriented domain, Eiffel Edition. Prentice Hall, (2001) ISBN 978-0-13-787946-5.
- J. L. Baer. Weight-balanced trees, University of Washington,1975.