TechCodeview

Binarno stablo znači da čvor može imati najviše dva djeteta. Ovdje samo binarno ime sugerira da je 'dva'; prema tome, svaki čvor može imati ili 0, 1 ili 2 djece.

Razmotrimo binarno stablo kroz primjer.

Gornje stablo je binarno stablo jer svaki čvor sadrži najviše dva djeteta. Logički prikaz gornjeg stabla dan je u nastavku:

U gornjem stablu, čvor 1 sadrži dva pokazivača, tj. lijevi i desni pokazivač koji pokazuju na lijevi odnosno desni čvor. Čvor 2 sadrži oba čvora (lijevi i desni čvor); dakle, ima dva pokazivača (lijevo i desno). Čvorovi 3, 5 i 6 su čvorovi lista, tako da svi ti čvorovi sadrže NULL pokazivač na lijevom i desnom dijelu.

Svojstva binarnog stabla

• Na svakoj razini od i, maksimalni broj čvorova je 2ⁱ.
• Visina stabla je definirana kao najduži put od korijenskog čvora do lisnog čvora. Gore prikazano stablo ima visinu jednaku 3. Stoga je maksimalan broj čvorova na visini 3 jednak (1+2+4+8) = 15. Općenito, najveći mogući broj čvorova na visini h je (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Najmanji mogući broj čvorova na visini h jednak je h+1 .
• Ako je broj čvorova minimalan, tada bi visina stabla bila maksimalna. Obrnuto, ako je broj čvorova maksimalan, tada bi visina stabla bila minimalna.

Ako postoji 'n' broj čvorova u binarnom stablu.

Minimalna visina može se izračunati kao:

Kao što to znamo,

n = 2^h+1-1

n+1 = 2^h+1

Uzimajući trupac s obje strane,

normalizacija u bazi podataka

log₂(n+1) = log2(2^h+1)

log₂(n+1) = h+1

h = log₂(n+1) - 1

Maksimalna visina može se izračunati kao:

Kao što to znamo,

n = h+1

h= n-1

Vrste binarnog stabla

Postoje četiri vrste binarnog stabla:

Potpuno/ ispravno/ strogo binarno stablo Kompletno binarno stablo Savršeno binarno stablo Degenerirano binarno stablo Uravnoteženo binarno stablo

1. Potpuno/ ispravno/ strogo binarno stablo

Potpuno binarno stablo poznato je i kao striktno binarno stablo. Stablo se može smatrati punim binarnim stablom samo ako svaki čvor mora sadržavati 0 ili 2 djeteta. Potpuno binarno stablo također se može definirati kao stablo u kojem svaki čvor mora sadržavati 2 djeteta osim lisnih čvorova.

Pogledajmo jednostavan primjer punog binarnog stabla.

U gornjem stablu možemo primijetiti da svaki čvor sadrži nula ili dva djeteta; stoga je to puno binarno stablo.

Svojstva punog binarnog stabla

• Broj lisnih čvorova jednak je broju unutarnjih čvorova plus 1. U gornjem primjeru, broj unutarnjih čvorova je 5; stoga je broj čvorova lista jednak 6.
• Maksimalni broj čvorova jednak je broju čvorova u binarnom stablu, tj. 2^h+1-1.
• Najmanji broj čvorova u punom binarnom stablu je 2*h-1.
• Minimalna visina punog binarnog stabla je log₂(n+1) - 1.
• Maksimalna visina punog binarnog stabla može se izračunati kao:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Kompletno binarno stablo

Potpuno binarno stablo je stablo u kojem su svi čvorovi potpuno popunjeni osim posljednje razine. U posljednjoj razini, svi čvorovi moraju biti što je moguće lijevo. U potpunom binarnom stablu čvorove treba dodavati slijeva.

Kreirajmo potpuno binarno stablo.

kako dobiti iphone emojije na android

Gornje stablo je potpuno binarno stablo jer su svi čvorovi u potpunosti popunjeni, a svi čvorovi na posljednjoj razini prvo se dodaju s lijeve strane.

Svojstva potpunog binarnog stabla

• Maksimalan broj čvorova u kompletnom binarnom stablu je 2^h+1- 1.
• Najmanji broj čvorova u kompletnom binarnom stablu je 2^h.
• Minimalna visina potpunog binarnog stabla je log₂(n+1) - 1.
• Maksimalna visina kompletnog binarnog stabla je

Savršeno binarno stablo

Stablo je savršeno binarno stablo ako svi unutarnji čvorovi imaju 2 djece, a svi lisni čvorovi su na istoj razini.

Pogledajmo jednostavan primjer savršenog binarnog stabla.

Donje stablo nije savršeno binarno stablo jer svi čvorovi listova nisu na istoj razini.

Napomena: Sva savršena binarna stabla su potpuna binarna stabla kao i potpuna binarna stabla, ali obrnuto nije točno, tj. sva potpuna binarna stabla i puna binarna stabla su savršena binarna stabla.

Degenerirano binarno stablo

Degenerirano binarno stablo je stablo u kojem svi unutarnji čvorovi imaju samo jednu djecu.

Razumimo degenerirano binarno stablo kroz primjere.

Gornje stablo je degenerirano binarno stablo jer svi čvorovi imaju samo jedno dijete. Također je poznato kao desno zakrivljeno stablo jer svi čvorovi imaju samo desno dijete.

oštar kut

Gore navedeno stablo također je degenerirano binarno stablo jer svi čvorovi imaju samo jedno dijete. Također je poznato kao lijevo zakošeno stablo jer svi čvorovi imaju samo lijevo dijete.

Uravnoteženo binarno stablo

Uravnoteženo binarno stablo je stablo u kojem se i lijevo i desno stablo razlikuju za najviše 1. Na primjer, AVL i Crveno-crno drveće su uravnoteženo binarno stablo.

Razumimo uravnoteženo binarno stablo kroz primjere.

Gornje stablo je uravnoteženo binarno stablo jer je razlika između lijevog podstabla i desnog podstabla nula.

Gore navedeno stablo nije uravnoteženo binarno stablo jer je razlika između lijevog podstabla i desnog podstabla veća od 1.

Implementacija binarnog stabla

Binarno stablo implementirano je uz pomoć pokazivača. Prvi čvor u stablu predstavljen je korijenskim pokazivačem. Svaki čvor u stablu sastoji se od tri dijela, tj. podataka, lijevog i desnog pokazivača. Da bismo stvorili binarno stablo, prvo moramo stvoriti čvor. Stvorit ćemo korisnički definirani čvor kao što je prikazano u nastavku:

 struct node { int data, struct node *left, *right; } 

U gornjoj strukturi, podaci je vrijednost, lijevi pokazivač sadrži adresu lijevog čvora, i desni pokazivač sadrži adresu desnog čvora.

Program binarnog stabla u C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Gornji kod rekurzivno poziva funkciju create() i stvara novi čvor pri svakom rekurzivnom pozivu. Kada se kreiraju svi čvorovi, formira se binarna struktura stabla. Proces posjećivanja čvorova poznat je kao obilazak stabla. Postoje tri vrste obilazaka koji se koriste za posjet čvoru:

• Prelazak po neredu
• Prolazak unaprijed
• Prolaz poštanskih naloga