Drevesna topologija je posebna vrsta strukture, v kateri so mnogi povezani elementi razvrščeni kot veje drevesa. Na primer, drevesne topologije se pogosto uporabljajo za organiziranje računalnikov v omrežju podjetja ali za informacije v bazi podatkov.

V drevesni topologiji lahko obstaja le ena povezava med katerima koli povezanima vozlišči. Ker imajo lahko vsaka dva vozlišča samo eno medsebojno povezavo, drevesne topologije tvorijo naravno hierarhijo staršev in otrok.

V računalniških omrežjih je drevesna topologija znana tudi kot topologija zvezda . Vključuje elemente topologije vodila in topologije zvezd. Spodaj je prikazan mrežni diagram drevesne topologije, v katerem so osrednja vozlišča dveh zveznih omrežij med seboj povezana.

Na zgornji sliki, če bi glavni kabel ali trunk med dvema zvezdastima topološkima omrežjema propadel, ta omrežja ne bi mogla komunicirati drug z drugim. Vendar pa bi računalniki z isto topologijo zvezdic še vedno lahko komunicirali.

Tree topologija v računalniškem programiranju

V računalniškem programiranju se lahko drevesne topologije uporabljajo za strukturiranje številnih vrst podatkov, vključno s samim računalniškim programom.

To je na primer preprost računalniški program, napisan v Lispu:

 (+ 1 2 (če (> p 10) 3 4)) 

Ta program pravi: "Če je p večji od 10, dodajte številke 1, 2 in 3. V nasprotnem primeru dodajte številke 1, 2 in 4." Tako kot vsi programi Lisp ima tudi lastno strukturo drevesne topologije. Če jo narišemo kot graf, je videti kot drevo prikazano na desni. Predstavljanje programa na ta način je lahko koristno, ker jasno kaže, kako so povezane vse operacije in podatki.

Programi v tej strukturi imajo tudi posebne namene. Na primer, tehnike genetskega programiranja lahko razvijejo nove računalniške programe z izmenjavo vej med obstoječimi programi, strukturiranimi kot drevesa.

Topologija dreves v binarnih drevesih

Binarno drevo je drevesna topologija, v kateri ima vsako vozlišče največ dva otroka. Otroška vozlišča so označena kot "levi otrok" ali "pravi otrok". Ta vrsta podatkovne strukture se pogosto uporablja za razvrščanje in iskanje velikih količin podatkov. V spodaj prikazanem binarnem drevesu ima levi otrok vsakega od staršev vrednost, ki je manjša od pravega otroka.

B-drevesa

B-drevo je različica binarnega drevesa, ki so ga izumili Rudolf Bayer in Ed McCreight v Boeing Labsu leta 1971. V njenih vozliščih so otroci, ki spadajo v vnaprej določen minimum in največ, običajno med 2 in 7. Preprosta B-drevo graf bi lahko izgledal kot spodnja slika.

B-drevesa so "samo-uravnotežujoča", kar pomeni, da se višina vej upravlja tako, da ne postanejo poljubno velike. Vsako vozlišče vsebuje particijske "ključne vrednosti", ki označujejo vrednosti otrok. Njihova zasnova je optimizirana za delo z zelo velikimi podatkovnimi datotekami in za zapisovanje podatkov v pomnilnik ali disk. Obsežno se uporabljajo v sistemih baz podatkov, kot so MySQL, PostgreSQL in Redis ter datotečni sistemi, kot so NTFS, HFS + in ext4.

Omrežni izrazi, topologija