Vodnik za binarna drevesa za začetnike

Če ste opravili tečaj podatkovnih struktur na stopnji računalništva ali ste programer samouk, obstaja velika verjetnost, da ste naleteli na izraz "binarna drevesa". Čeprav se morda slišijo nekoliko premočno in zapleteno, je koncept binarnega drevesa precej preprost.

Preberite, ko seciramo binarna drevesa, in zakaj so nujen temeljni koncept za programerje.

Kaj so binarna drevesa?

Binarna drevesa so med prvimi podatkovnimi strukturami, ki jih študentje učijo na tečaju podatkovnih struktur. Binarno drevo je sestavljeno iz številnih vozlišč in vsako vozlišče binarnega drevesa vsebuje dva kazalca, ki označujeta levo in desno podrejeno podatkovno vozlišče.

Prvo vozlišče v binarnem drevesu se imenuje "koren". Vozlišča zadnje ravni na drevesu se imenujejo listi.

Vsako vozlišče vsebuje podatkovni element in dva kazalca vozlišča. Prazno binarno drevo je predstavljeno z ničelnim kazalcem. Kot ste morda že ugotovili, imajo lahko binarna drevesa le dva otroka (od tod tudi ime).

Vrste binarnih drevesnih struktur

Glede na način postavitve vozlišč obstaja več različnih binarnih drevesnih struktur. Binarno drevo se imenuje polno binarno drevo, kadar ima vsako vozlišče v drevesu nič ali dva otroka. V popolnem binarnem drevesu imajo vsa vozlišča dva otroka in listi so vsi na isti globini.

Povezano: Najboljši načini za brezplačno kodiranje

Celotno binarno drevo ima vozlišča napolnjena na vseh ravneh, z izjemo zadnje ravni. V popolnih binarnih drevesih so vozlišča koncentrirana na levi strani korena. Druga pogosta struktura je uravnoteženo binarno drevo; v tej strukturi se morata višini desnega in levega poddrevesa razlikovati največ za eno. Prav tako je treba uravnotežiti levo in desno poddrevo.

Pomembno je omeniti, da je višina uravnoteženega binarnega drevesa O (logn), kjer je n število vozlišč v drevesu.

V nekaterih primerih, če ima vsako vozlišče le enega levega ali desnega otroka, lahko binarno drevo postane popačeno binarno drevo. Nato se bo obnašal kot povezan seznam, takšna drevesa se imenujejo tudi degenerirano drevo.

Kaj so binarna iskalna drevesa?

Binarno iskalno drevo (BST) je v bistvu urejeno binarno drevo s posebno lastnostjo, znano kot lastnost "binarno iskalno drevo". Lastnost BST pomeni, da so vozlišča z vrednostjo ključa manjšo od korena postavljena v levo poddrevo, vozlišča z vrednostjo ključa večjo od korena pa so del desnega poddreva.

Lastnost BST mora biti resnična za vsako naslednje nadrejeno vozlišče v drevesu.

Binarna drevesa za iskanje ponujajo hitro vstavljanje in iskanje. Operacije vstavljanja, brisanja in iskanja imajo najslabšo časovno zapletenost O (n), ki je podobna povezanemu seznamu.

Prednosti binarnih dreves

Binarna drevesa ponujajo številne prednosti, zato ostajajo zelo uporabna struktura podatkov. Uporabljajo se lahko za prikaz strukturnih razmerij in hierarhij v nizu podatkov. Še pomembneje je, da binarna drevesa omogočajo učinkovito iskanje, brisanje in vstavljanje.

Prav tako je zelo enostavno implementirati in vzdrževati binarno drevo. Binarno drevo ponuja programerjem prednosti urejenega niza in povezanega seznama; iskanje v binarnem drevesu je tako hitro kot v razvrščeni matriki, operacije vstavljanja ali brisanja pa enako učinkovite kot na povezanih seznamih.

Binarna drevesa so pomembna podatkovna struktura

Binarna drevesa so zelo pomembna struktura podatkov in ključnega pomena je, da jih programerji udobno uporabljajo v svojih programih. Pogosto anketarji postavljajo preproste težave z binarnim drevesom, kot so prehodi, največja globina, zrcaljenje itd.

Priporočamo razumevanje koncepta binarnega drevesa in poznavanje tipičnih težav pri intervjuju.

TreeViz: Enostaven način za vizualizacijo podatkovnih struktur

Preberite Naprej

O avtorju