5. Trær

Et tre har en rotnode, og rotnoden har barn. Hvert barn kan ha barn igjen. En node uten barn kalles en løvnode. Et barn med sine barn (og deres barn igjen, osv) kalles et subtre.
Dybden av en node N er lengden av stien fra rotnoden til N.
Høyden av et tre er den lengste stien fra rotnoden til en løvnode.

For eksempel syntaksen i språket er bygd opp som et tre. I eksemplene må du selv tegne inn rotnoden, den heter "helsetning".
Analyse 1
Analyse 2
(Analyse-eksemplene er fra Lingvistikk.)

5.1 Binære trær

Et binært tre er et tre der hver node kun kan ha 0-2 barn.
Istedenfor å deklarere pekere til venstrebarn og høyrebarn, kan man deklarere dem til å peke på første barn og neste søsken. På den måten kan ett hvert tre implementeres som et binært tre.
Binære trær kan degenerere til å bli lenkede lister.

5.2 BS-trær

I et binært søketre er nøklene ordnet slik at du alltid finner høyere nøkler til høyre for noden, og lavere nøkler til venstre for noden.

5.2.1 Finne

For å finne en node med en gitt nøkkel i treet, traverserer du treet slik at hvis nøkkelen du leter etter er større enn den du nå titter på, går du til i høyre i treet. Er den mindre, går du til venstre. Er den lik, har du funnet riktig node. Ender du opp hos en node uten barn uten å ha funnet nøkkelen, finnes den ikke i treet.

5.2.2 Sette inn

Du startet som om du skulle prøve å finne noden i treet. Hvis den faktisk finnes, kan du velge mellom å ikke gjøre noe som helst, eller for eksempel øke en variabel kalt Antall i noden du fant. Finnes ikke noen node med en slik nøkkel fra før, settes den nye noden inn på det siste stedet der traverseringen endte.

5.2.3 Slette

Først må vi finne noden som skal slettes. (Hvis den ikke finnes, returneres typisk en verdi som viser oss dette, for eksempel NULL.) Hvis noden er et løv (den har ingen barn) kan den slettes umiddelbart. Hvis den bare har ett barn, kan noden bli slettet etter at dens forelder har justert en link til å peke på barnet (til den noden som skal  slettes). Med to barn blir det mer komplisert. Strategien er å bytte ut dataene i denne noden med de minste dataene i det høyre subtre, og så rekursivt slette den noden (som nå er tom). Fordi den minste noden i det høyre subtreet ikke kan ha noen venstre-barn (da hadde ikke denne noden vært den minste), er den andre slette-operasjonen grei.
Fra filen bstree.cpp (etter Fongen): 
Position BStree::del(int a) {
 Position tmpcell;
 if (this == NULL)
  Error("!");
 else if (a < key) left = left->del(a);
 else if (a > key) right = right->del(a);
 else  // Found the element to be deleted
  if (right && left) { // Two children
   // Replace with the smallest in right subtree
   tmpcell = right->findMin();
   key = tmpcell->key;
   right = right->del(key);
  } else {
   // one or zero children
   if (!left)
    tmpcell = right;
   else //if (!right)
    tmpcell = left;
   delete this;
   return tmpcell;
  }
  return this;
}
 

5.2.4 To implementasjoner

bts.cpp (Etter Sedgewick).
bstree.cpp (Etter Fongen).

5.3 AVL-trær

Et AVL (Adelson-Velskii & Landis) -tre er et binært søketre med en balansekondisjon: for hver node i treet kan forskjellen av høyden av venstre og høyre subtree ikke være mer enn 1. (Høyden av et tomt tre er definert til -1.) Hver node inneholder høydeinformasjon om seg selv. Høyden av et AVL-tre er ca. 1.44 log(N +2)-.328, men i praksis er den bare litt mer enn log N. (For informasjon om logaritmer, se 1.4 Logaritmer.)
Minimumsnummer av noder, S(h), i et AVL-tre av høyden h er gitt ved
S(h) = S(h-1) + S(h-2) +1. For h = 0, S(h) = 1. For h = 1, S(h) = 2. Funksjonen S(h) er nært beslektet med Fibonacci-nummerene.

5.3.1 Innsetting

Ved innsetting er det bare noder på veien fra innsettingspunktet til roten som kan ha fått sin balanse forandret, fordi bare disse nodenes subtrær er blitt forandret. Mens vi følger veien opp til roten og oppdaterer balanseinformasjonen, kan det hende vi finner noder der den nye balansen bryter med AVL-kravet. Vi kommer til å rebalansere treet ved den første (dvs. dypeste) slike noden. Denne rebalanseringen garanterer at hele treet tilfredstiller AVL-kravet. (-Etter Weiss, p. 145-146.)

Det er fire tilfeller der det kan hende vi må rebalansere:
1. Ved innsetting i venstre subtre til nodens venstre barn.
2. Ved innsetting i høyre subtre til nodens venstre barn.
3. Ved innsetting i venstre subtre til nodens høyre barn.
4. Ved innsetting i høyre subtre til nodens høyre barn.

Tilfellene 1 & 4 og 2 & 3 er symmetriske med hensyn til foreldrenoden, men vi må likevel programmere for alle fire tilfellene.

5.3.1.1 Enkel rotasjon

I de tilfellene der innsettingen skjer på yttersiden (venstre - venstre eller høyre - høyre) er det nok med en enkel rotasjon for å få orden på treet igjen.

5.3.1.2 Dobbel rotasjon