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 kopplas till noll eller fler andra noder. De enskilda noderna innehåller en del data såväl som länkar till andra noder. Datan som finns i trädets noder är mycket ofta ordnad på något sätt för att möjliggöra effektiva algoritmer att söka efter, sätt in och ta bort noder med lätthet.
Noderna i ett sökträd beskrivs med fyra viktiga termer. Toppen av ett träd, där den första noden finns, kallas roten. Om en nod innehåller länkar till sub -noder, den noden är känd som en förälder. Noder som är under föräldern kallas barn, och alla noder som inte har några barnnoder kallas ett löv. Så, en rotnod identifieras eftersom den inte har en förälder, och lövnoder kommer inte att ha några barn.
Ett program kan förflytta sig genom ett träd och söka efter data genom att börja vid en viss nod, utföra en villkorskontroll och sedan flytta till nästa logiska nod om den nödvändiga informationen inte finns. Beroende på vilken datastruktur som används. , den här sökningen kan ta en 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 sätts ihop slumpmässigt, osorterat eller tillåter flera föräldrar, kan sökningen 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 ett där både de högra och vänstra barnen i rotnoden innehåller antingen samma djup av barnnoder eller ligger inom en nodräkning av varandra. Ett träds djup är antalet noder från trädets lägsta blad till roten. Ett obalanserat träd kan ha alla noder på bara en sida eller ha alla noderna arrangerade 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älvbalanserande. Dessa träd använder operationer som trädrotation för att hjälpa till att upprätthålla balansen samtidigt som ordningen på data i löven bevaras. Även om de utförs trädrotationer kan sakta ner ett program när man lägger till och tar bort noder, detta motverkas av den hastighet 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 löv i trädet är ordnade 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 det mycket enkelt att beställa data.
Det finns ingen enskild standardimplementering för sökträdnoder. Noderna kan representeras av en mängd olika datastrukturer. Matriser av matriser kan användas, liksom 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 slutföra de nödvändiga operationerna som programmet kräver. Vissa standardprogrammeringsbibliotek inkluderar till och med sina egna interna implementeringar av sökträd.