4.2 Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon

Prebetingelse: treet oppfyller BST-egenskapen, og a er ikke større enn
b.
Postbetingelse: nøyaktig de verdiene som ligger mellom a og b er
skrevet ut, i stigende rekkefølge, og treet er uendret.

Procedure InRange(v, a, b)
  Input:  rota v i et BST (nil hvis subtreet er tomt), nedre grense a, oevre grense b
  Output: alle verdier x i subtreet med a <= x <= b, skrevet ut i stigende rekkefoelge
  if v er nil:
      return
  if a < v.x:
      InRange(v.left, a, b)
  if a <= v.x and v.x <= b:
      skriv ut v.x
  if v.x < b:
      InRange(v.right, a, b)

Grunnideen i én setning: dette er in-order-traverseringen fra
kap. 4.1 med to vakter satt foran de rekursive kallene —
venstre besøkes bare hvis det kan finnes noe stort nok der, høyre bare hvis det
kan finnes noe lite nok.

De to vaktene er hele forskjellen, og de er verdt å lese én gang til:

- if a < v.x — er noden allerede mindre enn eller lik nedre grense, er alt i
venstre subtre for lite. Hopp over.
- if v.x < b — er noden allerede større enn eller lik øvre grense, er alt i
høyre subtre for stort. Hopp over.

Kjøretid: $O(\log n + t)$ i et balansert tre, der $n$ er antall noder og
$t$ er antall verdier som faktisk skrives ut. Begrunnelsen er todelt:
algoritmen følger to søkeveier ned gjennom treet, én for hver grense, og det
koster $O(h) = O(\log n)$; alt annet den besøker, er noder som enten skrives ut
eller ligger mellom de to søkeveiene, og det er $O(t)$ av dem. Generelt skrives
kjøretiden $O(h + t)$, siden $h$ er $n-1$ i et degenerert tre.

Spesialtilfellet du bør nevne: er a lik b, er $t$ høyst 1, og
kjøretiden blir $O(\log n)$. Da er InRange blitt et vanlig søk.

Poengtrapp-notat. Den naive løsningen — full InOrder med en
if-test på hver verdi — er $O(n)$ og gir typisk omtrent halv uttelling. Den
er ikke gal, den er bare dyrere enn nødvendig, og det er nettopp det
poengtrappen straffer.

Prebetingelse: ingen, ut over at rot peker på et tre eller er nil.
Postbetingelse: returverdien er antall kanter på den lengste stien i treet;
treet er uendret.

Procedure Diameter(rot)
  Input:  rota i et binaert tre (nil hvis treet er tomt)
  Output: lengden paa den lengste stien i treet, maalt i kanter
  maks = 0
  Hoyde(rot)
  return maks

Procedure Hoyde(v)
  Input:  noden v (kan vaere nil)
  Output: hoeyden til subtreet med rot v, maalt i kanter; -1 for tomt subtre
  if v er nil:
      return -1
  hL = Hoyde(v.left)
  hR = Hoyde(v.right)
  if hL + hR + 2 > maks:
      maks = hL + hR + 2
  return 1 + storste av hL og hR

Grunnideen i én setning: Hoyde regner ut det den er bedt om og noterer
samtidig, gratis, den lengste stien som passerer gjennom noden den står i — så
når rekursjonen er ferdig, er alle noder prøvd som toppunkt.

Rekkefølgen er post-order: begge barna er ferdige før noden selv gjør noe.
Det er nettopp derfor hL og hR er tilgjengelige når maks skal oppdateres.

Kjøretid: $O(n)$, der $n$ er antall noder. Hver node får nøyaktig ett
Hoyde-kall, og arbeidet i kallet er to sammenligninger og en addisjon utenom
rekursjonen — altså konstant per node.

Rekursjonen har én kostnad til, og den skal du nevne én gang i besvarelsen:
kallstakken blir like dyp som treet, altså $O(h)$ i minne. På et balansert tre
er det $O(\log n)$ og helt ufarlig; på et skjevt tre er $h = n - 1$, og da
bruker algoritmen $O(n)$ minne. Det er et fint delpoeng å ta med, og det er den
eneste prisen rekursjonen har her.

Poengtrapp-notat. Varianten som kaller Hoyde på nytt i hver node er
$O(n^2)$ og gir tydelig mindre uttelling enn denne, selv om den gir riktig
svar. På en diameteroppgave har trappen vært eksplisitt i veiledningen: den
lineære løsningen gir full pott, den kvadratiske noe under to tredjedeler.

Prebetingelse: treet oppfyller BST-egenskapen.
Postbetingelse: returverdien er den dypeste noden som har både x og y i
sitt subtre; treet er uendret.

Procedure LCA(v, x, y)
  Input:  rota v i et BST, to verdier x og y som finnes i treet, med x <= y
  Output: noden som er naermeste felles forfar til x og y
  while v er ikke nil:
      if y < v.x:
          v = v.left
      else if v.x < x:
          v = v.right
      else:
          return v
  return nil

Grunnideen i én setning: så lenge begge verdiene ligger på samme side av
noden, kan ikke noden være den nærmeste felles forfaren — og første gang de
ikke gjør det, er den det.

Merk at else-grenen også dekker tilfellet der v.x er lik x eller y. En
node regnes som sin egen forfar, så hvis den ene verdien ligger i noden og den
andre under den, er noden svaret.

Kjøretid: $O(h)$, der $h$ er høyden. Løkka går ett nivå ned per runde og
aldri opp igjen. I et balansert tre er det $O(\log n)$; på et skjevt tre
$O(n)$.

Varianten for et generelt tre — der verdiene ikke er ordnet og du i stedet
har v.parent og v.depth — går slik:

Procedure LCAGenerelt(u, w)
  Input:  to noder u og w i et tre der hver node har parent og depth
  Output: naermeste felles forfar til u og w
  while u.depth > w.depth:
      u = u.parent
  while w.depth > u.depth:
      w = w.parent
  while u er ikke lik w:
      u = u.parent
      w = w.parent
  return u

Også $O(h)$: først løftes den dypeste opp til lik dybde, så går begge oppover i
takt. Oppgi hvilken av de to du har antatt — sensor binder seg ikke til
representasjonen, men du må si hva du forutsetter.

Prebetingelse: ingen — det er nettopp gyldigheten som skal avgjøres.
Postbetingelse: returverdien er sant hvis og bare hvis subtreet under v
er et gyldig BST med alle verdier strengt inne i intervallet; treet er uendret.

Procedure CheckBST(v, low, high)
  Input:  noden v, og intervallet (low, high) som alle verdier i subtreet maa ligge i
  Output: sant hvis subtreet med rot v er et gyldig BST innenfor intervallet
  if v er nil:
      return sant
  if v.x <= low or v.x >= high:
      return usant
  return CheckBST(v.left, low, v.x) and CheckBST(v.right, v.x, high)

Kalles på hele treet som CheckBST(rot, -uendelig, +uendelig).

Invarianten i én setning: når kallet gjøres på en node, inneholder
intervallet (low, high) nøyaktig de verdiene som er lovlige der ut fra alle
forfedrene — så en node som bryter mot noe langt oppe i treet, blir tatt her
og ikke først senere.

Se hvordan intervallet strammes: går du til venstre, blir noden det nye
taket; går du til høyre, blir den det nye gulvet. Det er hele mekanismen.

Kjøretid: $O(n)$, der $n$ er antall noder. Hver node får ett kall, og
arbeidet per kall er to sammenligninger. I praksis stopper algoritmen ved
første brudd, men verste tilfelle — et gyldig tre — krever at alle noder
sjekkes.

Alternativet som også er $O(n)$: kjør InOrder og sjekk at utskriften er
strengt stigende. Den er like god, og den er lettere å forklare i naturlig
språk — noe som gir full uttelling så lenge forklaringen er entydig.

Poengtrapp-notat. Å hente Min og Maks i hvert subtre for hver node gir
riktig svar i $O(n^2)$ og dermed klart mindre uttelling. Å bare sammenligne
hver node med sine to barn er gal og gir tilsvarende lite, uansett hvor
pent den er skrevet.