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 merandre noder. De individuelle nodene inneholder noen data samt lenker til andre noder. Dataene som er inneholdt i nodene til treet er veldig ofte bestilt på en måte for å tillate effektive algoritmer å søke etter,Sett inn og fjern noder med letthet.

Nodene til et søketre er beskrevet med fire viktige begrep. Toppen av et tre, der den første noden ligger, kalles roten.Hvis en node inneholder lenker til undernoder, er den noden kjent som en forelder. Noder som er under foreldrene kalles barn, og en hvilken som helst node som ikke har noen barneknuter erkalt et blad. Så en rotknute blir identifisert fordi den ikke har en forelder, og bladknuter har ingen barn.

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

En faktor som påvirker bruken av søketrær er spørsmålet om balanse. Et balansert tre eren der både høyre og venstre barn av rotnoden inneholder enten den samme dybden av barneknuter eller er innenfor en en-node-antall av hverandre. Dybden på et tre er antall noder fraDet laveste bladet av et tre til roten. Et ubalansert tre kan ha alle nodene på bare den ene siden eller ha alle nodeneAnordnet på en lineær måte uten grener. Når dybden til et tre øker, kan hastigheten på søkealgoritmer redusere dramatisk.

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

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 nulltil to barneknuter. Det er bare en rotknute, og alle bladene i treet er bestilt fra venstre til høyre i stigende verdier i henhold til dataene de har. MangeAlgoritmer finnes for binære søketrær som kan gjøre bestillingsdata veldig enkelt.

Det er ingen enkelt standard iMplementation for søketre -noder. Nodene kan representeres med et bredt utvalg av datastrukturer. Arrays av matriser kan brukes, og det kan også multiplisere koblede lister. Ofte bruker et søketre en tilpasset en tilpassetDatastruktur som er designet for å hjelpe til med å fullføre de nødvendige operasjonene som er kalt av programmet. Noen standardprogrammeringsbiblioteker inkluderer til og med sine egne interne implementeringer av søketrær.