Rotfaste trestrukturer

Et rotfast tre er en rekursiv dekomponering: hver node er rota i sitt eget deltre. Da kan du kreve noe av alle deltrærne på én gang. I et binært søketre er alt i venstre deltre mindre enn rota og alt i høyre deltre større. Egenskapen gir søk, innsetting og etterfølger i tid proporsjonal med høyden. I en haug kreves bare at rota er størst, og kravet gjelder rekursivt for hvert deltre. Haugegenskapen gir mindre funksjonalitet, men haugen er billigere å bygge og holder seg balansert av seg selv, så den brukes som prioritetskø og til å sortere.

Rotfaste trær

Et fritt tre er en sammenhengende graf uten sykler. Det har nøyaktig én sti mellom hvert par av noder, og $|E| = |V| - 1$. Velger du ut én node som rot, får du et rotfast tre, og da har kantene retning: rota har ingen forelder, hver annen node har nøyaktig én, og nodene rett under en node er barna dens.

Treet i figur 1 har rota 7. Barna til 7 er 5 og 6, og barna til 5 er 1, 2, 3 og 4. En node uten barn er en løvnode, som 1 og 6, og de andre er indre noder, her 5 og 7. Dybden til en node er antall kanter opp til rota, så 1 har dybde 2. Høyden $h$ til treet er den største dybden, her 2. Deltreet med rot $x$ er $x$ og alt under den, så deltreet med rot 5 har fem noder.

Et binærtre har to barneposisjoner per node, venstre og høyre, og en av dem kan stå tom. Du vet altså hvilket barn som mangler. Et komplett binærtre er fullt, alle indre noder har to barn, og alle løvnodene har samme dybde. Har treet høyde $h$, har nivåene $1, 2, 4, \ldots, 2^h$ noder. Løvnodene på nederste nivå er $2^h$, og nivåene over har $2^h - 1$ noder til sammen, så treet har $n = 2^{h+1} - 1$ noder i alt. Da er $2^h \le n < 2^{h+1}$, og $h = \lfloor \lg n \rfloor$. Balansert binærtre defineres på flere måter, men alle gir logaritmisk høyde.

En node i et binærtre har pekere left og right, og gjerne p til forelderen. Kan en node ha vilkårlig mange barn, holder det likevel med to pekere: én til første barn og én til neste søsken. Barna til en node er da en lenket liste som starter i første barn.

Binære søketrær

Hver node har en nøkkel key. Du kan anta at nøklene er forskjellige.

Egenskapen gjelder for hver node, ikke bare rota, så hvert deltre er selv et binært søketre. Den er binærsøk lagret som datastruktur: fra hver node vet du hvilken side en nøkkel må ligge på.

Inorder-Tree-Walk skriver ut venstre deltre, så noden, så høyre deltre, rekursivt fra rota. Egenskapen gir at utskriften er sortert: alt til venstre kommer før noden og er mindre, alt til høyre kommer etter og er større. Hver node besøkes én gang, så det tar $\Theta(n)$. Preorder og postorder skriver ut noden før eller etter de to rekursive kallene i stedet for mellom dem.

Tree-Search sammenligner nøkkelen $k$ med nøkkelen i $x$. Er de like, er $x$ svaret. Er $k$ mindre, kan den bare ligge i venstre deltre, så du søker videre der, ellers i høyre. Treffer du nil, finnes ikke $k$. Ingenting skjer etter det rekursive kallet, så søket skrives like gjerne som en løkke. Stien går nedover fra rota og er høyst $h$ lang, så søket koster $O(h)$.

Tree-Insert søker etter nøkkelen til den nye noden $z$ til søket treffer nil, og henger $z$ på der. Under søket følger $y$ ett steg bak $x$, så når $x$ blir nil, er $y$ noden som skal bli forelder. Er $y$ nil, var treet tomt, og $z$ blir rot. Ellers blir $z$ venstre eller høyre barn av $y$ etter samme test som i søket. En ny node blir alltid en løvnode.

def tree_insert(T, z):
  x, y = T.root, None
  while x is not None:
      y = x
      if z.key < x.key:
          x = x.left
      else:
          x = x.right
  z.p = y
  if y is None:
      T.root = z
  elif z.key < y.key:
      y.left = z
  else:
      y.right = z

def inorder_tree_walk(x):
  if x is not None:
      inorder_tree_walk(x.left)
      print(x.key)
      inorder_tree_walk(x.right)

Tree-Minimum følger left til det ikke går lenger, for alt i et høyre deltre er større enn noden over. Tree-Maximum følger right. Etterfølgeren til $x$ er noden med den minste nøkkelen som er større enn nøkkelen til $x$, altså den neste i Inorder-Tree-Walk. Har $x$ et høyre deltre, er etterfølgeren minimum der. Har $x$ ikke noe høyre deltre, er $x$ maksimum i et deltre, og etterfølgeren er den nærmeste noden over $x$ som har $x$ i sitt venstre deltre. Gå oppover så lenge du kommer fra et høyre barn. Forgjengeren finnes symmetrisk. Alle fire følger én sti opp eller ned, $O(h)$.

def tree_search(x, k):
  while x is not None and k != x.key:
      x = x.left if k < x.key else x.right
  return x

def tree_minimum(x):
  while x.left is not None:
      x = x.left
  return x

def tree_successor(x):
  if x.right is not None:
      return tree_minimum(x.right)
  y = x.p
  while y is not None and x is y.right:
      x, y = y, y.p
  return y

Tree-Delete skiller på hvor mange barn $z$ har. Har $z$ høyst ett barn, kobles barnet inn der $z$ sto, med hjelpeprosedyren Transplant. Har $z$ to barn, er etterfølgeren $y$ minimum i høyre deltre og har ikke noe venstre barn, så $y$ kan kobles ut på samme måte og settes inn der $z$ sto. Tree-Delete følger også én sti, $O(h)$.

Alle operasjonene unntatt traverseringen koster altså $O(h)$, og høyden avhenger av innsettingsrekkefølgen. Settes $1, 2, \ldots, 7$ inn i stigende rekkefølge, blir hver ny nøkkel høyre barn av den forrige, og treet er en kjede med høyde $n - 1$. Da koster søk $\Theta(n)$, som i en lenket liste. Settes de samme nøklene inn i rekkefølgen $4, 2, 6, 1, 3, 5, 7$, er treet komplett med høyde $\lfloor \lg n \rfloor$.

Med en tilfeldig innsettingsrekkefølge finner du den forventede dybden ved å telle sammenligninger. Når $z$ settes inn, sammenlignes den med hver node på stien fra rota ned til forelderen, og den stien har like mange noder som dybden $z$ får. Summen av dybdene er altså antall sammenligninger i hele byggingen. Rota deler de senere nøklene i mindre og større, og hvert deltre deler sine videre på samme måte. Det er de samme sammenligningene som Quicksort gjør når pivoten i hvert segment er den nøkkelen som ble satt inn først. I en tilfeldig permutasjon er den pivoten tilfeldig, og da gjør Quicksort forventet $\Theta(n \lg n)$ sammenligninger. Snittet av dybdene er derfor forventet $\Theta(\lg n)$, og det er kostnaden til et søk etter en tilfeldig nøkkel. Høyden er den største dybden, og en finere regning viser at også forventet høyde er $\Theta(\lg n)$. Verste tilfelle er fortsatt lineært. Det finnes søketrær som balanserer seg selv etter hver innsetting og sletting i logaritmisk tid, for eksempel rød-svarte trær, og de garanterer $h = \Theta(\lg n)$.

Hauger

En haug er et binærtre som er komplett ned til nest nederste nivå, og der det nederste nivået er fylt fra venstre. Nummererer du nodene nivå for nivå med rota som 1, har nivå $d$ numrene $2^d$ til $2^{d+1} - 1$. Node $i$ på nivå $d$ har $i - 2^d$ noder foran seg på nivået, og barna til dem, to per node, står først på nivået under. Det første barnet til $i$ får da nummeret $2^{d+1} + 2(i - 2^d) = 2i$, og det andre $2i + 1$. Barna $2i$ og $2i + 1$ har begge forelderen $i$, så forelderen til en node $j$ er $\lfloor j/2 \rfloor$. Numrene er indekser i en tabell, så haugen trenger ingen pekere. $A[1 .. n]$ er treet, Left, Right og Parent er regnestykker, og haugstørrelsen size sier hvor mye av tabellen som er haug.

Haugegenskapen sier ingenting om rekkefølgen mellom søsken, så en haug er langt fra sortert. Sorteringsgrensen gjelder når svaret er én bestemt av $n!$ rekkefølger, og den gjelder derfor ikke for å bygge en haug.

Har haugen høyde $h$, er nivåene $0, \ldots, h - 1$ fulle og har $1 + 2 + \cdots + 2^{h-1} = 2^h - 1$ noder til sammen, og det nederste nivået har fra 1 til $2^h$ noder. Da er $2^h \le n \le 2^{h+1} - 1$, og $h = \lfloor \lg n \rfloor$.

Max-Heapify reparerer en haug der bare $A[i]$ kan være for liten, altså der begge deltrærne under $i$ er maks-hauger. Finn den største av $A[i]$ og de to barna. Er det $A[i]$, er alt i orden. Ellers bytt $A[i]$ med det største barnet, så den nye rota er større enn begge, og reparer deltreet der det mindre elementet havnet, rekursivt. Elementet synker til det er større enn begge barna eller er en løvnode. Byttet må være med det største barnet, ellers blir den nye rota mindre enn det andre barnet. Stien går nedover, høyst $h$ steg, så Max-Heapify koster $O(\lg n)$.

Node $i$ har et venstre barn bare når $2i \le n$, så nodene fra $\lfloor n/2 \rfloor + 1$ til $n$ har ingen barn. De er løvnoder og dermed maks-hauger alene. Build-Max-Heap kaller Max-Heapify på de indre nodene fra $\lfloor n/2 \rfloor$ og ned til 1, nedenfra og opp i treet. Når turen kommer til $i$, er barna $2i$ og $2i + 1$ løvnoder eller allerede behandlet, for de har høyere numre. Begge deltrærne under $i$ er da maks-hauger, så forutsetningen for Max-Heapify holder, og etter kallet er også deltreet med rot $i$ en maks-haug.

def max_heapify(A, i, size):
  l, r = 2 * i + 1, 2 * i + 2  # indekser fra 0: rota er A[0]
  m = i
  if l < size and A[l] > A[m]:
      m = l
  if r < size and A[r] > A[m]:
      m = r
  if m != i:
      A[i], A[m] = A[m], A[i]
      max_heapify(A, m, size)

def build_max_heap(A, n):
  for i in range(n // 2 - 1, -1, -1):
      max_heapify(A, i, n)

$\lfloor n/2 \rfloor$ kall til Max-Heapify som hvert koster $O(\lg n)$, gir $O(n \lg n)$. Det er riktig, men ikke stramt, for nesten alle kallene er langt nede i treet, der det er lite å synke. Høyden til en node er høyden til deltreet med noden som rot, og en node med høyde $k$ synker høyst $k$ steg. Følger du venstre barn $k$ ganger fra node $i$, kommer du til node $2^k i$, det laveste nummeret $k$ nivåer under $i$, så $i$ har høyde minst $k$ nøyaktig når $2^k i \le n$. Nodene $1$ til $\lfloor n/2^k \rfloor$ har derfor høyde minst $k$, og de med høyde nøyaktig $k$ er nodene fra $\lfloor n/2^{k+1} \rfloor + 1$ til $\lfloor n/2^k \rfloor$, altså høyst $\lceil n/2^{k+1} \rceil$ av dem.

Arbeidet per node vokser lineært med høyden, men antallet noder synker eksponentielt med den, og den geometriske faktoren dominerer. Hver indre node besøkes, så $\Omega(n)$ gjelder også, og Build-Max-Heap er $\Theta(n)$.

Prioritetskøer

En prioritetskø holder en mengde elementer med nøkler og støtter Insert, Maximum, Extract-Max og Increase-Key, eller min-variantene. Nøklene er prioriteter, så duplikater er vanlige, i motsetning til i en oppslagstabell. En lenket liste gir innsetting i konstant tid, men lineær tid for å finne maksimum. En maks-haug gir alle fire i logaritmisk tid eller bedre.

Max-Heap-Maximum er $A[1]$, i konstant tid. Max-Heap-Extract-Max tar vare på rota, flytter det siste elementet i haugen opp i rota, minsker haugstørrelsen med én og kaller Max-Heapify på rota, for nå er rota det eneste som kan være feil. Å forskyve resten av tabellen ett hakk i stedet ville kostet $\Theta(n)$ og gitt hvert element en ny forelder.

Max-Heap-Increase-Key gir elementet på plass $i$ en større nøkkel. Nå kan det være større enn forelderen, så det stiger: bytt med forelderen så lenge den er mindre. Max-Heap-Insert legger det nye elementet sist i haugen med nøkkel $-\infty$ og øker nøkkelen til den riktige verdien, så det stiger på plass. Synking og stiging følger begge én sti i treet, $O(\lg n)$. Increase-Key trenger indeksen $i$ til elementet, så er elementene objekter, må haugen bokføre hvor hvert av dem står, og oppdatere det ved hvert bytte.

from math import inf

def max_heap_maximum(A):
  if len(A) < 1:
      raise ValueError("heap underflow")
  return A[0]

def max_heap_extract_max(A):
  m = max_heap_maximum(A)
  A[0] = A[-1]
  A.pop()
  max_heapify(A, 0, len(A))
  return m

def max_heap_increase_key(A, i, key):
  if key < A[i]:
      raise ValueError("new key is smaller")
  A[i] = key
  # indekser fra 0: forelderen til i er (i - 1) // 2
  while i > 0 and A[(i - 1) // 2] < A[i]:
      A[i], A[(i - 1) // 2] = A[(i - 1) // 2], A[i]
      i = (i - 1) // 2

def max_heap_insert(A, key):
  A.append(-inf)
  max_heap_increase_key(A, len(A) - 1, key)

Heapsort

Sortering ved utvelgelse plukker ut det største av de usorterte elementene og legger det bakerst, $n$ ganger, og bruker $\Theta(n)$ per plukk. Heapsort gjør det samme med en maks-haug som usortert del, så hvert plukk er en Extract-Max. Bygg haugen av hele $A$. Så, for $i$ fra $n$ ned til 2: bytt rota $A[1]$ med $A[i]$, minsk haugstørrelsen med én og kall Max-Heapify på rota.

Invarianten er at $A[i+1 .. n]$ er de $n - i$ største elementene, sortert, og at $A[1 .. i]$ er en maks-haug. Rota er det største elementet i $A[1 .. i]$, så byttet legger det på plass $i$, rett foran de $n - i$ elementene som allerede er sortert. Etter byttet er bare den nye rota feilplassert i $A[1 .. i - 1]$, og Max-Heapify flytter den på plass. Sorteringen skjer på plass: haugen ligger foran i tabellen, og den sorterte delen vokser bakfra.

def heapsort(A, n):
  build_max_heap(A, n)
  size = n
  for i in range(n - 1, 0, -1):
      A[0], A[i] = A[i], A[0]
      size = size - 1
      max_heapify(A, 0, size)

Byggingen koster $\Theta(n)$, og så følger $n - 1$ kall til Max-Heapify på $O(\lg n)$ hver, altså $O(n \lg n)$. Heapsort er sammenligningsbasert, så sorteringsgrensen gir $\Omega(n \lg n)$ i verste tilfelle, og verste tilfelle er derfor $\Theta(n \lg n)$. Er alle elementene like, stopper hvert Max-Heapify med en gang, og beste tilfelle er $\Theta(n)$. Med forskjellige elementer er også beste tilfelle $\Theta(n \lg n)$, så sortert input gjør ikke Heapsort raskere.

Sjekk deg selv