Om du har gått en datastrukturkurs i din datavetenskapsexamen, eller är en självlärd programmerare, är chansen stor att du har stött på termen “binära träd”. Även om de kan låta 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 bland en av de första datastrukturerna som eleverna får lära 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 indikerar de vänstra och högra underordnade datanoderna.
Den första noden i ett binärt träd kallas “roten”. Noder på 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 räknat ut kan binära träd bara ha två barn (därav namnet).
Typer av binära trädstrukturer
Det finns flera olika binära trädstrukturer beroende på hur noderna är placerade. Ett binärt träd kallas ett helt 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 löven är alla på samma djup.
Ett komplett binärt träd har noder fyllda i varje nivå, med undantag för den sista nivån. I kompletta binära träd är noder koncentrerade till vänster sida av roten. En annan vanlig struktur är ett balanserat binärt träd; i denna struktur måste höjderna på höger och vänster underträd skilja sig åt högst en. Det krävs också att de vänstra och högra underträden 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 skevt binärt träd. Det kommer då att bete sig som en länkad lista, sådana träd kallas också för ett degenererat 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 känd som egenskapen “binärt sökträd”. BST-egenskapen innebär att noder med ett nyckelvärde mindre än roten placeras i det vänstra underträdet, och noder med ett nyckelvärde större än roten är en del av det högra underträdet.
BST-egenskapen måste vara sann för varje efterföljande överordnad nod i trädet.
Binära sökträd erbjuder snabb infogning och uppslagning. Insättning, radering och sökoperationer har en tidskomplexitet i värsta fall av O(n), vilket liknar en länkad lista.
Fördelarna med binära träd
Binära träd erbjuder många fördelar och det är därför de förblir en mycket användbar datastruktur. De kan användas för att visa strukturella samband och hierarkier i en datamängd. Ännu viktigare, binära träd tillåter 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 ordnad array och en länkad lista; sökning i ett binärt träd är lika snabbt som i en sorterad array och insättnings- eller raderingsoperationer är lika effektiva 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 är bekväma med att använda dem i sina program. Ofta frågar intervjuare enkla binära trädproblem som traverseringar, maximalt djup, spegling, etc.
Vi rekommenderar starkt att du förstår konceptet med binära träd och att du är bekant med typiska intervjuproblem.
Om författaren
M. Fahad Khawaja (91 artiklar publicerade)
Fahad är författare på MakeUseOf och studerar för närvarande datavetenskap. Som en ivrig teknikskribent ser han till att han håller sig uppdaterad med den senaste tekniken. Han är särskilt intresserad av fotboll och teknik.
Mer från M. Fahad Khawaja
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
