Nøkkelforskjell – binært tre vs binært søketre
En datastruktur er en systematisk måte å organisere data på for å bruke dem effektivt. Ordning av data ved hjelp av datastrukturen bør redusere kjøretiden eller utførelsestiden. Datastrukturen bør også kreve en minimumsmengde minne. Noen ganger kan dataene ordnes i en trestruktur. Et tre representerer en node forbundet med kanter. Den øverste noden er roten. Hver node kan ha maksim alt to noder. De er kjent som barnenoder. Noden til venstre for den overordnede noden er den venstre barnenoden, mens noden til høyre for den overordnede noden er den høyre noden. Det binære treet og det binære søketreet er to tredatastrukturer. Et binært tre er en type datastruktur der hver overordnet node kan ha maksim alt to underordnede noder. Det binære søketreet er et binært tre der venstre underordnede kun inneholder noder med verdier mindre enn eller lik overordnet node, og hvor høyre underordnet kun inneholder noder med verdier større enn til overordnet node. Det er den viktigste forskjellen. I motsetning til datastrukturer som matriser, har ikke det binære treet og det binære søketreet en øvre grense for lagring av data.
Hva er binært tre?
Når du ordner dataene i en trestruktur, er noden øverst i treet kjent som rotnoden. Det kan bare være én rot for hele treet. Enhver node unntatt rotnoden har en kant oppover til en node. Det kalles overordnet node. Noden under den overordnede koden kalles dens underordnede node. Hver overordnet node kan ha maksim alt to underordnede noder. De blir referert til som en venstre barnnode og høyre barnenode. En node uten noen barnenode kalles en bladnode. Det er ingen spesifikk måte å ordne data i det binære treet. Det er en bane fra rotnode til hver node.
Figur 01: Eksempel på binært tre
Ovenfor er et eksempel på et binært tre. Element 2, i toppen av treet, er roten. Hver node har maksim alt to noder. Hvis et tre inneholder noen løkker eller hvis en node inneholder mer enn to noder, kan det ikke klassifiseres som et binært tre. For å gå fra den ene noden til den andre, er det alltid én vei. Undernodene til rotnoden 2 er 7 og 5. Det er også mulig for en node å ikke ha noder. Men enhver node kan ikke ha mer enn to noder. Det høyre elementet i roten er 5. At element 5 er overordnet node for underordnet node 9. Noden 4 og 11 har ingen underordnede elementer. Derfor er de bladnoder.
Det binære treet brukes til å lagre data i hierarkisk rekkefølge. Det ligner på filstrukturen til datamaskinen. Datastrukturen som en matrise kan lagre en bestemt mengde data. Men i et binært tre er det ingen øvre grense for antall noder.
Hva er binært søketre?
Et binært søketre er en binær tredatastruktur. I likhet med et binært tre, kan det binære søketreet også ha to noder. Enhver node unntatt rotnoden har en kant oppover til en node. Det kalles overordnet node. Noden under en gitt sammenkoblet med kanten nedover kalles barnenoden. En node uten noen barnenode kalles en bladnode. Hver overordnet node kan ha maksim alt to noder. Det er underordnede noder som refererer til en venstre underknute og høyre underknute. Det øverste elementet kalles rotnoden. Det venstre barnet inneholder bare noder med verdier mindre enn eller lik den overordnede noden. Det høyre barnet inneholder bare noder med verdier større enn eller lik overordnet node.
Figur 02: Eksempel på binært søketre
Elementet 8 er det øverste elementet. Derfor er det rotnoden. Hvis 3 er en overordnet node, er 1 og 6 barnenoder. 1-en er den venstre barnenoden mens 6 er den høyre barnenoden. Det venstre barnet inneholder verdier mindre enn eller lik den overordnede noden. Når 3 er overordnet node, skal venstre side ha et element som er mindre enn eller lik 3. I dette eksemplet er det 1. Høyre underordnet inneholder kun noder med verdier større enn overordnet node. Når 3 er den overordnede noden, bør den høyre underordnede noden ha en høyere verdi enn 3. I dette eksemplet er den 6. På samme måte er det en viss rekkefølge for å ordne hvert dataelement i et binært søketre. Det er en datastruktur som gir en effektiv måte å utføre sortering, henting og søk på data.
Hva er likhetene mellom binært tre og binært søketre?
- Både binært tre og binært søketre er hierarkiske datastrukturer.
- Både binært tre og binært søketre har en rot.
- Både binært tre og binært søketre kan ha maksim alt to underordnede noder.
Hva er forskjellen mellom binært tre og binært søketre?
Binary Tree vs Binary Search Tree |
|
| Et binært tre er en type datastruktur der hver overordnede node kan ha maksim alt to underordnede noder. | Det binære søketreet er et binært tre der venstre underordnede kun inneholder noder med verdier mindre enn eller lik overordnet node, og der høyre underordnede kun inneholder noder med verdier større enn overordnet node. |
| Dataordningsbestilling | |
| Et binært tre har ikke en spesifikk rekkefølge for å ordne dataelementene. | Et binært søketre har en spesifikk rekkefølge for å ordne dataelementene. |
| Usage | |
| Et binært tre brukes som et effektivt oppslag av data og informasjon i en trestruktur. | Et binært søketre brukes for å sette inn, slette og søke i data. |
Sammendrag – binært tre vs binært søketre
En datastruktur er en måte å organisere data på. Noen ganger kan dataene ordnes i en trestruktur. To av dem er binært tre og binært søketre. Denne artikkelen diskuterte forskjellen mellom binært tre og det binære søketreet. Et binært tre er en type datastruktur der hver overordnet node kan ha maksim alt to underordnede noder. Det binære søketreet er et binært tre der venstre underordnede kun inneholder noder med verdier mindre enn eller lik overordnet node, og der høyre underordnede kun inneholder noder med verdier større enn overordnet node.
Last ned PDF-en av Binary Tree vs Binary Search Tree
Du kan laste ned PDF-versjonen av denne artikkelen og bruke den til offline-formål i henhold til sitat. Last ned PDF-versjonen her: Difference Between Binary Tree and Binary Search Tree
