TechCodeview

Først vil vi forstå binært tre og binært søketre separat, og så skal vi se på forskjellene mellom et binært tre og et binært søketre.

Hva er et binært tre?

EN Binært tre er enPeker til venstre barn:Den lagrer referansen til venstre underordnet node.Peker til rett barn:Den lagrer referansen til høyre underordnet node.Dataelement:Dataelementet er verdien av dataene som er lagret av noden.

Det binære treet kan representeres som:

I figuren ovenfor kan vi observere at hver node inneholder maksimalt 2 barn. Hvis en node ikke inneholder venstre eller høyre underordnede, vil verdien av pekeren med hensyn til det underordnede være NULL.

Grunnleggende terminologier som brukes i et binært tre er:

Rotnoden:Rotnoden er den første eller den øverste noden i et binært tre.Overordnet node:Når en node er koblet til en annen node gjennom kanter, er den noden kjent som en overordnet node. I et binært tre kan overordnet node ha maksimalt 2 barn.Barnnode:Hvis en node har sin forgjenger, er den noden kjent som en barn node .Bladknutepunkt:Noden som ikke inneholder noe barn kjent som en bladnode .Intern node:Noden som har minst 2 barn kjent som en intern node .Dybde av en node:Avstanden fra rotnoden til den gitte noden er kjent som a dybden til en node . Vi gir etiketter til alle nodene som rotnoden er merket med 0 da den ikke har noen dybde, barn av rotnodene er merket med 1, barn av rotbarnet er merket med 2.Høyde:Den lengste avstanden fra rotnoden til bladnoden er høyden på noden .

I et binært tre er det ett tre kjent som en perfekt binært tre . Det er en tre der alle interne noder må inneholde to noder, og alle bladnodene må være på samme dybde. Når det gjelder et perfekt binært tre, kan det totale antallet noder som finnes i et binært tre beregnes ved å bruke følgende ligning:

n = 2^m+1-1

hvor n er antall noder, m er dybden til en node.

Hva er et binært søketre?

EN Binært søketre er et tre som følger en eller annen rekkefølge for å ordne elementene, mens det binære treet ikke følger noen rekkefølge. I et binært søketre må verdien til venstre node være mindre enn overordnet node, og verdien til høyre node må være større enn overordnet node.

La oss forstå konseptet med et binært søketre gjennom eksempler.

I figuren ovenfor kan vi observere at verdien til rotnoden er 15, som er større enn verdien til alle nodene i det venstre undertreet. Verdien av rotnoden er mindre enn verdiene til alle nodene i et høyre undertre. Nå flytter vi til venstre underordnede av rotnoden. 10 er større enn 8 og mindre enn 12; det tilfredsstiller også egenskapen til det binære søketreet. Nå flytter vi til høyre underordnet av rotnoden; verdien 20 er større enn 17 og mindre enn 25; det tilfredsstiller også egenskapen til binært søketre. Derfor kan vi si at treet vist ovenfor er det binære søketreet.

Nå, hvis vi endrer verdien av 12 til 16 i det binære treet ovenfor, må vi finne ut om det fortsatt er et binært søketre eller ikke.

Verdien av rotnoden er 15, som er større enn 10, men mindre enn 16, så den tilfredsstiller ikke egenskapen til det binære søketreet. Derfor er det ikke et binært søketre.

Operasjoner på binært søketre

Vi kan utføre innsetting, sletting og søkeoperasjoner på det binære søketreet. La oss forstå hvordan et søk utføres på et binært søk. Det binære treet er vist nedenfor som vi må utføre søkeoperasjonen på:

Anta at vi må søke 10 i det binære treet ovenfor. For å utføre det binære søket vil vi vurdere alle heltallene i en sortert matrise. Først lager vi en komplett liste i et søkerom, og alle tallene vil eksistere i søkefeltet. Søkefeltet er markert med to pekere, dvs. start og slutt. Matrisen til det binære treet ovenfor kan representeres som

Først skal vi beregne det midterste elementet og sammenligne det midterste elementet med elementet som skal søkes. Midtelementet beregnes ved å bruke n/2. Verdien av n er 7; derfor er det midterste elementet 15. Det midterste elementet er ikke likt det søkte elementet, dvs. 10.

Merk: Hvis elementet som søkes er mindre enn midtelementet, vil søket utføres i venstre halvdel; ellers vil søking gjøres på høyre halvdel. Ved likestilling finnes elementet.

Siden elementet som skal søkes er mindre enn midtelementet, vil søkingen utføres på venstre array. Nå er søket redusert til det halve, som vist nedenfor:

Midtelementet i venstre array er 10, som er lik det søkte elementet.

Tidskompleksitet

I et binært søk er det n elementer. Hvis det midterste elementet ikke er lik det søkte elementet, reduseres søkerommet til n/2, og vi vil fortsette å redusere søkerommet med n/2 til vi fant elementet. I hele reduksjonen, hvis vi flytter fra n til n/2 til n/4 og så videre, vil det ta logg₂n trinn.

Forskjeller mellom binært tre og binært søketre