Itse tasapainottavat puut ovat tietoteknisessä aineistorakenteissa käytettäviä datarakenteita lajitellun tiedon tehokkaaseen ylläpitoon. Tasapainotekijä on keskeinen metri, joka auttaa määrittämään, pysyykö puu tasapainossa istutusten tai poistojen jälkeen. Tämän tekijän laskeminen on välttämätöntä optimoitujen algoritmien suunnittelussa.

Mikä on tasapainokerroin?

Tasapainokerroin solmussa on sen vasemman ja oikean alaosan korkeuden ero. Se osoittaa, onko solmu tasapainossa, vasemmalla tai oikealla painava. Tasapainokerroin 0, 1 tai -1 tyypillisesti merkitsee tasapainoista solmua.

Tasapainotekijän laskeminen

Laske tasapainotekijä, mittaa korkeus vasemman alaluvun ja vähentää korkeus oikean alaluvun. Korkeus subtree on määrä reunojen pisin polku solmusta lehtiin. Kaava on:

Tasapainokerroin = Korkeus(vasen alapuu) - Korkeus(oikea alapuu)[

Soveltaminen puutoiminnoissa

Kun puu on lisätty tai poistettu, tasapainotekijän uudelleenlaskeminen auttaa määrittämään, tarvitaanko vuorotteluja puun tasapainon ylläpitämiseksi. Jos tasapainokerroin ylittää 1 tai laskee alle -1, puu tekee kiertoja tasapainon palauttamiseksi, tehokkaan haun varmistamiseksi, lisää ja poistaa toimintoja.

Yleiset itsetasapainottavat puut

  • AVL-puu
  • Punamusta puu
  • Leikkipuu
  • Treap