AVL-træ

Fra Wikipedia, den frie encyklopædi

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.

Indholdsfortegnelse 1 Sammenligning med det binære søgetræ 1.1 Indsættelse 1.2 Sletning 2 Kilder

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

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.

[redigér] Indsættelse

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.

[redigér] Sletning

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)

[redigér] Kilder

• File organization and Processing af Allan L. Tharp ISBN 0-471-61766-0