Hvad er et søgetræ?
Et søgetræ er en datastruktur, der bruges i computerprogrammering til at indeholde og organisere en liste over data. Hvert søgetræ består af et bestilt sæt noder. Disse noder kan forbindes til nul eller flere andre noder. De individuelle knudepunkter indeholder nogle data såvel som links til andre knudepunkter. De data, der er indeholdt i træets knudepunkter, er meget ofte bestilt på en eller anden måde for at lade effektive algoritmer søge efter, indsæt og fjern noder med lethed.
Knudepunkterne i 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 sub -knudepunkter, den knude kaldes en forælder. Noder, der er under forælderen kaldes børn, og enhver knude, der ikke har nogen underordnede knudepunkter, kaldes et blad. 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 den anvendte datastruktur , kan denne søgning tage en variabel tidsperiode. Hvis søgetræet er organiseret under processen med at tilføje og fjerne noder, kan søgningen være meget hurtig. Når et træ samles tilfældigt, er ikke sorteret eller tillader flere forældre, kan søgningen tage meget lang tid.
En faktor, der påvirker brugen af søgetræer, er spørgsmålet om balance. Et afbalanceret træ er en, hvor både højre og venstre børn i rodnoden indeholder enten den samme dybde af underordnede knudepunkter eller er inden for en enkeltknudetælling hinanden. Dybden af et træ er antallet af knudepunkter fra det laveste blad af et træ til roden. Et ubalanceret træ kunne have alle knudepunkter på kun den ene side eller have alle knudepunkter arrangeret på en lineær måde uden grene. Når dybden af et træ øges, kan søgealgoritmernes hastighed falde dramatisk.
Der er visse typer af søgetræer, der beskrives som selvbalancerende. Disse træer bruger operationer såsom trærotation for at hjælpe med at bevare balancen, mens du bevarer rækkefølgen af data i bladene. trærotationer kan nedsætte et program, når du tilføjer og fjerner noder, dette modvirkes af den hastighed, hvormed data kan hentes.
Selvom der er mange typer af søgetræer, er den mest almindelige trædatastruktur et binært søgetræ. Denne datatype består af noder, der hver har nul til to underordnede noder. Der er kun en rodnode, og alle blade i træet ordnes fra venstre mod højre i stigende værdier i henhold til de data, de har. Mange algoritmer findes til binære søgetræer, der kan gør bestillingsdata meget let.
Der er ikke en enkelt standardimplementering til søgetræknudepunkter. Knudepunkterne kan repræsenteres af en lang række datastrukturer. Arrays af arrays kan bruges, som det også kunne multiplicere sammenkoblede lister. Ofte kan en søgetræ bruger en brugerdefineret datastruktur, der er designet til at hjælpe med gennemførelsen af de nødvendige operationer, som programmet kræver. Nogle standardprogrammeringsbiblioteker inkluderer endda deres egne interne implementeringer af søgetræer.