Factorul de echilibru este un concept cheie în arborii AVL, un tip de arbore de căutare binar autoechilibrare. Acesta ajută la menținerea înălțimea copacului și asigură operațiuni eficiente, cum ar fi căutarea, inserarea și ștergerea. Înțelegerea modului de calcul și de aplicare a factorului de echilibru este esențială pentru gestionarea eficientă a arborilor AVL.

Ce este factorul de echilibru?

Factorul de echilibru al unui nod într-un copac AVL este diferența dintre înălțimile subarboreului stâng și drept. Se calculează ca:

Factor de balanță = Înălțimea subtree-ului stâng - Înălțimea subtree-ului drept

Factorul de echilibru al nodului poate fi -1, 0 sau 1 pentru ca arborele să fie echilibrat. Dacă factorul de echilibru depășește aceste valori, arborele necesită reechilibrare prin rotație.

Calcularea factorului de echilibru

Pentru a determina factorul de echilibru, mai întâi găsiţi înălţimea fiecărui suburbie înrădăcinat la copiii nodului. Înălţimea este numărul de margini pe cea mai lungă cale de la nod la o frunză. Scădeţi înălţimea subrubrica dreapta de la înălţimea subtree stânga pentru a obţine factorul de echilibru.

De exemplu, dacă subtrenul stâng are înălţimea 3 şi subrubrica dreaptă are înălţimea 1, atunci factorul de echilibru este 2, indicând faptul că nodul este dezechilibrat şi necesită rotaţie.

Aplicațiile factorului de echilibru

Factorul de echilibru este utilizat în timpul inserării și ștergerii pentru a menține echilibrul copacului AVL. Când factorul de echilibru al nodului devine în afara intervalului de -1-1, se efectuează rotație pentru a restabili echilibrul. Aceste rotație includ:

  • Rotire unică la dreapta
  • Rotire simplă la stânga
  • Rotire stânga- dreapta
  • Rotire pe stânga-dreapta

Aceste operaţiuni ajută la menţinerea înălţimii copacilor la minimum, asigurând performanţa optimă pentru operaţiunile de căutare.