Skillnad mellan binärt träd och binärt sökträd

Huvudskillnad - binärt träd mot Binärt sökträd
 

En datastruktur är ett systematiskt sätt att organisera data för att använda det effektivt. Att ordna data med datastrukturen bör minska körtiden eller körtiden. 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 förbunden med kanter. Den högsta noden är rot. Varje nod kan ha högst två noder. De är kända som barnnoder. Noden till vänster om parentnoden är den vänstra barnnoden medan noden till höger om parentnoden är den högra noden. Binärt träd och binärt sökträd är två träddatastrukturer. Ett binärt träd är en typ av datastruktur där varje föräldraknut kan ha högst två barnknutor. Binärt sökträd är ett binärt träd, där det vänstra barnet innehåller endast noder med värden som är mindre än eller lika med grundnodet, och där rätt barn bara innehåller noder med värden som är större än för modernoden. Det är nyckelskillnad. Till skillnad från datastrukturer som arrays, har binärt träd och binärt sökträd inte en övre gräns för att lagra data.

INNEHÅLL

1. Översikt och nyckelskillnad
2. Vad är binärt träd
3. Vad är binärt sökträd
4. Likheter mellan binärt träd och binärt sökträ
5. Side vid sidajämförelse - Binärt träd vs binärt sökträ i tabellform
6. Sammanfattning

Vad är binärt träd?

När man ordnar data i en trädstruktur är noden på toppen av trädet känd som rotnodet. Det kan bara vara en rot för hela trädet. Varje nod utom rotknutpunkten har en kant uppåt till en nod. Det kallas föräldernoden. Noden under föräldrakoden heter sin barnnod. Varje moderkod kan ha högst två barnnoder. De hänvisas till som vänster barn nod och rätt barn nod. En nod utan någon barnnod kallas a bladkod. Det finns inget specifikt sätt att ordna data i binärträdet. Det finns en väg från rotnod till varje nod.

Figur 01: Exempel på binärt träd

Ovanstående är ett exempel på ett binärt träd. Elementet 2, i toppen av trädet, är roten. Varje nod har högst två noder. Om ett träd innehåller några slingor eller om en nod innehåller mer än två noder, kan den inte klassificeras som ett binärt träd. Att gå från en nod till den andra finns alltid en väg. Barnnodarna i root node 2 är 7 och 5. Det är också möjligt att en nod inte har några noder. Men någon nod kan inte ha mer än två noder. Det rätta elementet i roten är 5. Det elementet 5 är moderkoden för barnnod 9. Noden 4 och 11 har inga barnelement. Därför är de bladnoder.

Binärträdet används för att lagra data i hierarkisk ordning. Det liknar filens struktur. Datastrukturen som en array kan lagra en viss 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. Liksom ett binärt träd kan det binära sökträdet också ha två noder. Varje nod utom rotknutpunkten har en kant uppåt till en nod. Det kallas föräldernoden. Noden under en given förbunden med sin kant nedåt kallas sin barnnod. En nod utan någon barnnod kallas en bladnod. Varje moderkod kan ha högst två noder. Det finns barnnoder som refererar till en vänster barnnod och rätt barnnod. Det översta elementet kallas rotnodet. Det vänstra barnet innehåller bara noder med värden som är mindre än eller lika med grundnodet. Det rätta barnet innehåller bara noder med värden som är större än eller lika med grundnodet.

Figur 02: Exempel på binärt sökträd

Elementet 8 är det övre elementet. Därför är det rootnoden. Om 3 är en moderkod, är 1 och 6 barnnoder. 1 är vänster barnnod medan 6 är rätt barnnod. Det vänstra barnet innehåller värden som är mindre än eller lika med moderkoden. När 3 är grundkoden, måste vänster sida ha ett element som är mindre än eller lika med 3. I det här exemplet är det 1. Rätt barn innehåller bara noder med värden som är större än moderkoden. När 3 är moderkoden, borde den högra barnkoden ha ett högre värde än 3. I det här exemplet är det 6. På samma sätt finns det en viss ordning att arrangera varje dataelement 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.

Vad ä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ä kan ha högst två barnnoder.

Vad är skillnaden mellan binärt träd och binärt sökträd?

Binärt träd vs binärt sökträ
Ett binärt träd är en typ av datastruktur där varje förälder nod kan ha maximalt två barn noder.	Binärt sökträd är ett binärt träd där det vänstra barnet innehåller endast noder med värden som är mindre än eller lika med föräldrakoden, och där det rätta barnet bara innehåller noder med värden som är större än modernoden.
Datordelsordning
Ett binärt träd har ingen specifik ordning för att ordna dataelementen.	Ett binärt sökträd har en specifik ordning för att ordna dataelementen.
Användande
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, radera och söka data.

Sammanfattning - Binärt träd mot Binärt sökträd 

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 binärt sökträd. I denna artikel diskuterades skillnaden mellan binärt träd och binärt sökträd. Ett binärt träd är en typ av datastruktur där varje föräldraknut kan ha högst två barnknutor. Binärt sökträd är ett binärt träd där det vänstra barnet innehåller endast noder med värden som är mindre än eller lika med föräldrakoden, och där det rätta barnet bara innehåller noder med värden som är större än modernoden.

Ladda ner PDF-filen av binärt träd vs binärt sökträd

Du kan ladda ner PDF-versionen av den här artikeln och använda den för offline-ändamål enligt citationsnotat. Vänligen ladda ner PDF-versionen här: Skillnad mellan binärt träd och binärt sökträd

Referens:

1.Point, handledning. "Datastrukturer och algoritmer.", Tutorials Point, 8 jan 2018. Tillgänglig här
2. Skillnaden mellan binärt träd och binärt sökträd. | javapedia.Net, Javapedia.net, 15 februari 2017. Tillgänglig här

Image Courtesy:

1. "Binärt träd" Med Derrick Coetzee - Egent arbete, (Public Domain) via Commons Wikimedia
2. "Binärt sökträd". Ingen maskinläsbar författare. (baserat på upphovsrättskrav)., (Public Domain) via Commons Wikimedia