T-stablo: razlika između inačica

*Provjeri balans stabla: Kreni od lista prema korijenu; ukoliko se podstablo bilo kojeg od čvorova na tom putu razlikuje za više od jednog nivoa, izbalansiraj stablo, ali (za razliku od postupka kod algoritma umetanja), nakon balansiranja, potrebno je provjeriti i prvi roditeljski čvor. Razlog je to što rotacija jednog čvora može iz balansa izbaciti čvor iznad (prethodni, dakle roditeljski), te se balansiranje nastavlja sve dok se ne dođe do čvora koji jest u balansu.

 

Balansiranje T-stabla slično je balansiranju AVL stabla. Potrebno je ako se podstabla bilo kojeg čvora razlikuju za više od jedne razine, što se može dogoditi nakon umetanja ili brisanja čvora. Provjerava se put od lista do korijena stabla. Na tom putu mora se provjeriti za svaki čvor njegova podstabla. Ukoliko stablo nije u ravnoteži (jedno podstablo jednog od rečenih čvorova razlikuje se za više od jedne razine od drugog), čini se jedno rotiranje stabla - koja je dovoljno da se stablo vrati u ravnotežu. Ipak, nakon akcije brisanja rotiacija jednog čvora nakon može prouzročiti neravnotežu u čvoru roditelju, potrebno je ponavljati akciju rotacije za sve čvorove iznad onoga koje je prvo rotirano, dokle god se ne dođe do prvog čvora koji jest u ravnoteži.