Alla oleva AVL-puu on epätasapainossa viimeisen lisäyksen jälkeen (mallivastauksessa on tilat ennen lisäystä ja lisäyksen jälkeen). Tasapainota puu tekemällä rotaatio. Katso lisätietoa Ohje-sivulta.

Rotaatiot voi tehdä muokkaamalla kaaria, eli vetämällä kaari osoittamaan uuteen solmuun. Puu päivitetään vasta, kun Update References -painiketta painetaan. Päivitä puu vasta kun olet muuttanut kaikki rotaatiossa muuttuvat kaaret.

Visuaalisessa esityksessä ympyrä ja sen sisällä oleva kirjain vastaavat yksittäistä puun solmua eli tietuetta ja sen avainta. Kunkin solmun vieressä oleva numero kertoo kyseisen alipuun korkeuden. Mikäli puuhun muodostuu sykli (virheellisten) osoitinpäivitysten seurauksena, piirretään tällainen rakenne kolmiona.

Tehtävässä on käytetty C-kielestä tuttua notaatiota solmua vastaavan tietueen (node) kenttiin viittaamiseksi ("->"-operaattori). Voit olettaa, että binääripuun solmu on toteutettu seuraavanlaisena tietueena:

struct node {
    char key;
    struct node *left;
    struct node *right;
};

struct node *p, *f;

// Solmu p on epätasapainossa ja sen isäsolmu on f
if (f->left == p) {
  if (height(p.left) > height(p.right)) {
    f->left = p->left;  // single rotation right
    p->left = f->left->right;
    f->left->right = p;
  } else { // height(p.left) < height(p.right)
    f->left = p->right; // single rotation left
    p->right = f->left->left;
    f->left->left = p;
  }
} else { // f->right == p
  if (height(p.left) < height(p.right)) {
    f->right = p->right; // single rotation left
    p->right = f->right->left;
    f->right->left = p;
  } else { // height(p.left) > height(p.right)
    f->right = p->left;  // single rotation right
    p->left = f->right->right;
    f->right->right = p;  
  }
}