Copacii de căutare binari echilibrați sunt structuri de date care mențin date sortate și asigură operațiuni eficiente, cum ar fi căutarea, inserarea și ștergerea. Două tipuri comune sunt arbori AVL și copaci roșii-negru, fiecare cu principii unice de echilibrare care optimizează performanța.

Copaci AVL

Copacii AVL sunt arbori de căutare binari care se autoechilibrează, în cazul în care diferența de înălțime dintre subarborele stâng și cel drept al oricărui nod este cel mult una. Acest echilibru strict asigură timpi de căutare mai rapizi, dar necesită mai multe rotiri în timpul inserțiilor și ștergerilor pentru a menține echilibrul.

Atunci când un nod devine dezechilibrat după o operațiune, se efectuează rotație pentru a restabili proprietatea AVL. Aceste rotație include rotație unică și dublă, care ajută la menținerea constrângerii de diferență de înălțime.

Copaci roșii-negri

Copacii rosii-negri sunt un tip de copac de cautare binar autoechilibrare care atribuie o culoare (roșu sau negru) la fiecare nod. Regulile de colorat asigura copacul rămâne aproximativ echilibrat, fără nici o cale de la rădăcină la o frunză fiind mai mult de două ori mai mult decât orice alt.

Proprietățile principale includ:

  • Fiecare nod este fie roşu, fie negru.
  • Rădăcina e întotdeauna neagră.
  • Nodurile roşii nu pot avea copii roşii.
  • Fiecare cale de la un nod la frunzele descendente conține același număr de noduri negre.

Aceste proprietăţi permit copacilor roşii-negri să efectueze inserţii şi ştergeri eficient în timp ce menţine echilibrul prin recolorare şi rotaţii.

Comparație între AVL și copacii roșii-negri

Atât copacii AVL cât și cei roșii-negri au ca scop păstrarea copacului echilibrat pentru o performanță optimă. Copacii AVL tind să fie mai strict echilibrați, oferind căutări mai rapide, dar pot necesita mai multe rotiri în timpul actualizărilor. Copacii roșii-negru sunt mai puțin stricți, oferind inserții și ștergeri mai rapide cu căutări ușor mai lente.