Balanserte binære søketre er datastrukturer som opprettholder sorterte data og sikrer effektive operasjoner som søk, sett inn og slett. To vanlige typer er AVL-trær og Rød-Svarte trær, hver med unike balanseringsprinsipper som optimaliserer ytelsen.

AVL Treer

AVL-trær er selvbalanserende binære søketre der forskjellen i høyde mellom venstre og høyre undertreer av en node er på det meste en. Denne strenge balansen sikrer raskere søketider, men krever flere rotasjoner under innsettinger og slettinger for å opprettholde balanse.

Når en node blir ubalansert etter en operasjon, utføres rotasjoner for å gjenopprette AVL-egenskapen. Disse rotasjonene inkluderer enkelt- og dobbeltrotasjoner, som bidrar til å opprettholde høydeforskjellsbegrensningen.

Rød-svarte trær

Rød-svart trær er en type selvbalanserende binære søketre som tildeler en farge (rød eller svart) til hver node. Fargeleggerreglene sikrer at treet forblir omtrent balansert, uten at veien fra rota til et blad er mer enn dobbelt så lang som noen annen.

Nøkkelegenskaper inkluderer:

  • Hver node er enten rød eller svart.
  • Roten er alltid svart.
  • Røde noder kan ikke ha røde barn.
  • Hver bane fra en node til dens etterkommerblader inneholder samme antall svarte noder.

Disse egenskapene tillater Rød-Black-trær å utføre innsettinger og slettinger effektivt samtidig som balansen opprettholdes gjennom omfargelse og rotasjoner.

Sammenligning av AVL og rød-svarte trær

Både AVL og Red-Black-trær har som mål å holde treet balansert for optimal ytelse. AVL-trær har en tendens til å være strengere balansert, noe som gir raskere oppslag, men kan kreve mer rotasjoner under oppdateringer. Røde-Black-trær er mindre strenge, og tilbyr raskere innsettinger og slettinger med litt langsommere oppslag.