Hva er et søketre?

Et søketre er en datastruktur som brukes i dataprogrammering for å inneholde og organisere en liste over data. Hvert søketre består av et bestilt sett med noder. Disse nodene kan kobles til null eller flere andre noder. De individuelle nodene inneholder noen data i tillegg til koblinger til andre noder. Dataene som er inneholdt i treets noder er veldig ofte bestilt på noen måte for å la effektive algoritmer søke etter, sett inn og fjern noder med letthet.

Knutepunktene til et søketre er beskrevet med fire viktige uttrykk. Toppen av et tre, der den første noden befinner seg, kalles roten. Hvis en node inneholder lenker til sub -noder, den noden er kjent som en overordnet. Noder som er under foreldrene kalles barn, og enhver node som ikke har noen barneknuter kalles et blad. en rotknute identifiseres fordi den ikke har en forelder, og bladknutene har ingen barn.

Et program er i stand til å bevege seg gjennom et tre som søker etter data ved å starte ved en bestemt nod, utføre en betinget sjekk og deretter flytte til neste logiske node hvis de nødvendige dataene ikke er til stede. , kan dette søket ta en variabel periode. Hvis søketreet er organisert under prosessen med å legge til og fjerne noder, kan søket være veldig raskt. Når et tre er satt sammen tilfeldig, er usortert eller tillater flere foreldre, kan søket ta veldig lang tid.

Én faktor som påvirker bruken av søketrær er spørsmålet om balanse. Et balansert tre er en der både høyre og venstre barn i rotnoden inneholder enten samme dybde av barneknuter eller er innenfor en teller med en node av hverandre. Dybden på et tre er antall noder fra det laveste bladet av et tre til roten. Et ubalansert tre kan ha alle nodene på bare en side eller ha alle nodene ordnet på en lineær måte uten grener. Når dybden på et tre øker, kan hastigheten på søkealgoritmer avta dramatisk.

Det er visse typer søketrær som beskrives som selvbalanserende. Disse trærne bruker operasjoner som trerotasjon for å opprettholde balansen mens du bevarer rekkefølgen på dataene i bladene. trerotasjoner kan bremse et program når du legger til og fjerner noder, dette motvirkes av hastigheten som data kan hentes på.

Selv om det er mange typer søketrær, er den vanligste tredatastrukturen et binært søketre. Denne datatypen består av noder som hver har null til to underordnede noder. Det er bare en rotnode, og alle bladene i treet er bestilt fra venstre til høyre i stigende verdier i henhold til dataene de har. Mange algoritmer finnes for binære søketrær som kan gjøre bestillingsdata veldig enkelt.

Det er ingen standardimplementering for søketre-noder. Knutepunktene kan være representert av et bredt utvalg av datastrukturer. Arrays av matriser kan brukes, slik som mangedoble lister. Ofte kan en søketrær bruker en tilpasset datastruktur som er utviklet for å hjelpe deg med gjennomføringen av nødvendige operasjoner som programmet krever. Noen standardprogrammeringsbiblioteker inkluderer til og med egne interne implementeringer av søketrær.