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 av pekvariabler. Denna typ av träd har sitt namn från det faktum att ingen nod i trädet kan ha fler än två barn.

Trädatasstrukturer 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, spara för den översta noden, kommer att ha en överordnad nod som ligger ovanför i trädets hierarki. Det kan också ha barnnoder, som finns under den. En given nod nås genom dem ovanför i trädet och ger åtkomst till dem under den.

Binära träddatastrukturer tillåter varje nod att inte ha mer än två barn. En given nod kan alltså ha noll-, en eller två barnnoder knutna till den. Vanliga binära träd tillåter noder med valfritt antal barn när som helst i trädet. De sätter inte heller några begränsningar för hur värdena som lagras i noder som utgör 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 för att fö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 det värde som lagras 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 hos en sökalgoritm. Den minst effektiva variationen av ett binärt träd är en där varje nod endast har ett enda barn. En dator kan behöva undersöka alla data i hela trädet för att hitta en enda information i den här konfigurationen. Det mest effektiva binära trädet, däremot, är en där varje nod som är sparat för dem längst ner i trädet har två barn och där alla bladnoderna, bottennoderna i trädet, är samma avstånd från roten.