Rotfaste trestrukturer

Et tre organiserer data etter en rekursiv relasjon: en rot med deltrær som selv er trær. To rotfaste strukturer går igjen i pensum fordi de løser hver sin oppgave effektivt — haugen gir konstant tilgang til ekstremverdien og logaritmisk innsetting, og det binære søketreet holder nøklene ordnet slik at søk kan kaste halve treet ved hver sammenligning.

Haugen som tabell og prioritetskø

En Haug er et nesten komplett binærtre: alle nivåer er fulle unntatt eventuelt det nederste, som fylles fra venstre. Nettopp fordi treet er nesten komplett kan vi lagre det kompakt i en tabell uten pekere — node $i$ ligger i a[i], og navigasjonen er ren aritmetikk.

Dette gjør haugen til en effektiv prioritetskø. Maximum leser bare a[0] i konstant tid. Extract-Max flytter siste element til roten og lar det sive ned (Max-Heapify) til egenskapen er gjenopprettet. Insert legger elementet bakerst og lar det boble opp mot roten. Begge berører bare én vei fra rot til blad, så de koster $O(\lg n)$ — like dypt som treet er.

Build-Max-Heap og Heapsort

For å gjøre en vilkårlig tabell om til en haug kan vi kjøre Max-Heapify på hver interne node nedenfra og opp. Bladene (den øverste halvdelen av indeksene) er allerede trivielle hauger, så vi starter på den siste forelderen, $\lfloor n/2 \rfloor - 1$, og jobber mot roten. Da er begge deltrærne alltid gyldige hauger før vi siver ned i en node.

Build-Max-Heap kjører i lineær tid: selv om hvert enkelt Max-Heapify-kall koster opptil $O(\lg n)$, er de aller fleste nodene grunne. Summerer vi det faktiske arbeidet over alle høydene konvergerer det til $O(n)$ — ikke $O(n \lg n)$.

def max_heapify(a, i, heap_size):
  l, r = 2*i + 1, 2*i + 2
  largest = i
  if l < heap_size and a[l] > a[largest]:
      largest = l
  if r < heap_size and a[r] > a[largest]:
      largest = r
  if largest == i:
      return                              # haug-egenskapen holder
  a[i], a[largest] = a[largest], a[i]     # bytt med største barn
  max_heapify(a, largest, heap_size)      # og siv videre nedover

def build_max_heap(a):
  n = len(a)
  for i in range(n // 2 - 1, -1, -1):     # interne noder, nedenfra og opp
      max_heapify(a, i, n)

def heapsort(a):
  build_max_heap(a)
  for size in range(len(a), 1, -1):
      a[0], a[size-1] = a[size-1], a[0]   # trekk ut maksimum til halen
      max_heapify(a, 0, size-1)           # gjenopprett haugen

Heapsort gjenbruker haugen som en sorteringsmaskin. Etter Build-Max-Heap er a[0] det største elementet; vi bytter det med det siste elementet i haugen, der det havner på sin endelige plass, krymper haugen med én og kjører Max-Heapify på roten igjen. Hver av de $n-1$ uttrekkingene koster $O(\lg n)$, så Heapsort sorterer in-place i $\Theta(n \lg n)$ — men den er ikke stabil.

Node- og pekerrepresentasjon

Haugen er kompakt nettopp fordi den er nesten komplett. Generelle rotfaste trær er ikke det, og lagres derfor med eksplisitte pekere: hver node er et objekt med en nøkkel og pekere til barn (og ofte til forelder). For trær med ukjent eller varierende forgreningsgrad bruker man «venstre barn, høyre søsken»-representasjonen, slik at hver node trenger bare to pekere uansett hvor mange barn den har. Denne fleksibiliteten er prisen vi betaler når strukturen ikke kan kodes implisitt i en tabell slik haugen kan.

Binære søketrær

Et Binært søketre ordner nøklene slik at søk blir retningsbestemt.

Søk utnytter dette direkte: i hver node sammenligner vi nøkkelen vår med x.key, og går til venstre eller høyre deltre. Dermed elimineres ett helt deltre ved hvert steg, akkurat som i binærsøk. De andre standardoperasjonene følger samme mønster og koster alle $O(h)$, der $h$ er treets høyde.

Siden alt koster $O(h)$, er høyden hele spørsmålet. Et balansert tre har $h = \Theta(\lg n)$ og gir logaritmiske operasjoner. Et degenerert tre — bygget ved å sette inn allerede sorterte nøkler — blir en lenket liste med $h = n-1$ og lineære operasjoner.

Forventningen gjelder bare for tilfeldig innsettingsrekkefølge — vi kan ikke stole på den hvis dataene kan komme sortert. Balanserte søketrær (som rød-svarte trær eller AVL-trær) gir derfor en garanti: ved å rebalansere under innsetting og sletting holder de $h = O(\lg n)$ for enhver sekvens, og dermed logaritmisk verste tilfelle for alle operasjonene.

Sjekk deg selv