Redigerer Tre (datastruktur) (avsnitt)

==Binære trær==
[[Fil:Binary tree (oriented digraph).png|thumb|Et binært tre: hver node peker på maksimum to barn]]

Et binært tre er et tre der hver node kan ha maksimum to barn. Man kan derfor la hver node ha en direkte peker til hvert enkelt barn. Trær av denne typen vil ha en gjennomsnittlig dybde på <math>O(\sqrt n)</math>.

Binære trær brukes innenfor flere områder av informatikken, og spesielt innenfor [[kompilator]]design.

===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.

===Rød-svarte trær===

En variant av binære søketrær kalles rød-svarte trær. I denne tretypen får hver node tildelt en farge, enten rød eller svart, basert på tre regler:

# Roten i treet er svart
# Om en node er rød, må barna være svarte
# Alle stier fra en node til en ''null''-referanse må inneholde det samme antallet svarte noder.

Disse reglene fører til at høyden på et rød-svart tre med n noder er maksimum <math>2 log_2(n+1)\,</math>. Søking blir derfor alltid en logaritmisk operasjon, faktisk kan alle operasjoner på rød-svarte trær gjøres med tidsforbruk <math>O(log_2 n)\,</math>.

Det er relativt fiklete å sette inn nye elementer i et rød-svart tre. Dette gjør at denne datastrukturen ikke lenger brukes så mye.