// Řešení 26-2-5 pomocí rotací

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Jeden vrchol stromu
struct node {
  struct node *l, *r;		// Levý a pravý syn
  int x;			// Hodnota uložená ve vrcholu
};

/*
 *  Při operacích se stromy dodržujeme následující konvenci:
 *  Funkce vždy dostane pointer na proměnnou, která ukazuje na kořen
 *  právě zpracovávaného podstromu. Díky tomu může kořen podstromu
 *  snadno nahradit jiným vrcholem.
 */

// Rotuje hranu xy doprava
void rotate_right(struct node **px)
{
  struct node *x = *px;
  struct node *y = x->l;
  x->l = y->r;
  y->r = x;
  *px = y;
}

// Rotuje hranu yx doleva
void rotate_left(struct node **py)
{
  struct node *y = *py;
  struct node *x = y->r;
  y->r = x->l;
  x->l = y;
  *py = x;
}

// Převede strom na seznam pomocí postupných rotací
void linearize(struct node **rootp)
{
  struct node **pp = rootp;
  struct node *v;

  while (v = *pp)
    {
      if (v->l)
	{
	  // Mám-li levého syna, rotuji doprava
	  rotate_right(pp);
	}
      else
	{
	  // Nemám-li levého syna, sestoupím doprava
	  pp = &v->r;
	}
    }
}

// Změří délku seznamu
int list_length(struct node *root)
{
  int n = 0;
  while (root)
    {
      n++;
      root = root->r;
    }
  return n;
}

// Jeden krok vyvažování: "zubatění" cesty
void fold(struct node **rootp, int m)
{
  struct node **pp = rootp;

  while (m--)
    {
      rotate_left(pp);
      pp = &(*pp)->r;
    }
}

// Ze seznamu délky m=2^i-1 vytvoří úplný strom
void balance(struct node **rootp, int m)
{
  while (m > 1)
    {
      m /= 2;
      fold(rootp, m);
    }
}

// Rozmístí přebytečné vrcholy tak, aby visely pod listy úplného stromu
void disperse(struct node **rootp, int m, int r)
{
  struct node **pp = rootp;
  int z = 0;

  for (int i=0; i<m; i++)
    {
      z += r;
      if (z >= m)
	{
	  z -= m;
	  rotate_left(pp);
	}
      pp = &(*pp)->r;
    }
}

/*** Testování ***/

// Vložení prvku do stromu (bez vyvažování)
void insert(struct node **rootp, int x)
{
  struct node *root = *rootp;
  if (!root)
    {
      root = malloc(sizeof(struct node));
      root->l = root->r = NULL;
      root->x = x;
      *rootp = root;
    }
  else if (x < root->x)
    insert(&root->l, x);
  else
    insert(&root->r, x);
}

// Vygeneruje náhodný strom o n prvcích
struct node *random_tree(int n)
{
  struct node *root = NULL;

  for (int i=0; i<n; i++)
    insert(&root, rand() % 1000);
  return root;
}

// Vykreslí strom
void dump2(struct node *v, int indent)
{
  if (!v)
    return;
  dump2(v->r, indent+1);
  printf("%*s%d\n", indent*4, "", v->x);
  dump2(v->l, indent+1);
}

void dump(struct node *v, char *name)
{
  printf("%s:\n", name);
  dump2(v, 0);
  putchar('\n');
}

// Zkontroluje, že strom je dokonale vyvážený
int verify(struct node *root)
{
  if (!root)
    return 0;

  int nl = verify(root->l);
  int nr = verify(root->r);
  if (abs(nl-nr) > 1)
    {
      printf("Nekorektní vyvážení!\n");
      exit(1);
    }
  return nl + nr + 1;
}

// Hlavní testovací program
int main(void)
{
  // Vygenerujeme náhodný strom
  struct node *root = random_tree(10);
  dump(root, "Původní strom");

  // Vyrobíme z něj seznam
  linearize(&root);
  dump(root, "Převeden na seznam");

  // Spočítáme velikost úplného stromu m a počet přívěsků r
  int n = list_length(root);
  int m = 1;
  while (2*m + 1 <= n)
    m = 2*m + 1;
  int r = n - m;
  printf("Strom obsahuje %d prvků\n", n);
  printf("Nejbližší menší úplný jich má %d, budeme doplňovat %d přívěsků\n\n", m, r);

  // Rozmístíme přívěsky
  disperse(&root, m, r);
  dump(root, "Připraveny přívěsky");

  // Zbytek vyvážíme jako úplný
  balance(&root, m);
  dump(root, "Vyvážen");

  // Na závěr zkontrolujeme, že se dílo podařilo
  verify(root);
  return 0;
}