Vad är ett sökträd?
Ett sökträd är en datastruktur som används i datorprogrammering för att innehålla och organisera en lista med data. Varje sökträd består av en ordnad uppsättning noder. Dessa noder kan anslutas till noll eller mer noder. De enskilda noderna innehåller en del data såväl som länkar till andra noder. Uppgifterna som finns i trädets noder är ofta ordnade på något sätt så att effektiva algoritmer kan söka efter, sätt in och ta bort noder med lätthet.
Noderna i ett sökträd beskrivs med fyra viktiga termer. Överst på ett träd, där den första noden finns, kallas roten. Om en nod innehåller länkar till sub -noder, den noden kallas förälder. Noder som ligger under föräldern kallas barn, och alla noder som inte har några barnnoder kallas ett blad. en rotnod identifieras eftersom den inte har en förälder, och bladnoder har inga barn.
Ett program kan röra sig genom ett träd som söker efter data genom att börja vid en viss nod, utföra en villkorlig kontroll och sedan flytta till nästa logiska nod om den nödvändiga datan inte finns. Beroende på vilken datastruktur som används , kan denna sökning ta varierande tid. Om sökträdet är organiserat under processen att lägga till och ta bort noder kan sökningen vara mycket snabb. När ett träd monteras slumpmässigt, är osorterat eller tillåter flera föräldrar, sökningen kan ta mycket lång tid.
En faktor som påverkar användningen av sökträd är frågan om balans. Ett balanserat träd är en där både höger och vänster barn i rotnoden innehåller antingen samma djup av barnnoder eller är inom en enda nod. av varandra.Djupet för ett träd är antalet noder från det lägsta bladet av ett träd till roten. Ett obalanserat träd kan ha alla noderna på endast en sida eller ha alla noderna ordnade på ett linjärt sätt utan grenar. När djupet på ett träd ökar kan sökalgoritmernas hastighet minska dramatiskt.
Det finns vissa typer av sökträd som beskrivs som självbalansering. Dessa träd använder operationer som trädrotation för att upprätthålla balans medan de bevarar ordningen på uppgifterna i bladen. trädrotationer kan bromsa ett program när du lägger till och tar bort noder, detta motverkas av hastigheten med vilken data kan hämtas.
Även om det finns många typer av sökträd är den vanligaste träddatastrukturen ett binärt sökträd. Denna datatyp består av noder som var och en har noll till två underordnade noder. Det finns bara en rotnod, och alla blad i trädet beställs från vänster till höger i stigande värden enligt de data de har. Många algoritmer finns för binära sökträd som kan gör beställningsdata väldigt enkelt.
Det finns ingen enskild standardimplementering för sökträdnoder. Noderna kan representeras av ett brett utbud av datastrukturer. Arrayer av matriser kan användas, vilket också kan multiplicera länkade listor. Ofta kan en sökträdet använder en anpassad datastruktur som är utformad för att hjälpa till att genomföra nödvändiga operationer som programmet kräver. Vissa standardprogrammeringsbibliotek inkluderar även sina egna interna implementeringar av sökträd.