Nøgleforskel – binært træ vs binært søgetræ
En datastruktur er en systematisk måde at organisere data på for at bruge dem effektivt. Arrangering af data ved hjælp af datastrukturen bør reducere køretiden eller eksekveringstiden. Desuden bør datastrukturen kræve et minimum af hukommelse. Nogle gange kan dataene arrangeres i en træstruktur. Et træ repræsenterer en knude forbundet med kanter. Den øverste knude er roden. Hver node kan maksim alt have to noder. De er kendt som børneknuder. Noden til venstre for moderknuden er den venstre underordnede node, mens noden til højre for moderknuden er den højre node. Det binære træ og det binære søgetræ er to trædatastrukturer. Et binært træ er en type datastruktur, hvor hver overordnet node højst kan have to underordnede noder. Det binære søgetræ er et binært træ, hvor det venstre underordnede kun indeholder noder med værdier mindre end eller lig med den overordnede knude, og hvor det højre underordnede kun indeholder knudepunkter med værdier, der er større end til den overordnede knude. Det er den vigtigste forskel. I modsætning til datastrukturer såsom arrays, har det binære træ og det binære søgetræ ikke en øvre grænse for lagring af data.
Hvad er binært træ?
Når du arrangerer dataene i en træstruktur, er knudepunktet i toppen af træet kendt som rodknuden. Der kan kun være én rod til hele træet. Enhver knude undtagen rodnoden har en kant opad til en knude. Det kaldes forældreknudepunktet. Noden under forældrekoden kaldes dens underordnede node. Hver overordnet node kan maksim alt have to underordnede noder. De omtales som en venstre børneknude og højre børneknude. En node uden nogen underordnet node kaldes en bladknude. Der er ingen specifik måde at arrangere data i det binære træ. Der er en sti fra rodnode til hver node.
Figur 01: Eksempel på binært træ
Ovenfor er et eksempel på et binært træ. Elementet 2, i toppen af træet, er roden. Hver node har maksim alt to noder. Hvis et træ indeholder nogen sløjfer, eller hvis en node indeholder mere end to noder, kan det ikke klassificeres som et binært træ. For at gå fra den ene node til den anden er der altid én vej. De underordnede noder af rodknude 2 er 7 og 5. Det er også muligt for en node ikke at have nogen noder. Men enhver node kan ikke have mere end to noder. Det højre element i roden er 5. Det element 5 er forældreknudepunktet for underknudepunkt 9. Knudepunktet 4 og 11 har ingen underordnede elementer. Derfor er de bladknuder.
Det binære træ bruges til at gemme data i hierarkisk rækkefølge. Det ligner filstrukturen på computeren. Datastrukturen som et array kan lagre en bestemt mængde data. Men i et binært træ er der ingen øvre grænse for antallet af noder.
Hvad er binært søgetræ?
Et binært søgetræ er en binær trædatastruktur. I lighed med et binært træ kan det binære søgetræ også have to noder. Enhver knude undtagen rodnoden har en kant opad til en knude. Det kaldes forældreknudepunktet. Noden under en given, der er forbundet med sin kant nedad, kaldes dens underknude. En node uden nogen underordnet node kaldes en bladknude. Hver overordnet node kan maksim alt have to noder. Der er underordnede knudepunkter, der henviser til en venstre underknude og en højre underknude. Det øverste element kaldes rodknuden. Det venstre barn indeholder kun noder med værdier mindre end eller lig med den overordnede node. Det højre underordnede indeholder kun noder med værdier større end eller lig med overordnet node.
Figur 02: Eksempel på binært søgetræ
Elementet 8 er det øverste element. Derfor er det rodnoden. Hvis 3 er en overordnet node, så er 1 og 6 underordnede noder. 1'eren er den venstre underordnede knude, mens 6'eren er den højre underordnede knude. Det venstre barn indeholder værdier mindre end eller lig med den overordnede node. Når 3 er den overordnede node, skal venstre side have et element, der er mindre end eller lig med 3. I dette eksempel er det 1. Det højre underordnede element indeholder kun noder med værdier større end den overordnede node. Når 3 er den overordnede node, skal den højre underordnede node have en højere værdi end 3. I dette eksempel er den 6. Ligeledes er der en bestemt rækkefølge til at arrangere hvert dataelement et binært søgetræ. Det er en datastruktur, der giver en effektiv måde at udføre sortering, hentning og søgning i data på.
Hvad er lighederne mellem binært træ og binært søgetræ?
- Både binært træ og binært søgetræ er hierarkiske datastrukturer.
- Både binært træ og binært søgetræ har en rod.
- Både binært træ og binært søgetræ kan have maksim alt to underordnede noder.
Hvad er forskellen mellem binært træ og binært søgetræ?
Binært træ vs binært søgetræ |
|
| Et binært træ er en type datastruktur, hvor hver overordnet node maksim alt kan have to underordnede noder. | Det binære søgetræ er et binært træ, hvor det venstre underordnede kun indeholder noder med værdier mindre end eller lig med den overordnede knude, og hvor det højre underordnede kun indeholder knudepunkter med værdier, der er større end den overordnede knude. |
| Dataordningsordre | |
| Et binært træ har ikke en specifik rækkefølge til at arrangere dataelementerne. | Et binært søgetræ har en specifik rækkefølge til at arrangere dataelementerne. |
| Usage | |
| Et binært træ bruges som et effektivt opslag af data og information i en træstruktur. | Et binært søgetræ bruges til at indsætte, slette og søge i data. |
Opsummering – Binært træ vs binært søgetræ
En datastruktur er en måde at organisere data på. Nogle gange kan dataene arrangeres i en træstruktur. To af dem er binært træ og det binære søgetræ. Denne artikel diskuterede forskellen mellem binært træ og det binære søgetræ. Et binært træ er en type datastruktur, hvor hver overordnet node højst kan have to underordnede noder. Det binære søgetræ er et binært træ, hvor det venstre underordnede kun indeholder noder med værdier mindre end eller lig med moderknuden, og hvor det højre underordnede kun indeholder noder med værdier, der er større end den overordnede node.
Download PDF'en af Binary Tree vs Binary Search Tree
Du kan downloade PDF-versionen af denne artikel og bruge den til offline-formål i henhold til citatnotat. Download venligst PDF-versionen her: Forskellen mellem binært træ og binært søgetræ
