Referanseside · Kapittel 14
Begreper & formler
Alle nøkkelbegrepene og formlene fra Utvidede datastrukturer, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Øv med flashcards7 kort fra dette kapittelet
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
01Augmentering
Å legge til ekstra felt i en datastruktur for å støtte nye operasjoner uten å endre kompleksitet.
02Order-statistic tree
Et red-black-tre utvidet med størrelsesfelt for hver node.
03Dynamic interval tree
Struktur for effektiv søking etter overlapp mellom intervaller.
04Balansetid
Når data utvides, må man sikre at oppdatering av felt ikke øker kompleksiteten.
05Eksempler
Red-black-trær med subtre-størrelser, heaps med høyder, og segmenttrær.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.