Referanseside · Kapittel 12

Begreper & formler

Alle nøkkelbegrepene og formlene fra Binære søketrær, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Binært søketre (BST)

Tre der for hver node $x$ gjelder at alle nøkler i venstre undertre < $x . k ey$ < høyre undertre.

02In-order traversering

Besøker noder i stigende rekkefølge (venstre, rot, høyre).

03Søk

Traverserer treet fra rot til blad basert på sammenligning med nøkler.

04Innsetting

Legger inn en ny nøkkel som blad på korrekt plass etter søk.

05Sletting

Fjerner node og rekonstruerer treet avhengig av antall barn.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

\forall x, y : y \in venstre (x) \Rightarrow y . k ey < x . k ey, y \in høyre (x) \Rightarrow y . k ey > x . k ey

T (h) = O (h)

InOrder (x) : InOrder (x . l e f t); print (x . k ey); InOrder (x . r i g h t)