Tasapainoiset binääriset hakupuut ovat datarakenteita, jotka ylläpitävät lajiteltua tietoa ja varmistavat tehokkaat toiminnot, kuten haku, lisää ja poista. Kaksi yleistä tyyppiä ovat AVL puut ja punamusta puut, joista jokaisella on ainutlaatuinen tasapainotusperiaatteet, jotka optimoivat suorituskyvyn.

AVL-puut

AVL puut ovat itse tasapainottava binary haku puita, joissa ero korkeus välillä vasemman ja oikean alapuita tahansa solmu on enintään yksi. Tämä tiukka tasapaino takaa nopeammat hakuajat, mutta vaatii enemmän pyörii aikana sisäänpanot ja poistot säilyttää tasapaino.

Kun solmu muuttuu epätasapainoiseksi toiminnan jälkeen, suoritetaan kiertoja AVL-kiinteistön palauttamiseksi. Kierrot sisältävät yhden ja kaksi kierrosta, jotka auttavat pitämään korkeuseron rajoitteen.

Punamustat puut

Puna-musta puut ovat eräänlainen itse tasapainottava binary hakupuu, joka määrittää värin (punainen tai musta) kullekin solmu. Väritys säännöt takaavat puun pysyy suunnilleen tasapainoinen, ilman polkua juuresta lehti on yli kaksi kertaa niin kauan kuin mikään muu.

Tärkeimmät ominaisuudet ovat:

  • Jokainen solmu on joko punainen tai musta.
  • Juuri on aina musta.
  • Punaiset solmut eivät voi saada punaisia lapsia.
  • Jokainen polku solmusta sen jälkeläisiin sisältää saman määrän mustia solmuja.

Nämä ominaisuudet mahdollistavat punamustat puut suorittaa istutuksia ja poistoja tehokkaasti säilyttäen tasapainon läpi uudelleen väritys ja kiertoja.

AVL:n ja punamustan puun vertailu

Sekä AVL että punamustat puut pyrkivät pitämään puun tasapainossa optimaalisen suorituskyvyn kannalta. AVL-puut ovat yleensä tasapainoisempia, mikä nopeuttaa hakua, mutta saattavat vaatia lisää kiertoja päivitysten aikana. Punamustat puut ovat vähemmän tiukkoja, mikä tarjoaa nopeampia sisäänpanoja ja poistoja hieman hitaammin.