Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Hauger og binære søketrær, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Et nesten komplett binærtre lagret i et array, der haug-egenskapen holder for hver node.
En haug der hver forelder er minst like stor som barna, så det største elementet ligger i rota.
Operasjonen som gjenoppretter haug-egenskapen ved å la et for lite element synke nedover. .
Bygger en haug fra et uordnet array nedenfra-og-opp i lineær tid — ikke det samme som gjentatte innsettinger.
En abstrakt datatype som alltid gir det elementet med høyest (eller lavest) prioritet. Effektivt implementert med en haug.
Sorterer på stedet ved å bygge en maks-haug og gjentatte ganger flytte rota til enden. .
Et tre der hver node har nøkler i venstre delre mindre, og i høyre delre større, enn noden selv.
Besøker et BST i venstre–node–høyre-rekkefølge og gir nøklene i stigende orden.
Den minste nøkkelen som er større enn en gitt node — neste node i inorden-rekkefølgen.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Haug-indeksering (1-basert)
En haug lagres i et array uten pekere: barn og forelder finnes ved enkel aritmetikk på indeksen.
Maks-haug-egenskapen
Hver node er minst like stor som barna sine, så det største elementet ligger alltid i rota. Min-haug snur ulikheten.
Høyde av en haug
Et nesten komplett binærtre med noder har logaritmisk høyde, derfor koster heapify .
Build-Max-Heap
Å bygge en haug nedenfra-og-opp er lineært — ikke — fordi de fleste nodene ligger nær bunnen og har kort heapify-vei. Skiller seg fra gjentatte innsettinger.
Heapsort
Bygg en maks-haug, og flytt så gjentatte ganger rota til enden og gjenopprett haugen. Sorterer på stedet med logaritmisk arbeid per element.
Inorden-traversering av BST
Besøker nodene i et binært søketre i stigende nøkkelrekkefølge. Gir en sortert utskrift i .
BST-operasjoner
Søk, innsetting, minimum, etterfølger og sletting følger alle én sti og koster proporsjonalt med treets høyde . Balansert: ; degenerert: .
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Forklare maks-haug-egenskapen og hvordan et nesten komplett binærtre lagres i et array via indeks-aritmetikk
- 02Spore Max-Heapify, Build-Max-Heap og Heapsort på et lite eksempel og begrunne kjøretidene O(lg n), O(n) og Θ(n lg n)
- 03Forklare hvordan en haug gir en prioritetskø med O(lg n) innsetting og uthenting
- 04Beskrive søk, innsetting og sletting i et binært søketre, og forklare hvorfor kjøretiden O(h) avhenger av treets form