AVL-træ

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

AVL-træet har fået navn efter Adelson-Velskij og Landis, der først beskrev det. Det er et binært søgetræ med en anden måde at håndtere indsættelse af data. I forbindelse med hver indsættelse undersøges det, om træet lokalt er ude af balance, og hvis det er tilfældet, ændres træets struktur. Resultatet er, at træet ikke er følsomt over for den rækkefølge data tilføjes i.

Sammenligning med det binære søgetræ[redigér | redigér wikikode]

I hver knude i AVL-træet er der et felt, som indeholder en balancefaktor, der beskriver højdeforskellen mellem knudens to undertræer. Hvis balancefaktoren bliver ±2, er træet ude af balance, og der skal rettes op på det.

Indsættelse[redigér | redigér wikikode]

Når en ny knude indsættes i AVL-træet, sættes balancefaktoren i knuden til nul, da der ikke er flere knuder under. Så opdateres balancefaktoren i knuden over den nyindsatte knude. Der lægges til eller trækkes fra alt efter om der indsættes til højre eller til venstre i træet. Hvis balancefaktoren bliver 2 eller -2, roteres knuderne i træet.

     A (2)
      \
       B  (1)    ⇒    B (0)
        \           /   \
         C (0)     A (0) C (0)

Rotation mod venstre. Tallene i paraneteser er balancefaktorerne.

Rotationen gentages opad i træet indtil roden er nået.

Sletning[redigér | redigér wikikode]

Ved sletning af data kan den knude, der skal slettes flyttes ned i træet ved hjælp af rotationer indtil knuden er yderst i træet. Herefter er den enkel at fjerne.

Tidskompleksitet
Operation Relativ tid
Find O(log2 N)
Indsæt O(log2 N)
Slet O(log2 N)

Kilder[redigér | redigér wikikode]

Commons-logo.svg
Wikimedia Commons har medier relateret til: