Hvad er et søgningstræ?
Et søgningstræ er en datastruktur, der bruges i computerprogrammering til at indeholde og organisere en liste over data. Hvert søgningstræ består af et ordnet sæt noder. Disse noder kan tilsluttes til nul eller mereAndre knudepunkter. De individuelle knudepunkter indeholder nogle data såvel som links til andre knudepunkter. De data, der er indeholdt i træets knudepunkter, bestilles ofte på en eller anden måde for at give effektive algoritmer mulighed for at søge efter,Indsæt og fjern noder let.
Knudepunkterne på et søgetræ er beskrevet med fire vigtige udtryk. Toppen af et træ, hvor den første knude er placeret, kaldes roden.Hvis en knude indeholder links til undernoder, er den knude kendt som en forælder. Knudepunkter, der er under forælderen, kaldes børn, og enhver knude, der ikke har nogen barneknuder, erkaldes et blad. Så en rodnode identificeres, fordi den ikke har en forælder, og bladknudepunkter har ingen børn.
Et program er i stand til at bevæge sig gennem et træ, der søger efter data ved at starte ved en bestemt knude, udføre en betinget kontrol og derefter flytte til den næste logiske knude, hvis de krævede data ikke er til stede. Afhængig af datastrukturenBrugt, kan denne søgning tage en variabel mængde tid. Hvis søgningstræet er organiseret under processen med at tilføje og fjerne knudepunkter, kan søgningen være meget hurtig. Når et træ erSamlet tilfældigt, er usorteret eller tillader flere forældre, søgningen kan tage meget lang tid.
En faktor, der påvirker brugen af søgningstræer, er spørgsmålet om balance. Et afbalanceret træ erEn, hvor både højre og venstre børn i rodknuden indeholder enten den samme dybde af børnesknudepunkter eller er inden for et en-node-antal af hinanden. Dybden af et træ er antallet af knudepunkter fradet laveste blad af et træ til roden. Et ubalanceret træ kunne have alle knudepunkter på kun den ene side eller have alle knudepunkterArrangeret på en lineær måde uden grene. Når dybden af et træ øges, kan hastigheden af søgealgoritmer falde dramatisk.
Der er visse typer søgetræer, der beskrives som selvbalancerende.Disse træer bruger operationer såsom trærotation til at hjælpe med at opretholde balance, mens de bevarer rækkefølgen af dataene i bladene. Selvom udførelse af trærotationer muligvis bremser et program, når du tilføjer og fjerner knudepunkter,Dette modvirkes af den hastighed, hvormed data kan hentes.
Selvom der er mange typer søgningstræer, er den mest almindelige trædatastruktur et binært søgetræ. Denne datatype består af knudepunkter, som hver har nultil to børnesknudepunkter. Der er kun en rodnode, og alle blade i træet bestilles fra venstre mod højre i stigende værdier i henhold til de data, de har. MangeAlgoritmer findes for binære søgningstræer, der kan gøre bestillingsdata meget let.
Der er ingen enkelt standard IMlemplementering til søgningstræknudepunkter. Knudepunkterne kan repræsenteres af en lang række datakonstruktioner. Arrays af arrays kan bruges, ligesom multiplicerede lister kan multiplicere lister. Ofte bruger et søgningstræ en sædvaneDatastruktur, der er designet til at hjælpe med at afslutte de nødvendige operationer, der kræves af programmet. Nogle standardprogrammeringsbiblioteker inkluderer endda deres egne interne implementeringer af søgningstræer.