nyckelskillnad – binärt träd vs binärt sökträd
En datastruktur är ett systematiskt sätt att organisera data för att använda dem effektivt. Att ordna data med hjälp av datastrukturen bör minska körtiden eller exekveringstiden. Dessutom bör datastrukturen kräva en minimal mängd minne. Ibland kan data ordnas i en trädstruktur. Ett träd representerar en nod som är förbunden med kanter. Den översta noden är roten. Varje nod kan ha maxim alt två noder. De är kända som barnnoder. Noden till vänster om föräldernoden är den vänstra barnnoden medan noden till höger om föräldernoden är den högra noden. Det binära trädet och det binära sökträdet är två träddatastrukturer. Ett binärt träd är en typ av datastruktur där varje föräldernod kan ha högst två underordnade noder. Det binära sökträdet är ett binärt träd där det vänstra underordnade endast innehåller noder med värden mindre än eller lika med föräldernoden, och där det högra underordnade endast innehåller noder med värden större än föräldernoden. Det är den viktigaste skillnaden. Till skillnad från datastrukturer som arrayer har det binära trädet och det binära sökträdet ingen övre gräns för att lagra data.
Vad är binärt träd?
När du ordnar data i en trädstruktur kallas noden högst upp i trädet rotnoden. Det kan bara finnas en rot för hela trädet. Vilken nod som helst utom rotnoden har en kant uppåt till en nod. Det kallas föräldranoden. Noden under föräldrakoden kallas dess underordnade nod. Varje föräldernod kan ha maxim alt två underordnade noder. De kallas en vänster barnnod och höger barnnod. En nod utan någon barnnod kallas lövnod. Det finns inget specifikt sätt att ordna data i det binära trädet. Det finns en väg från rotnod till varje nod.
Figur 01: Exempel på binärt träd
Ovan är ett exempel på ett binärt träd. Elementet 2, i toppen av trädet, är roten. Varje nod har maxim alt två noder. Om ett träd innehåller några loopar eller om en nod innehåller fler än två noder, kan det inte klassificeras som ett binärt träd. För att gå från en nod till en annan finns det alltid en väg. Undernoderna för rotnod 2 är 7 och 5. Det är också möjligt för en nod att inte ha några noder. Men vilken nod som helst kan inte ha fler än två noder. Det högra elementet i roten är 5. Det elementet 5 är modernoden för undernod 9. Noden 4 och 11 har inga underordnade element. Därför är de lövnoder.
Det binära trädet används för att lagra data i hierarkisk ordning. Det liknar filstrukturen på datorn. Datastrukturen som en array kan lagra en specifik mängd data. Men i ett binärt träd finns det ingen övre gräns för antalet noder.
Vad är binärt sökträd?
Ett binärt sökträd är en binär träddatastruktur. I likhet med ett binärt träd kan det binära sökträdet också ha två noder. Vilken nod som helst utom rotnoden har en kant uppåt till en nod. Det kallas föräldranoden. Noden under en given förbunden med sin kant nedåt kallas dess undernod. En nod utan någon barnnod kallas lövnod. Varje föräldernod kan ha maxim alt två noder. Det finns barnnoder som hänvisar till en vänster undernod och en höger undernod. Det översta elementet kallas rotnoden. Det vänstra barnet innehåller endast noder med värden mindre än eller lika med den överordnade noden. Det högra underordnade elementet innehåller bara noder med värden större än eller lika med den överordnade noden.
Figur 02: Exempel på binärt sökträd
Elementet 8 är det översta elementet. Därför är det rotnoden. Om 3 är en överordnad nod, är 1 och 6 barnnoder. 1:an är den vänstra undernoden medan 6:an är den högra undernoden. Det vänstra barnet innehåller värden som är mindre än eller lika med den överordnade noden. När 3 är föräldranoden, bör den vänstra sidan ha ett element som är mindre än eller lika med 3. I det här exemplet är det 1. Det högra underordnade elementet innehåller bara noder med värden större än föräldernoden. När 3 är föräldernoden, bör den högra underordnade noden ha ett högre värde än 3. I detta exempel är det 6. Likaså finns det en viss ordning för att ordna varje dataelement i ett binärt sökträd. Det är en datastruktur som ger ett effektivt sätt att utföra sortering, hämtning och sökning av data.
Vilka är likheterna mellan binärt träd och binärt sökträd?
- Både binärt träd och binärt sökträd är hierarkiska datastrukturer.
- Både binärt träd och binärt sökträd har en rot.
- Både binärt träd och binärt sökträd kan ha maxim alt två underordnade noder.
Vad är skillnaden mellan binärt träd och binärt sökträd?
Binary Tree vs Binary Search Tree |
|
| Ett binärt träd är en typ av datastruktur där varje föräldernod kan ha maxim alt två underordnade noder. | Det binära sökträdet är ett binärt träd där det vänstra underordnade trädet endast innehåller noder med värden mindre än eller lika med föräldernoden, och där det högra underordnade endast innehåller noder med värden större än föräldernoden. |
| Data Arranging Order | |
| Ett binärt träd har inte en specifik ordning för att ordna dataelementen. | Ett binärt sökträd har en specifik ordning för att ordna dataelementen. |
| Användning | |
| Ett binärt träd används som en effektiv uppslagning av data och information i en trädstruktur. | Ett binärt sökträd används för att infoga, ta bort och söka i data. |
Sammanfattning – Binary Tree vs Binary Search Tree
En datastruktur är ett sätt att organisera data. Ibland kan data ordnas i en trädstruktur. Två av dem är binärt träd och det binära sökträdet. Den här artikeln diskuterade skillnaden mellan binärt träd och det binära sökträdet. Ett binärt träd är en typ av datastruktur där varje föräldernod kan ha högst två underordnade noder. Det binära sökträdet är ett binärt träd där det vänstra underordnade endast innehåller noder med värden mindre än eller lika med föräldernoden, och där det högra underordnade endast innehåller noder med värden större än föräldernoden.
Ladda ner PDF-filen för Binary Tree vs Binary Search Tree
Du kan ladda ner PDF-versionen av den här artikeln och använda den för offlineändamål enligt citat. Ladda ner PDF-versionen här: Difference Between Binary Tree och Binary Search Tree
