7.1 ADT-design — mediankø, bøttekø og trie

Å velge og kombinere strukturer til en abstrakt datatype — mediankø (to heaps), bøttekø (array av lister) og trie — med kjøretid per operasjon.

50 min

5 oppgaver

ADT-designmediankøbøttekøtrie

Din fremgang i kapitlet

0 / 5 oppgaver

Kapitlets plass i kurset

Bygger på

4.4Heap og prioritetskø

ADT-design er med i 3 av 7 sett (43 %), og andelen er økende — de tre
forekomstene ligger i de nyeste settene. Sjangeren er

- Sjanger J — designskisse med kjøretid, altså at du velger og kombinerer
datastrukturer for å støtte et sett operasjoner, beskriver løsningen og oppgir
kjøretiden per operasjon.

Dette er ikke en oppgave der du skriver mye kode. Det er en oppgave der du
velger, og der begrunnelsen er svaret. Tre design går igjen: mediankøen (to
heaps), bøttekøen (array av lister) og trie-et (prefikstre).

Prioritet: kunne (nivå 2 av tre — «må sitte» er nivå 1, «kjenne til» er
nivå 3). Sjangeren er en av dem som skiller toppsjiktet, fordi den krever at du
kjenner kjøretidene til strukturene fra Del 3 og Del 4 godt nok til å sette dem
sammen på nytt.

En ting er verdt å si med én gang: det finnes sjelden ett riktig svar. Sensor
vurderer om løsningen virker og om kjøretiden du oppgir, stemmer med den. En
heap-basert løsning som gir $O(\log n)$ der en array-basert gir $O(1)$ , er
korrekt — den gir bare færre poeng.

Slik er kapitlet lagt opp (50 min): fire løkker med teori, gjennomkjørt
eksempel og oppgaver, med et pausepunkt etter løkke 2.

Sist du var her — forkunnskaper i kortform

Tre resultater fra tidligere deler er hele byggematerialet her. De står ferdig
oppfrisket:

1. Min-heapen er et array med indeks fra 0. Forelder til $i$ er
$\lfloor (i-1)/2 \rfloor$ , barna er $2i+1$ og $2i+2$ . Insert og RemoveMin
koster $O(\log n)$ ; å lese toppen uten å fjerne den er $O(1)$ . Å bygge en heap
fra et array er $O(n)$ , ikke $O(n \log n)$ . Se
kap. 4.4.

2. En max-heap er samme struktur med snudd ordning. Forelderen er større
enn begge barna, så toppen er det største elementet. Alt annet er identisk.

3. Hashmap og hash-set er $O(1)$ forventet, $O(n)$ verste. Ordet «forventet» er
obligatorisk. Se kap. 3.2. Har du brukt en ordbok i et
program, er det denne strukturen: Ordbøker.

Fra kap. 4.1 trengs også at et binært søketre gir sortert
rekkefølge ved in-order-traversering.

Notasjons- og pseudokodeliste

Løkke 1 — hva oppgaven egentlig ber om (ca. 8 min)

En abstrakt datatype er et sett operasjoner med en kontrakt, uten at det er
sagt hvordan de skal implementeres. «En struktur som støtter Insert(x) og
Median()» er en abstrakt datatype; en max-heap er en implementasjon.

Eksamensoppgaven gir deg alltid det første og ber om det andre. Formen er fast:

«Design en datastruktur som støtter operasjonene … effektivt. Beskriv
strukturen og oppgi kjøretiden per operasjon.»

Det er ordet per operasjon som er nøkkelen. Du skal ikke oppgi én samlet
kjøretid — du skal gå gjennom operasjon for operasjon og si hva hver av dem koster.
En besvarelse som sier « $O(\log n)$ » uten å spesifisere hva, mister poeng selv om
løsningen er riktig.

Abstrakt datatype (ADT)

Et sett operasjoner med en beskrevet oppførsel, uten at implementasjonen er fastlagt. En prioritetskø er en ADT: den lover Insert og RemoveMin . En min-heap er en implementasjon av den ADT-en; et AVL-tre er en annen. Å skille de to nivåene er hele poenget med sjangeren — oppgaven gir deg kontrakten, du velger implementasjonen.

📜Svarformen på en ADT-design-oppgave

Fire ledd, i denne rekkefølgen. Dette er sensors faktiske krav, og mangler ett av
dem, trekkes det.

1. Hvilke strukturer bruker du, og hva lagrer hver av dem? «To heaps: en
max-heap med den nedre halvdelen av tallene, en min-heap med den øvre.»
2. Hva er invarianten? Den regelen som må holde etter hver operasjon, og som
gjør at operasjonene blir billige. «De to heapene er like store, eller max-heapen
har ett element mer.»
3. Hver operasjon, steg for steg, og hvordan invarianten gjenopprettes.
4. Kjøretid per operasjon, med $n$ definert.

Og til slutt spørsmålet som gir det siste poenget: kan noen av operasjonene
gjøres raskere? Ofte kan én av dem senkes fra $O(\log n)$ til $O(1)$ ved å lagre
litt ekstra — og det er nettopp den forbedringen poengtrappen belønner.

📝Oppgave 1

(Innstegsoppgave, sjanger J — ADT-design, altså at du velger og kombinerer
strukturer og oppgir kjøretiden per operasjon.) En struktur skal støtte
Insert(x) og HentMinste(), der HentMinste fjerner og returnerer det minste
elementet.

a) Hvilken kjent struktur løser dette direkte?
b) Oppgi kjøretiden per operasjon.
c) Hva ville en usortert liste gitt i stedet?

Løkke 2 — mediankøen: to heaps som møtes på midten (ca. 15 min)

Nå en oppgave der ingen enkelt struktur holder.

Et vaktsystem tar imot responstider fortløpende, og skal til enhver tid kunne
oppgi medianen — det midterste tallet når alle er sortert. Operasjonene er
Insert(x) og Median().

En sortert liste gir Median() i $O(1)$ , men Insert blir $O(n)$ fordi alt bak
innsettingspunktet må flyttes. En min-heap gir Insert i $O(\log n)$ , men
medianen ligger et sted midt i arrayet, uten fast plass — å finne den koster
$O(n)$ .

Trikset er å bruke to heaps. Del tallene i to like store halvdeler: den nedre
halvdelen i en max-heap (så det største av de små ligger på toppen), og den
øvre halvdelen i en min-heap (så det minste av de store ligger på toppen). Da
ligger medianen alltid på toppen av max-heapen — rett ved skillet.

Mediankø

O(\log n)

📜Pseudokode-kontrakt: `Mediankø`

Antagelser om representasjon. nedre er en max-heap og ovre er en
min-heap, begge implementert som array med indeks fra 0 (se
kap. 4.4). Begge støtter Insert og RemoveTopp i

O(\log n)

, og Topp i

O(1)

. Størrelsen på en heap leses i

O(1)

Invariant (må holde etter hver operasjon):
alle tall i nedre er mindre enn eller lik alle tall i ovre, og
$\lvert \text{nedre} \rvert = \lvert \text{ovre} \rvert$ eller
$\lvert \text{nedre} \rvert = \lvert \text{ovre} \rvert + 1$ .

Procedure Insert(x)
  Input:  et tall x
  Output: strukturen inneholder x, og invarianten holder
  if nedre er tom or x <= nedre.Topp():
      nedre.Insert(x)
  else:
      ovre.Insert(x)
  // gjenopprett balansen — hoyst én flytting
  if storrelsen paa nedre > storrelsen paa ovre + 1:
      ovre.Insert(nedre.RemoveTopp())
  else if storrelsen paa ovre > storrelsen paa nedre:
      nedre.Insert(ovre.RemoveTopp())

Procedure Median()
  Input:  ingenting
  Output: medianen av alle innsatte tall
  return nedre.Topp()

Hvorfor invarianten gir medianen: er de to like store, er nedre.Topp() det
største av den nedre halvdelen — altså det nedre av de to midterste tallene. Har
nedre ett element mer, er toppen der det midterste tallet. I begge tilfeller er
Median() bare et oppslag.

Kjøretid: Insert er $O(\log n)$ — én heap-innsetting, pluss høyst én
flytting som er ett uttak og én innsetting, alle $O(\log n)$ . Median() er
$O(1)$ , siden toppen av en heap ligger på indeks 0.

Merk at balanseringen aldri trenger mer enn én flytting. Størrelsene endrer
seg med 1 per innsetting, så avviket kan aldri bli mer enn 1 for stort.

✏️Eksempel 1: Håndkjøring av mediankøen

Responstidene 14, 9, 21, 3, 17, 12 og 25 kommer inn i denne rekkefølgen. Vis
tilstanden til begge heapene etter hver innsetting, og oppgi medianen underveis.

Heapene vises som array med indeks fra 0. I max-heapen ligger det største
elementet på indeks 0; i min-heapen ligger det minste der.

Steg	Sett inn	Rebalansering	Nedre (max-heap, array)	Øvre (min-heap, array)	Median etter steget
1	14	—	`14`	`tom`	14
2	9	14 flyttes fra nedre til øvre	`9`	`14`	9
3	21	14 flyttes fra øvre til nedre	`14, 9`	`21`	14
4	3	14 flyttes fra nedre til øvre	`9, 3`	`14, 21`	9
5	17	14 flyttes fra øvre til nedre	`14, 3, 9`	`17, 21`	14
6	12	14 flyttes fra nedre til øvre	`12, 3, 9`	`14, 21, 17`	12
7	25	14 flyttes fra øvre til nedre	`14, 12, 9, 3`	`17, 21, 25`	14

Sluttilstand — dette er svaret du leverer:

nedre (max-heap):  14, 12, 9, 3
ovre  (min-heap):  17, 21, 25
Median:            14

Kontrollen: sorter alle sju tallene — 3, 9, 12, 14, 17, 21, 25. Det midterste
er 14. Stemmer.
Se på steg 5. Tallet 17 er større enn nedre.Topp() (som er 9 der), så det går
i ovre. Da blir ovre større enn nedre, og 14 flyttes tilbake ned. Det er
balanseringen i arbeid: ett tall over skillet per innsetting, høyst.
Se på hvordan medianen beveger seg: 14, 9, 14, 9, 14, 12, 14. Den hopper opp

og ned, som den skal — med et partall elementer velger denne implementasjonen det

nedre av de to midterste. Sier oppgaven at medianen av et partall skal være

gjennomsnittet av de to midterste, leser du bare begge toppene og deler på to.
Det er fortsatt $O(1)$ .

Fellenote. Fella her er å bruke én heap. Med bare en min-heap ligger
medianen et vilkårlig sted i arrayet, og du må lete gjennom alt: $O(n)$ i stedet
for $O(1)$ . Det er en korrekt løsning som taper poengtrappen.

📝Oppgave 2

Sjanger E

Tallene 7, 2, 11, 4 og 9 settes inn i en mediankø i denne
rekkefølgen.

a) Vis begge heapene etter hver innsetting.
b) Oppgi medianen til slutt, og kontrollér den mot den sorterte rekken.
c) Hvor mange elementer flyttes mellom heapene til sammen?

— naturlig pausepunkt —

Mediankøen er den vanligste ADT-designoppgaven. De to neste — bøttekøen og trie-et
— er kortere, men de tester noe annet: at du tør å velge en enklere struktur
enn den du kan best.

Løkke 3 — bøttekøen: når heapen er overkill (ca. 12 min)

Nå en oppgave der den opplagte løsningen gir færre poeng enn den enkle.

Et meldingssystem behandler meldinger etter prioritet. Prioritetene er hele tall
fra 0 til 9 — et fast, lite antall nivåer, uavhengig av hvor mange meldinger
som ligger i køen. Operasjonene er Insert(melding, prioritet) og RemoveMin(),
som tar den viktigste ventende meldingen.

En min-heap løser dette: $O(\log n)$ per operasjon. Men se på forutsetningen én
gang til: bare ti prioritetsnivåer. Da trenger du ingen heap. Lag et array med
ti bøtter, én per prioritet, og la hver bøtte være en lenket liste med meldingene
på det nivået.

Bøttekø

N

📜Pseudokode-kontrakt: `Bøttekø`

Antagelser om representasjon. botter er et array med N plasser, indeksert
fra 0 til N-1, der hver plass er en lenket liste med

O(1)

innsetting bakerst
og

O(1)

uttak forrest. Prioritetene er heltall i 0..N-1, og N er et fast
tall som ikke vokser med antall elementer.

Prebetingelse: 0 <= p < N. Postbetingelse for RemoveMin: returnerer et
element med lavest prioritet blant dem som ligger i køen, eller melder at køen er
tom.

Procedure Insert(x, p)
  Input:  element x med prioritet p, der 0 <= p < N
  Output: x ligger bakerst i botte p
  botter[p].leggTilBakerst(x)

Procedure RemoveMin()
  Input:  ingenting
  Output: et element med lavest prioritet, eller melding om at koen er tom
  for p = 0 til N-1:
      if botter[p] er ikke tom:
          return botter[p].taUtForrest()
  return «koen er tom»

Grunnideen i én setning: når prioritetene er få og kjente på forhånd, trenger
du ikke sortere dem — du kan gi hver sin plass og slå opp direkte.

Kjøretid: Insert er $O(1)$ — ett arrayoppslag og én innsetting bakerst i en
lenket liste. RemoveMin er $O(N)$ i verste tilfelle, som er $O(1)$ når $N$ er
konstant. Merk at kjøretiden ikke avhenger av $n$ , altså hvor mange elementer som
ligger i køen — bare av antall nivåer.

Bonusen som er verdt å nevne: køen er stabil. To elementer med samme
prioritet kommer ut i den rekkefølgen de ble satt inn, fordi hver bøtte er en
FIFO-liste. Det gir en heap deg ikke uten videre.

✏️Eksempel 2: Håndkjøring av bøttekøen

Et meldingssystem har prioritetsnivåene 0 til 4, der 0 er viktigst. Utfør denne
sekvensen og vis køens tilstand etter hvert steg:

Insert(M4, 3), Insert(M1, 0), Insert(M7, 3), RemoveMin(),
Insert(M2, 1), RemoveMin(), RemoveMin(), RemoveMin(),
RemoveMin().

Kolonnen til høyre viser bare de ikke-tomme bøttene, med innholdet i hver.

Steg	Operasjon	Returnerer	Ikke-tomme bøtter etter
1	`Insert(M4, prioritet 3)`	—	`3: [M4]`
2	`Insert(M1, prioritet 0)`	—	`0: [M1]; 3: [M4]`
3	`Insert(M7, prioritet 3)`	—	`0: [M1]; 3: [M4, M7]`
4	`RemoveMin()`	`M1` (prioritet 0)	`3: [M4, M7]`
5	`Insert(M2, prioritet 1)`	—	`1: [M2]; 3: [M4, M7]`
6	`RemoveMin()`	`M2` (prioritet 1)	`3: [M4, M7]`
7	`RemoveMin()`	`M4` (prioritet 3)	`3: [M7]`
8	`RemoveMin()`	`M7` (prioritet 3)	`alle bøtter tomme`
9	`RemoveMin()`	køen er tom	`alle bøtter tomme`

Sluttilstand — dette er svaret du leverer:

Uttaksrekkefolge: M1, M2, M4, M7, deretter «koen er tom»
Alle botter tomme

Se på steg 7 og 8. Både M4 og M7 har prioritet 3, og de kommer ut i den
rekkefølgen de ble satt inn. Det er stabiliteten — hver bøtte er en FIFO-liste.
En min-heap ville ikke gitt noen garanti om innbyrdes rekkefølge for like nøkler.
Se på steg 4. RemoveMin skanner fra bøtte 0, finner M1 med én gang, og
returnerer. I steg 6 må den skanne forbi bøtte 0 (nå tom) og finner M2 i bøtte 1.
Skanningen kan i verste fall gå gjennom alle fem bøttene — men fem er et fast tall.
Sammenligning med en heap. En min-heap ville gitt samme uttaksrekkefølge for
prioritetene (men ikke nødvendigvis for M4 og M7 innbyrdes), til

O(\log n)

per operasjon i stedet for $O(1)$ . Med mange meldinger og få nivåer er bøttekøen

klart raskere.

Fellenote. Fella her er å gripe til heapen fordi oppgaven sier
«prioritetskø». Les forutsetningen: er antall prioritetsnivåer fast og lite?
Er svaret ja, er bøttekøen det øverste trinnet i poengtrappen, og en heap-basert

løsning gir mindre.

📝Oppgave 3

Sjanger J

En kølapp-app i et venterom har tre hastegrader: akutt (0), vanlig
(1) og lav (2). Systemet skal støtte Insert(pasient, hastegrad) og NesteInn().

a) Foreslå en struktur og oppgi kjøretid per operasjon.
b) Hvorfor er en min-heap et dårligere valg her?
c) Hva ville skjedd med argumentet ditt hvis hastegraden i stedet var et
tall mellom 0 og 1 000 000?

Løkke 4 — trie-et: strukturen som kjenner prefikser (ca. 12 min)

Den tredje faste ADT-oppgaven handler om autocomplete: du skriver noen
bokstaver, og systemet skal finne alle ord som begynner slik.

Et hashmap løser oppslaget «finnes dette ordet?» i $O(1)$ forventet. Men det løser
ikke «hvilke ord begynner med sa?» — hashverdien til sa har ingen
sammenheng med hashverdien til sand. Du måtte gått gjennom alle ordene og sjekket
hver enkelt: $O(\text{antall ord})$ .

Trie-et lagrer ordene bokstav for bokstav i et tre, slik at alle ord med samme
prefiks havner i samme subtre.

Trie (prefikstre)

O(L)

📜Pseudokode-kontrakt: `Trie`

Antagelser om representasjon. Hver node har et kart barn fra bokstav til
node (et lite array eller et hashmap), og et flagg erOrdslutt. Rota representerer
det tomme prefikset.

L

er lengden på ordet eller prefikset.

Postbetingelse for SettInn: ordet finnes i treet, og erOrdslutt er satt på
den siste noden.

Procedure SettInn(rot, ord)
  Input:  rota i et trie, og et ord
  Output: ordet er lagret i treet
  v = rot
  for hver bokstav b i ord:
      if v.barn har ingen oppfoering for b:
          v.barn[b] = ny tom node
      v = v.barn[b]
  v.erOrdslutt = sant

Procedure FinnPrefiks(rot, p)
  Input:  rota i et trie, og et prefiks p
  Output: noden som svarer til p, eller «ingen»
  v = rot
  for hver bokstav b i p:
      if v.barn har ingen oppfoering for b:
          return «ingen»
      v = v.barn[b]
  return v

Grunnideen i én setning: alle ord med samme prefiks deler den samme veien ned
fra rota, så prefikset peker rett på subtreet som inneholder dem.

Kjøretid: SettInn og FinnPrefiks er $O(L)$ — ett steg per bokstav,
uavhengig av hvor mange ord treet inneholder. Å liste alle ordene under et
prefiks koster i tillegg tid proporsjonal med antall treff, siden hvert av dem må
skrives ut.

Hvorfor erOrdslutt er nødvendig: uten flagget kan treet ikke skille «sal» —
som er et helt ord — fra en node som bare er passert på vei til «salt». Det er et
kanttilfelle sensor gir delpoeng for å ha tenkt på.

✏️Eksempel 3: Eksamensnivå — autocomplete

Et søkefelt skal foreslå ord mens brukeren skriver. Ordlista har $m$ ord, og det
lengste er $L$ bokstaver. Design en struktur som støtter SettInn(ord) og
Forslag(prefiks), som gir alle ord med det gitte prefikset.

Sammenlign med en hashmap-basert løsning, på kjøretid og minne.

Strukturene. Et trie: hver node har et kart fra bokstav til barnenode, og
et flagg erOrdslutt.

Invariant. Veien fra rota til en node staver nøyaktig det prefikset noden
representerer, og erOrdslutt er satt nøyaktig på de nodene som avslutter et
lagret ord.

Operasjonene.

- SettInn(ord): følg eller lag én node per bokstav; sett erOrdslutt på den
siste. $O(L)$ .
- Forslag(prefiks): følg prefikset ned fra rota. Finnes ikke veien, er svaret
tomt. Ellers: traversér subtreet under noden og samle alle ordslutt-noder.
$O(L + k)$ , der $k$ er antall treff.

Kjøretiden er uavhengig av $m$ . Å ha en million ord i treet gjør ikke oppslaget
tregere — bare treet større. Det er den avgjørende egenskapen.

Sammenligning med hashmap.

Trie	Hashmap
`SettInn(ord)`	$O(L)$	$O(L)$ forventet (hashing leser hele ordet)
«finnes ordet?»	$O(L)$	$O(L)$ forventet, $O(m \cdot L)$ verste
`Forslag(prefiks)`	$O(L + k)$	$O(m \cdot L)$ — må sjekke hvert ord
Minne	én node per unik prefiksbokstav	ett oppslag per ord

Konklusjonen, skarpt formulert: for autocomplete er trie-et det riktige
valget. Hashmap-et er like raskt på eksakte oppslag, men på prefikssøk må det gå
gjennom hele ordlista, og det er forskjellen mellom

O(L + k)

O(m \cdot L)

— altså mellom «uavhengig av ordlistas størrelse» og «lineær i
den».

Prisen er minne. Et trie bruker mer plass enn et hashmap, fordi hver bokstav i
hvert unikt prefiks blir en node med plass til barn. Er ordlista liten, eller
gjøres det bare eksakte oppslag, er hashmap-et bedre. Er prefikssøk hovedbruken,
er trie-et det verdt.
Poengtrapp-notat. Full uttelling krever tre ting: strukturen beskrevet,

kjøretid per operasjon, og en sammenligning som ender i en konklusjon — ikke
bare «det kommer an på». En besvarelse som foreslår hashmap og oppgir
$O(m \cdot L)$ for prefikssøket, er korrekt og ærlig, og gir delvis uttelling. En
som foreslår hashmap og påstår at prefikssøk er $O(1)$ , er derimot feil, og det er

en dyrere feil enn å velge feil struktur.

📝Oppgave 4

Sjanger J

Et system skal støtte Insert(x), Median() og i tillegg
FjernMedian(), som fjerner og returnerer medianen.

a) Kan mediankøen fra løkke 2 utvides til å støtte FjernMedian()?
b) Oppgi kjøretiden for alle tre operasjonene.
c) Hva må gjøres etter at medianen er fjernet?

Typiske feil

- Å bruke én heap til mediankøen. Med bare én heap ligger medianen et
vilkårlig sted i arrayet, og du må lete: $O(n)$ i stedet for $O(1)$ . Korrekt
løsning, men den taper poengtrappen.
- Å glemme å holde de to heapene balansert. Uten balanseringen er ikke toppen
av max-heapen medianen, og hele designet faller sammen. Invarianten er svaret —
skriv den ned først.
- Å velge heap der bøttekø er raskere. Er antall prioritetsnivåer et fast, lite
tall, gir bøttekøen $O(1)$ mot heapens $O(\log n)$ . Les forutsetningen i
oppgaveteksten før du velger.
- Å ikke oppgi kjøretid per operasjon. Sjangeren spør eksplisitt om det. Én
samlet kjøretid er ikke et svar, og « $O(\log n)$ » uten å si for hvilken
operasjon, gir lite.
- Å påstå at et hashmap gir raskt prefikssøk. Det gjør det ikke:
hashverdien til sa har ingen sammenheng med hashverdien til sand. Å ikke se
det er en dyrere feil enn å velge feil struktur, fordi kjøretiden da er direkte
gal.
- Å glemme ordslutt-merket i et trie. Uten det kan strukturen ikke skille et
helt ord fra et prefiks som bare passeres på veien.

Og den gjennomgående: å ikke definere $n$ . I dette kapitlet er $n$ antall
lagrede elementer, $N$ antall prioritetsnivåer og $L$ lengden på et ord — tre helt
forskjellige størrelser. Å bruke dem om hverandre er felle #10, og det trekkes
eksplisitt for det.

📝Oppgave 5

Sjanger J, krevende

En struktur skal støtte tre operasjoner på en samling
heltall: Insert(x), Finnes(x) og HentMinste() (som fjerner og returnerer det
minste).

a) Hvorfor holder det ikke med bare en min-heap?
b) Foreslå en kombinasjon av strukturer, og oppgi kjøretid per operasjon.
c) Hva er invarianten, og hva må gjøres i hver operasjon for å holde den?

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Mediankøens invariant

\lvert \text{nedre} \rvert = \lvert \text{øvre} \rvert \quad \text{eller} \quad \lvert \text{nedre} \rvert = \lvert \text{øvre} \rvert + 1

Hvorfor to heaps og ikke én

O(n)

Mediankøens kjøretider

O(\log n)

Bøttekø

N

Bøttekø mot heap

O(1)

Trie (prefikstre)

O(L)

Hvorfor hashmap ikke gir prefikssøk

O(m \cdot L)

Trie mot hashmap

O(L)

Svarformen på en ADT-oppgave

n

Heap-egenskapen gir ikke søk

O(n)

Å kombinere to strukturer

Standardgrepet når ingen enkeltstruktur gir alle operasjonene billig: hold de samme dataene i to strukturer samtidig, én per operasjonstype. Prisen er dobbelt minnebruk, og kravet er en invariant om at strukturene til enhver tid inneholder det samme. Glemmer du å oppdatere begge i hver operasjon, blir feilen usynlig helt til noe svarer galt.

Å velge enklere enn du kan

Den vanligste tapte poengen i ADT-sjangeren er å gripe til den mektigste strukturen du kjenner — heapen — når oppgaveteksten har gitt deg en forutsetning som gjør noe enklere raskere. Les alltid etter begrensningene: få faste prioritetsnivåer gir bøttekø, kjent lite verdiområde gir tellearray, prefikssøk gir trie.

Repetisjon — kapitlet på ett kort

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.