Balansen faktor er et sentralt konsept i AVL trær, en type selvbalanserende binære søketre. Det bidrar til å opprettholde treets høyde og sikrer effektive operasjoner som søk, innsetting og sletting. Forstå hvordan du beregner og bruke balansefaktoren er viktig for å administrere AVL trær effektivt.

Hva er balansefaktoren?

Balansefaktoren til en node i et AVL-tre er forskjellen mellom høydene på sine venstre og høyre undertre. Det beregnes som:

Balance Factor = Høyde på venstre undertre - Høyde på høyre undertre]

En node balansefaktor kan være -1, 0, eller 1 for at treet skal balanseres. Hvis balansefaktoren overstiger disse verdiene, treet krever rebalansering gjennom rotasjoner.

Beregner balansefaktoren

For å bestemme balansefaktoren, finner du først høyden på hvert undertre rotet på nodebarn. Høyden er antall kanter på den lengste banen fra node til et blad. Trekk høyden på høyre undertre fra høyden på venstre undertre for å få balansefaktoren.

For eksempel, hvis venstre undertre har høyde 3 og høyre undertre har høyde 1, så er balansefaktoren 2, noe som indikerer at noden er ubalansert og trenger rotasjon.

Anvendelser av balansefaktoren

Balansefaktoren brukes under innsetting og sletting for å opprettholde AVL-treets balanse. Når en nodes balansefaktor blir utenfor området -1 til 1, utføres rotasjoner for å gjenopprette balansen. Disse rotasjonene inkluderer:

  • Enkelt høyre rotasjon
  • Enkelt venstre rotasjon
  • Venstre-høyre rotasjon
  • Høyre-venstre rotasjon

Disse operasjonene bidrar til å holde trehøyden minimal, noe som sikrer optimal ytelse for søkeoperasjoner.