Vad är ett binärt träd?

Ett binärt träd är en typ av datastruktur som används i datorprogrammering för att lagra, sortera och få åtkomst till information.Binära träd är den enklaste variationen av träd, men är mycket användbara och enkla att implementera.En typisk implementering av ett binärt träd förlitar sig på en rotnod kopplad till en serie noder som utgör själva trädet med pekarevariabler.Denna typ av träd härstammar sitt namn från det faktum att ingen nod i trädet kan ha mer än två barn.

Träddatastrukturer finns i många sorter.De består av olika noder, som är organiserade i ett hierarkiskt mönster.En enda nod, roten, är åtkomstpunkten genom vilken hela dataträdet kan sökas eller på annat sätt manipuleras.Denna rotnod pekar på den övre noden i själva trädet.

Varje nod i ett träd, förutom för den översta noden, kommer att ha en föräldernod som ligger ovanför den i trädets hierarki.Det kan också ha barnnoder, som finns under den.En given nod kan således ha noll, en eller två barnnoder som är kopplade till den.Vanliga binära träd tillåter noder med valfritt antal barn när som helst i trädet.De lägger inte heller några begränsningar för hur värdena som lagras i noder som omfattar ett träd är ordnade.

Datastrukturer är mest användbara när de förbättrar hastigheten med vilken data kan nås av en dator och modifierade versioner av binära träd används tillförbättra deras effektivitet.Ett binärt sökträd är ett där alla datavärden som finns på vänster fallande gren från en given nod har värden som är lika med eller mindre än värdet lagrat i den noden.Värden på höger sida av en nod i ett ordnat binärt träd måste i sin tur vara större än värdet i basnoden.Denna databeställning gör det möjligt att skriva en mycket effektivare sökalgoritm.

Formen på ett binärt träd är också viktigt för att bestämma effektiviteten för en sökalgoritm.Den minst effektiva variationen av ett binärt träd är en där varje nod bara har ett enda barn.En dator kan behöva undersöka varje dataobjekt i hela trädet för att hitta en enda information i denna konfiguration.Det mest effektiva binära trädet, däremot, är ett där varje nod som sparar för dem längst ner i trädet har två barn och där alla bladnoder, de nedre noderna i trädet, är samma avstånd från roten.