Dagens 10 kort

Søk i et BST følger én sti fra roten nedover, så kostnaden er proporsjonal med treets høyde h, ikke antall noder n. I verste tilfelle blir treet degenerert (skjevt): hvis nøklene settes inn i sortert eller omvendt sortert rekkefølge, får hver node bare ett barn, og treet blir i praksis en lenket liste med høyde h = n - 1. Da blir søk, innsetting og sletting O(n). For å garantere O(log n) må treet holdes balansert, slik at høyden er Θ(log n). Et perfekt/komplett binærtre med n noder har høyde ⌊$\log_2 n$⌋, og balanserte trevarianter som AVL-trær og rød-svart-trær bruker rotasjoner ved innsetting/sletting for å sikre at høyden forblir O(log n) uansett innsettingsrekkefølge.