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 merandra noder. De enskilda noderna innehåller vissa data såväl som länkar till andra noder. Uppgifterna som finns i trädets noder beställs ofta på något sätt för att tillåta effektiva algoritmer att söka efter,Sätt in och ta bort noder med lätthet.

Noderna på ett sökträd beskrivs med fyra viktiga termer. Överst på ett träd, där den första noden är belägen, kallas roten.Om en nod innehåller länkar till undernoder, kallas den noden som en förälder. Noder som ligger under föräldern kallas barn, och alla noder som inte har några barnnoder ärkallas ett blad. Så en rotnod identifieras eftersom den inte har en förälder, och bladnoder har inga barn.

Ett program kan gå igenom ett träd som söker efter data genom att starta vid en viss nod, utföra en villkorad kontroll och sedan flytta till nästa logiska nod om de nödvändiga data inte finns. Beroende på datastrukturenAnvänds kan denna sökning ta en variabel 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 ärMonterat 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 ären där både höger och vänster barn i rotnoden innehåller antingen samma djup av barnnoder eller är inom ett antal en nod av varandra. Djupet på ett träd är antalet noder fråndet lägsta bladet av ett träd till roten. Ett obalanserat träd kunde ha alla noder på bara en sida eller ha alla nodernaArrangerat på ett linjärt sätt utan grenar. När djupet på ett träd ökar kan hastigheten för sökalgoritmer 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 balansen samtidigt som man bevarar dataens ordning i bladen. Även om utförande av 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 nolltill två barnnoder. 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ångaAlgoritmer finns för binära sökträd som kan göra beställningsdata mycket enkla.

Det finns ingen enda standard iMplementering för sökträdnoder. Noderna kan representeras av en mängd olika datastrukturer. Uppsättningar av matriser kan användas, vilket kan multiplicera länkade listor. Ofta använder ett sökträd en anpassningDatastruktur som är utformad för att hjälpa till att genomföra de nödvändiga operationerna som krävs av programmet. Vissa standardprogrammeringsbibliotek inkluderar till och med sina egna interna implementeringar av sökträd.