Topologija stabla je posebna vrsta strukture u kojoj su mnogi povezani elementi raspoređeni kao grane stabla. Na primjer, topologije stabala se često koriste za organiziranje računala u korporacijskoj mreži ili za informacije u bazi podataka.

U topologiji stabla može postojati samo jedna veza između bilo kojih dva povezana čvora. Budući da svaka dva čvora mogu imati samo jednu međusobnu vezu, topologije stabala formiraju prirodnu roditeljsku i podređenu hijerarhiju.

U računalnim mrežama, topologija stabla je također poznata kao topologija zvijezda . On uključuje elemente topologije sabirnice i topologije zvijezda. U nastavku je primjer mrežnog dijagrama topologije stabla, u kojem su središnji čvorovi dviju zvjezdastih mreža međusobno povezani.

Na gornjoj slici, ako glavni kabel ili prtljažnik između svake od topoloških mreža dvije zvijezde ne uspije, te mreže ne bi mogle međusobno komunicirati. Međutim, računala na istoj topologiji zvijezda i dalje bi mogla komunicirati.

Topologija stabla u računalnom programiranju

U računalnom programiranju, topologije stabala mogu se koristiti za strukturiranje mnogih vrsta podataka, uključujući i sam računalni program.

Na primjer, ovo je jednostavan računalni program napisan u Lisp-u:

 (+ 1 2 (ako (> p 10) 3 4)) 

Ovaj program kaže "Ako je p veći od 10, dodajte brojeve 1, 2 i 3. Inače, dodajte brojeve 1, 2 i 4." Kao i svi Lisp programi, on ima svojstvenu strukturu topologije stabla. Ako ga nacrtamo kao graf, izgleda kao stablo prikazano desno. Predstavljanje programa na ovaj način može biti korisno jer jasno pokazuje kako su sve operacije i podaci povezani.

Programi u takvoj strukturi također imaju posebne namjene. Primjerice, tehnike genetskog programiranja mogu razviti nove računalne programe razmjenom grana između postojećih programa strukturiranih kao stabla.

Topologija stabla u binarnim stablima

Binarno stablo je topologija stabla u kojoj svaki čvor ima najviše dvoje djece. Dječji čvorovi su označeni kao "lijevo dijete" ili "pravo dijete". Ova vrsta strukture podataka često se koristi za sortiranje i pretraživanje velikih količina podataka. U binarnom stablu prikazanom u nastavku, lijevo dijete svakog roditelja ima vrijednost manju od prave djece.

B-stabla

B-stablo je varijacija binarnog stabla koje su izumili Rudolf Bayer i Ed McCreight u Boeing Labs-u 1971. Njegovi čvorovi imaju djecu koja spadaju u prethodno definirani minimum i maksimum, obično između 2 i 7. Jednostavno B-stablo grafikon može izgledati kao slika ispod.

B-stabla su "samo-balansirajuća", što znači da se visina grana upravlja tako da ne dobivaju proizvoljno velike. Svaki čvor sadrži particijske "ključne vrijednosti" koje označavaju vrijednosti djece. Njihov dizajn je optimiziran za rukovanje vrlo velikim datotekama i za upisivanje podataka u memoriju ili disk. Oni se široko koriste u sustavima baza podataka kao što su MySQL, PostgreSQL i Redis te datotečni sustavi kao što su NTFS, HFS + i ext4.

Uvjeti mreže, topologija