logo

TechCodeview

Komplett binært tre

Vi vet en tre er en ikke-lineær datastruktur. Den har ingen begrensning på antall barn. ENHva er et komplett binært tre?

Et komplett binært tre er en spesiell type binært tre der alle nivåene i treet er fylt fullstendig bortsett fra nodene på laveste nivå som er fylt fra så venstre som mulig.



Komplett binært tre

Litt terminologi for Complete Binary Tree:

  • Rot – Node der ingen kant kommer fra overordnet. Eksempel - node A
  • Barn – Node som har en innkommende kant kalles barn. Eksempel - nodene B, F er barnet til henholdsvis A og C.
  • Søsken – Noder som har samme forelder er søsken. Eksempel- D, E er søsken da de har samme forelder B.
  • Grad av en node – Antall barn av en bestemt forelder. Eksempel- Graden av A er 2 og graden av C er 1. Graden av D er 0.
  • Interne/Eksterne noder – Bladnoder er eksterne noder og ikke-bladnoder er interne noder.
  • Nivå – Tell noder i en bane for å nå en destinasjonsnode. Eksempel- Nivået til node D er 2 ettersom nodene A og B danner banen.
  • Høyde – Antall kanter for å nå destinasjonsnoden, roten er i høyden 0. Eksempel – Høyden på noden E er 2 siden den har to kanter fra roten.

Egenskaper til komplett binært tre:

  • Et komplett binært tre sies å være et skikkelig binært tre der alle bladene har samme dybde.
  • I et komplett binært tre antall noder i dybden d er 2 d .
  • I et komplett binært tre med n noder høyden på treet er log(n+1) .
  • Alle nivåene bortsett fra det siste nivået er helt fulle.

Perfekt binært tre vs komplett binært tre:

Et binært tre med høyden 'h' med maksimalt antall noder er a perfekt binært tre.
For en gitt høyde h , er maksimalt antall noder 2 h+1 -1 .

EN fullstendig binært tre med høyde h er et perfekt binært tre opp til høyden h-1 , og i det siste nivået lagres elementer i venstre til høyre rekkefølge.



Eksempel 1:

Et binært tre

Høyden på det gitte binære treet er 2 og maksimalt antall noder i det treet er n= 2h+1-1 = 22+1-1 = 23-1 = 7 .
Derfor kan vi konkludere med at det er det et perfekt binært tre .
Nå for et komplett binært tre, det er fullt opp til høyden h-1 dvs.; 1, og de siste nivåelementene lagres i venstre til høyre rekkefølge. Derfor er det også et komplett binært tre. Her er representasjonen av elementer når de er lagret i en matrise



Element lagret i en matrise nivå for nivå

I matrisen lagres alle elementene kontinuerlig.

Eksempel 2:

b+ trær

Et binært tre

Høyden på det gitte binære treet er 2 og maksimalt antall noder som skal være der er 2h+1– 1 = 22+1– 1 = 23– 1 = 7 .
Men antall noder i treet er 6 . Derfor er det ikke et perfekt binært tre .
Nå for et komplett binært tre, det er fullt opp til høyden h-1 dvs.; 1 , og det siste nivåelementet lagres i venstre til høyre rekkefølge. Derfor er dette en komplett binært tre . Lagre elementet i en matrise, og det vil være som;

Element lagret i en matrise nivå for nivå

Eksempel 3:

hvordan konvertere str til int

Et binært tre

Høyden på det binære treet er 2 og det maksimale antallet noder som kan være der er 7, men det er bare 5 noder, derfor er det ikke et perfekt binært tre .
I tilfelle av et komplett binært tre, ser vi at i det siste nivået er ikke elementene fylt fra venstre til høyre rekkefølge. Sånn er det ikke et komplett binært tre .

Element lagret i en matrise nivå for nivå

Elementene i matrisen er ikke kontinuerlige.

Fullt binært tre vs komplett binært tre:

For et fullt binært tre har hver node enten 2 barn eller 0 barn.

Eksempel 1:

Et binært tre

I det gitte binære treet er det ingen node som har grad 1, enten 2 eller 0 barn for hver node, derfor er det et fullt binært tre .

For et komplett binært tre lagres elementer i nivå for nivå og ikke fra venstre side på det siste nivået. Derfor er dette ikke et komplett binært tre . Matriserepresentasjonen er:

Element lagret i en matrise nivå for nivå

Eksempel 2:

Et binært tre

I det gitte binære treet er det ingen node med grad 1. Hver node har en grad på enten 2 eller 0. Derfor er det en fullt binært tre .

For et komplett binært tre, lagres elementene på nivå for nivå og fylles ut fra venstre side av det siste nivået. Derfor dette a komplett binært tre . Nedenfor er matrisepresentasjonen av treet:

Element lagret i en matrise nivå for nivå

Eksempel 3:

Et binært tre

I den gitte binære trenoden har B grad 1 som bryter med egenskapen til fullt binært tre, derfor er det ikke et fullt binært tre

stabel i java

For et komplett binært tre, lagres elementene nivå for nivå måte og fylt fra venstre side av siste nivå. Derfor er dette en komplett binært tre . Matriserepresentasjon av det binære treet er:

Element lagret i en matrise nivå for nivå

Eksempel 4:

et binært tre

I den gitte binære trenoden har C grad 1 som bryter med egenskapen til et fullt binært tre, derfor er det ikke et fullt binært tre

java prøv catch

For et komplett binært tre, lagres elementene nivå for nivå måte og fylt fra venstre side av siste nivå. Her bryter node E betingelsen. Derfor er dette ikke et komplett binært tre .

Oppretting av komplett binært tre:

Vi vet en komplett binært tre er et tre der bortsett fra det siste nivået (si l )alle de andre nivåene har ( 2l ) noder og nodene er oppstilt fra venstre til høyre side.
Det kan representeres ved hjelp av en matrise. Hvis forelderen er det indeks Jeg så det venstre barnet er kl 2i+1 og det rette barnet er på 2i+2 .

Komplett binært tre og dets matrisepresentasjon

Algoritme:

For opprettelsen av en Komplett binært tre , vi krever en Trinn 1: Initialiser roten med en ny node når treet er tomt.

Steg 2: Hvis treet ikke er tomt, hent frontelementet

  • Hvis frontelementet ikke har et venstre underordnet, sett det venstre barnet til en ny node
  • Hvis det riktige barnet ikke er til stede, sett det riktige barnet som en ny node

Trinn 3: Hvis noden har begge barna da pop det fra køen.

Trinn 4: Sett de nye dataene i kø.

Illustrasjon:

Vurder matrisen nedenfor:

1. Det første elementet vil roten (verdi ved indeks = 0 )

lenge til int java

A er tatt som rot

2. Det neste elementet (ved indeks = 1 ) vil være venstre og tredje element (indeks = 2 ) vil være rett barn av rot

B som venstre barn og D som høyre barn

3. fjerde (indeks = 3 ) og femte element (indeks = 4 ) vil være venstre og høyre barn til B-noden

E og F er venstre og høyre barn av B

4. Neste element (indeks = 5 ) vil bli igjen underordnet av noden D

G er gjort til venstre barn av D-noden

Dette er hvordan komplett binært tre opprettes.

Gjennomføring: For implementering av å bygge et komplett binært tre fra nivåordregjennomgang er gitt inn denne posten .

Anvendelse av det komplette binære treet:

  • Heap Sorter
  • Heapsorteringsbasert datastruktur

Sjekk om et gitt binært tre er komplett eller ikke: Følg denne posten for å sjekke om det gitte binære treet er komplett eller ikke.