Referanseside · Kapittel 13

Begreper & formler

Alle nøkkelbegrepene og formlene fra Rød-svarte trær, 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.

01Farget node

Hver node er enten rød eller svart.

02Red-Black-egenskaper

Fem regler som sikrer balanse, blant annet at roten alltid er svart og ingen to røde noder er naboer.

03Svart høyde

Antall svarte noder fra en node til et blad.

04Rotasjon

Operasjon som omstrukturerer treet lokalt for å opprettholde balanse.

05Balansert høyde

Red-Black-trær sikrer $h \leq 2 lo g_{2} (n + 1)$ .

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

h \leq 2 lo g_{2} (n + 1)

O (lo g n)