|
Strukture podataka i algoritmi
|
| Nebalansirana stabla
|
Ako se u binarno stablo dodaje uredjeni niz objekata,
tada se dobija sledece nebalansirano stablo:
Pretrazivanje ovakvog stabla u najgorem slucaju
moze da zahteva cak n poredjenja.
Prema tome, vreme pretrazivanja binarnog stabla u najgorem slucaju je
O(n).
Kasnije cemo prouciti crveno-crna stabla,
koja obezbedjuju strategiju za izbegavanje ovakvog patoloskog ponasanja.
- Balansirano binarno stablo
- Binarno stablo u kome je svaki list na istom rastojanju od korena.
© John Morris, 1998.
Prevod sa engleskog,
Dragan Stevanovic, 2002.