Vodič za binarna stabla za početnike

Ako ste pohađali tečaj o strukturi podataka na svom diplomu računarstva ili ste programer samouk, velika je vjerojatnost da ste naišli na pojam "Binarna stabla". Iako mogu zvučati pomalo nadmoćno i složeno, koncept binarnog stabla prilično je jednostavan.

Čitajte dalje dok seciramo binarna stabla i zašto su oni neophodan temeljni koncept za programere.

Što su binarna stabla?

Binarna stabla jedna su od prvih struktura podataka koje studenti uče na tečaju o strukturama podataka. Binarno stablo sastoji se od mnogo čvorova, a svaki čvor binarnog stabla sadrži dva pokazivača koji označavaju lijevi i desni podređeni čvor podataka.

Prvi čvor u binarnom stablu naziva se "korijen". Čvorovi posljednje razine na drvetu zovu se lišće.

Svaki čvor sadrži stavku podataka i dva pokazivača čvora. Prazno binarno stablo predstavljeno je nultim pokazivačem. Kao što ste možda već shvatili, binarna stabla mogu imati samo dvoje djece (otuda i naziv).

Vrste binarnih drvenih struktura

Postoji nekoliko različitih binarnih struktura stabla, ovisno o načinu postavljanja čvorova. Binarno stablo naziva se puno binarno stablo kada svaki čvor u stablu ima ili nulu ili dvoje djece. U savršenom binarnom stablu svi čvorovi imaju dvoje djece, a listovi su na istoj dubini.

Povezano: Najbolji načini da besplatno naučite kodirati

Potpuno binarno stablo ima čvorove ispunjene na svakoj razini, s izuzetkom posljednje razine. U potpunim binarnim stablima čvorovi su koncentrirani na lijevoj strani korijena. Druga uobičajena struktura je uravnoteženo binarno stablo; u ovoj strukturi visine desnog i lijevog podstabla moraju se razlikovati najviše za jedan. Također je potrebno da se lijevo i desno podstablo također moraju uravnotežiti.

Važno je napomenuti da je visina uravnoteženog binarnog stabla O (logn), gdje je n broj čvorova u stablu.

U nekim slučajevima, ako svaki čvor ima samo jedno lijevo ili desno dijete, tada binarno stablo može postati iskrivljeno binarno stablo. Tada će se ponašati kao povezani popis, takva se stabla nazivaju i degeneriranim stablom.

Što su binarna stabla pretraživanja?

Binarno stablo pretraživanja (BST) u biti je uređeno binarno stablo s posebnim svojstvom poznatim kao svojstvo "binarno stablo pretraživanja". Svojstvo BST znači da su čvorovi čija je vrijednost ključa manja od korijena smješteni u lijevo podstablo, a čvorovi čija je vrijednost ključa veća od korijena dio su desnog podstabla.

BST svojstvo mora biti točno za svaki sljedeći roditeljski čvor u stablu.

Binarna stabla pretraživanja nude brzo umetanje i pretraživanje. Operacije umetanja, brisanja i pretraživanja imaju složenost O (n) u najgorem slučaju, što je slično povezanom popisu.

Prednosti binarnog drveća

Binarna stabla nude mnoge prednosti zbog čega ostaju vrlo korisna struktura podataka. Mogu se koristiti za prikaz strukturnih odnosa i hijerarhija u skupu podataka. Što je još važnije, binarna stabla omogućuju učinkovito pretraživanje, brisanje i umetanje.

Također je vrlo jednostavno implementirati i održavati binarno stablo. Binarno stablo nudi programerima prednosti uređenog niza i povezanog popisa; pretraživanje u binarnom stablu jednako je brzo kao u sortiranom nizu, a operacije umetanja ili brisanja jednako su učinkovite kao i na povezanim popisima.

Binarna stabla važna su struktura podataka

Binarna stabla vrlo su važna struktura podataka i ključno je da ih programeri ugodno primjenjuju u svojim programima. Često anketari postavljaju jednostavne probleme s binarnim stablom, poput prelaska, najveće dubine, zrcaljenja itd.

Toplo preporučujemo razumijevanje koncepta binarnog stabla i upoznavanje s tipičnim problemima intervjua.

TreeViz: jednostavan način vizualizacije struktura podataka

Pročitajte Dalje

O autoru