søketreet

Søketreet, ofte kalt søketreet eller søketrær i norsk teknisk terminologi, er en trebasert datastruktur som organiserer nøkler i en sortert rekkefølge og muliggjør effektiv oppslag, innsetting og sletting av elementer. I et grunnleggende binært søketre følger nøklene en ordnet rekke: nøkler i venstre undertre, som er mindre enn roten, og nøkler i høyre undertre, som er større. Dette gjør at søk og oppdateringer kan utføres ved å bruke sammenligning og halvdelende deling av treet.

Vanlige operasjoner inkluderer søk, innsetting, sletting, samt tilgang til minimum og maksimum. Dybden på treet påvirker hvor mange sammenligninger som trengs for å finne et element. Uten balanse kan et binært søketre bli skjevt og dermed ha dårligere ytelse, nær O(n) i verste fall. For å sikre mer konsekvent ytelse finnes balansevarianter som AVL-tre og rød-svart tre, som garanterer O(log n) søk og oppdateringer i alle tilfeller. For database- og filsystemapplikasjoner brukes ofte B-tre og dets varianter, som er tilpasset disklagring og lar mange nøkler lagres per node.

Bruksområder omfatter implementering av ordlister og tavler, effektive oppslag i programvarebiblioteker, og indeksering i databaser. Søketreet gir enkel implementasjon og rask tilgang ved midlertidig eller dynamisk datasett, men valget mellom et enkelt binært søketre og et balansert tre avhenger av behov for garantert ytelse og minne- eller diskbruk. Konseptet har vært en grunnstein i datastrukturteori siden midten av 1900-tallet og har utviklet seg i takt med moderne informasjonsbehandling.