// Řešení 26-2-5 simulací rekurzivní konstrukce stromu

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

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

// Založí nový vrchol
struct node *new_node(void)
{
  struct node *v = malloc(sizeof(*v));
  memset(v, 0, sizeof(*v));
  return v;
}

// Vypíše strom (a zkontroluje, že je konsistentní)
void dump2(struct node *v, struct node *p, int indent)
{
  if (!v)
    return;
  if (v->p != p)
    printf("<bad parent at %p>\n", v);
  dump2(v->r, v, indent+1);
  printf("%*s%d\n", indent*4, "", v->x);
  dump2(v->l, v, indent+1);
}

void dump(struct node *v)
{
  dump2(v, NULL, 0);
}

// Samotné vyvažování stromu
struct node *balance(struct node *list, int n)
{
  int d = 1;		// V jaké hloubce zrovna jsme
  // Zásobníky indexované hloubkou (1 bit na položku)
  bool mod[32];		// Zbytek při dělení počtu vrcholů dvěma
  bool flag[32];	// Zpracovali jsme už levý podstrom?
  bool side[32];	// Z které strany jsme napojeni k nejbližšímu vyššímu
			// skutečnému vrcholu (viz níže)

  // Založíme virtuální vrchol nad budoucím kořenem, aby bylo kam napojovat.
  struct node *res = new_node();
  struct node *conn = res;
  res->x = -1;
  flag[0] = 0;
  side[0] = 0;

left:
  // Pokud můžeme jít doleva, činíme tak.
  // Trochu to komplikuje fakt, že procházíme přes vrcholy, které ještě neexistují :)
  // Proto si udržujeme pointer "conn" na nejbližší vyšší vrchol, který je skutečný.
  if (n)
    {
      mod[d] = (n-1) % 2;
      flag[d] = 0;
      side[d] = side[d-1];
      n = (n-1) / 2;
      d++;
      goto left;
    }

  // Krok nahoru
up:
  d--;
  if (!d)
    {
      // Hotovo. Odpojíme virtuální "nadkořen" a vrátíme skutečný kořen.
      struct node *root = res->l;
      root->p = NULL;
      free(res);
      return root;
    }

  // Rekonstruujeme n vrcholu, do nějž jsme vystoupili.
  if (flag[d])
    n -= mod[d];
  n = 2*n + 1 + mod[d];

  // Pokud jsme se vrátili zprava, je celý podstrom hotov, takže se vrátíme o další patro výš.
  if (flag[d])
    {
      conn = conn->p;
      goto up;
    }

  // Vrátili jsme se zleva. Tím pádem se aktuální vrchol (zatím virtuální) stává skutečným,
  // konkrétně na jeho místo přepojíme následující prvek seznamu.
  struct node *v = list;
  list = list->r;
  v->l = (side[d-1] ? conn->r : conn->l);
  if (v->l)
    v->l->p = v;
  v->r = NULL;
  v->p = conn;
  if (side[d-1])
    conn->r = v;
  else
    conn->l = v;

  // Nový vrchol se stane "připojovacím místem" pro svůj pravý podstrom.
  // Uděláme jeden krok doprava a pak kráčíme doleva, jako na začátku.
  conn = v;
  flag[d] = 1;
  side[d] = 1;
  n = (n-1) / 2 + mod[d];
  d++;
  goto left;
}

/*** Testovací program ***/

int main(void)
{
  int n = 18;

  // Vytvoří seznam (konverze stromu na seznam viz první vzorové řešení)
  struct node *first = NULL, **plast = &first;
  for (int i=1; i<=n; i++)
    {
      struct node *v = new_node();
      v->x = i;
      *plast = v;
      plast = &v->r;
    }

  dump(balance(first, n));
}