Binary Search Trees

// INSERT · SEARCH · DELETE · TRAVERSALS
CS DATA STRUCTURES
Insert Node
Forhåndsinnstillinger
Søk
Slett
Traverseringer
Traverseringsresultat
Animasjonshastighet
Trestatistikk
0
NODER
0
HØYDE
0
BLADER
BALANSE
Trevisualiserer
Nøkkelkonsepter
🌳

BST-egenskap

Venstre barn < forelder < høyre barn — alltid. Dette gjør søk raskt.

Tidskompleksitet

Søk/Sett inn/Slett: O(h). Balansert tre gir O(log n).

📐

In-order = Sortert

In-order-traversering gir alltid en perfekt sortert sekvens.

⚖️

Balanse er viktig

Sorterte innsettinger lager en lenket liste (O(n)). Tilfeldig rekkefølge holder det balansert.

📏

Høyde

Ideell høyde ≈ log₂(n). Et tre med 7 noder kan ha høyde 3 hvis balansert.

🔍

Søkesti

Hver sammenligning halverer gjenværende noder — som binærsøk på en sortert tabell.