Redigerer Tre (datastruktur) (avsnitt)

===Binære søketrær===

I et binært søketre har hver node fått tilordnet en verdi. Et binært søketre kjennetegnes av at verdien i en node er større enn alle verdiene i venstre subtre, og mindre enn alle verdiene i høyre subtre.

Et binært søketre vil ha en gjennomsnittlig dybde på <math>O(\log_2 n)\,</math>. Dette gjør at man raskt kan finne et element i et binært søketre.

Innsetting av et element i et slikt tre er også relativt enkelt. Det gjøres ved å søke seg frem til riktig plass i treet, på samme måte som for finn-operasjonen, og deretter dytte noden man tar plassen til ned som barnet til noden man setter inn.

Det er noe verre å slette en node fra det binære søketreet. Om noden man vil slette er en bladnode, kan den slettes umiddelbart. Om noden man vi lette bare har ett barn, kan man slette den og la foreldrenoden til den man slettet peke på barnenoden til noden man slettet. Om noden man vil slette har to barn, må man erstatte noden man sletter, men det minste barnet i høyre subtre, og rekursivt slette noden man flytter opp.