En nybörjarguide till binära träd

Om du har gått en datastrukturkurs i din datavetenskapliga examen eller är en självlärd programmerare, är chansen stor att du har stött på termen "Binära träd". Även om de kanske låter lite överväldigande och komplexa, är konceptet med ett binärt träd ganska enkelt.

Läs vidare när vi dissekerar binära träd och varför de är ett nödvändigt kärnkoncept för programmerare.

Vad är binära träd?

Binära träd är en av de första datastrukturer som eleverna lär sig i en datastrukturkurs. Ett binärt träd består av många noder, och varje nod i det binära trädet innehåller två pekare som anger vänster och höger barns datanoder.

Den första noden i ett binärt träd kallas "roten". Noder för den sista nivån i ett träd kallas löv.

Varje nod innehåller ett dataobjekt och två nodpekare. Ett tomt binärt träd representeras av en nollpekare. Som du kanske redan har förstått kan binära träd bara få två barn (därav namnet).

Typer av binära trädstrukturer

Det finns flera olika binära trädstrukturer beroende på hur noder placeras. Ett binärt träd kallas ett fullständigt binärt träd när varje nod i trädet har antingen noll eller två barn. I ett perfekt binärt träd har alla noder två barn och bladen är alla på samma djup.

Relaterad: Bästa sätten att lära dig att koda gratis

Ett komplett binärt träd har noder fyllda på varje nivå, med undantag för den sista nivån. I kompletta binära träd är noder koncentrerade på rotens vänstra sida. En annan vanlig struktur är ett balanserat binärt träd; i denna struktur måste höjden på höger- och vänsterunderträdet högst skilja sig åt med en. Det krävs också att vänster och höger subtrees måste balanseras också.

Det är viktigt att notera att höjden på det balanserade binära trädet är O (logn), där n är antalet noder i trädet.

I vissa fall, om varje nod bara har ett vänster eller höger barn, kan det binära trädet bli ett snett binärt träd. Det kommer då att bete sig som en länkad lista, sådana träd kallas också ett urartat träd.

Vad är binära sökträd?

Ett binärt sökträd (BST) är i huvudsak ett ordnat binärt träd med en speciell egenskap som kallas egenskapen "binärt sökträd". BST -egenskapen betyder att noder med ett nyckelvärde som är mindre än roten placeras i det vänstra delträdet, och noder med ett nyckelvärde som är större än roten är en del av det högra delträdet.

BST -egenskapen måste vara sann för varje efterföljande överordnad nod i trädet.

Binära sökträd erbjuder snabb insättning och sökning. Infogning, borttagning och sökoperationer har en värsta fallskomplexitet av O (n), vilket liknar en länkad lista.

Fördelar med binära träd

Binära träd erbjuder många fördelar, varför de förblir en mycket användbar datastruktur. De kan användas för att visa strukturella relationer och hierarkier i en datamängd. Ännu viktigare är att binära träd möjliggör effektiv sökning, radering och infogning.

Det är också mycket enkelt att implementera och underhålla ett binärt träd. Ett binärt träd erbjuder programmerare fördelarna med en beställd matris och en länkad lista; sökning i ett binärt träd är lika snabbt som i en sorterad matris och infogning eller radering är lika effektiv som i länkade listor.

Binära träd är viktiga datastrukturer

Binära träd är en mycket viktig datastruktur och det är avgörande att programmerare trivs med att tillämpa dem i sina program. Ofta frågar intervjuare enkla binära trädproblem som transversaler, maximaldjup, spegling etc.

Vi rekommenderar starkt att du förstår det binära trädkonceptet och känner till typiska intervjuproblem.

TreeViz: Ett enkelt sätt att visualisera datastrukturer

Läs Nästa

Om författaren