// Strom.cpp 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

struct prvek {
		int key;
		int v;
		string value;
		prvek * left;
		prvek * right;
	};


prvek * search (prvek * b, int k)
{
	while (b!=nullptr && b->key != k){
	   if (k < b->key)
		  b=b->left;
	   else 
		  b=b->right;
	}
	return b;
}

inline int vyska (prvek * p)
{
	return p == NULL ? 0 : p->v;
}

void spocitej (prvek * p)
{
	p->v = vyska (p->left);
	int r = vyska (p->right);
	if (r > p->v)
		p->v = r;
}

void oprav1 (prvek * & target)
{
	prvek * c = target;
	prvek * b = c->left;
	if (vyska (b->left) > vyska (c->right))
	{
		c->left = b->right;
		b->right = c;
		target = b;
		spocitej (b);
	}
	else
	{
   	    prvek * a = b->right;
		b->right = a->left;
		c->left = a->right;
		a->left = b;
		a->right = c;
		spocitej (b);
		spocitej (c);
		spocitej (a);
	}
}

void insert (prvek * & b, int k, string v)
{
	if (b == nullptr){
	    prvek * p = new prvek;
		p->key = k;
		p->value = v;
		p->v = 1;
		p->left = NULL;
		p->right = NULL;
		b = p;
	}
	else if (b->key == k)
		b->value=v;
	else if (k < b->key)
		insert (b->left, k, v);
	    if (vyska (b->left) > vyska (b->right) + 1)
	       oprav1 (b); 
	else 
		insert (b->right, k, v);
}

void insert0 (prvek * & branch, int k, string v)
{
	prvek * b = branch;
	prvek * last = NULL;
	while (b!=nullptr && b->key != k){
	   last = b;
	   if (k < b->key) b=b->left; else b=b->right;
	}
	if (b != NULL)
   	  b->value = v;
	else 
	{
		prvek * p = new prvek;
		p->key = k;
		p->value = v;
		p->left = NULL;
		p->right = NULL;
		if (last == NULL)
			branch = p;
		else if (k < last->key)
			last->left = p;
		else 
			last->right = p;
	}
}

prvek * find (prvek * b, int k)
{
	if (b == nullptr)
		return nullptr;
	else if (b->key == k)
	    return b;
	else if (k < b->key)
		return find (b->left, k);
	else 
		return find (b->right, k);
}

prvek * odpoj (prvek * & p)
{
	if (p->right!=nullptr) 
	  return odpoj (p->right);
	else {
		prvek* a=p;
		p=p->left;
		a->left=nullptr;
		return a;
	}
}

void smaz (prvek * & b,int k)
{
	if (b == nullptr)
	{ }
	else if (k < b->key)
		 smaz (b->left, k);
	else if (k > b->key)
		 smaz (b->right, k);
	else
	{
		prvek *a = b;
		if (b->left == nullptr)
			b = b->right;
		else if (b->right == nullptr)
			b = b->left;
		else
		{
			prvek * r = odpoj(b->left);
			b = r;
			r->left = a->left;
			r->right = a->right;
		}
		delete a;	
	}
}

void remove (prvek * * b, int k)
{
	if (*b == nullptr)
	{ }
	else if (k < (*b)->key)
		b = & ((*b)->left);
	else if (k > (*b)->key)
		b = & ((*b)->right);
	else
	{
		prvek * a = * b;
		if (a->left == nullptr)
			*b = a->right;
		else if (a->right == nullptr)
		    *b = a->left;
		else
		{
			prvek * * u = & (a->left);
			while ((*u)->right != nullptr)
				u = & ((*u)->right);
			
			prvek * r = *u;
			*u = r->left;
			r->left = nullptr;

			*b = r;
			r->left = a->left;
			r->right = a->right;
		}
		delete a;	
	}
}

void write(prvek *b, int level = 1)
{
	if(b!=nullptr)
	{
		for (int i = 1; i < 4*level; i++)
			 cout << " ";
		cout << b->key << " " << b->value << endl;
		write(b->left, level+1);
		write(b->right, level+1);
	}
}

void write2 (prvek *b)
{
	if (b!=nullptr)
	{
		write2 (b->left);
		cout << "(" << b->key << "," << b->value << ") ";
		write2 (b->right);
	}
}

bool any; // true => na dolnim patre jsou nejake hodnoty
int pos; // pozice na prave tistenem radku

void write_key (prvek *b, int target)
{
	stringstream f;
	if (b != NULL)
	{
	   f << b->key; // priprav cislo
	   any = true; // potkal jsem nejakou hodnotu
	}
	string s = f.str (); // preved cislo na retezec
	int characters = target - pos; 
	while (s.length() < characters) // dopln zleva mezerami
		s = " " + s;
	cout << s; // vytiskni
	pos = pos + characters; // poznamenej si pocet vytistenych znaku
}


void write_level (prvek *b, int target, int step, int level)
// b ... tisteny prvek (muze but mullptr)
// target ... cilovy sloupec
// step ... vzdalenost mezi sloupci/podstromy
// level ... o kolik pater jeste mam sestoupit
{
	if (b != nullptr)
	{
		if (level == 1) // jsme na spravnem patre, tiskneme
		{
			write_key (b, target);
		}
		else // jeste se musime ponorit 
		{
  	       write_level (b->left,  target-step, step/2, level-1);
		   write_level (b->right, target+step, step/2, level-1);
		   // tiskneme levou a pravou vetev
		   // target+-step ... posuneme si cilovy sloupec
		   // step/2  ... polovicni vzdalenost mezi podstromy
		   // level-1 ... zbyva nam o jedno patro mene
     	}
	}
}

void write3 (prvek *b)
{
	int level = 1; // nejprve vytiskneme horni patro
	any = true; // true ... while cyklus poprve probehne
	while (any)
	{
		any = false; // az najdeme na nejnizsim patre hodnotu, zmeni se na true
		pos = 0; // pocet vytistenych znaku
		write_level (b, 40, 20, level);
		// zacneme na sloupci 40
		// na dalsim patre to budou sloupce 40-20 a 40+20
		cout << endl; // konec radky
		cout << endl; // a jeste prazdnou radku
		level = level + 1; // priste vytiskneme dalsi patro
	}
}

prvek * root;

int _tmain(int argc, _TCHAR* argv[])
{
	root = nullptr;

	insert (root, 7, "sedm");
	insert (root, 10, "");
	insert (root, 5, "");
	/*
	insert (root, 8, "osm");
	insert (root, 12, "");

	insert (root, 1, "");
	insert (root, 6, "");

	insert (root, 2, "");
	insert (root, 9, "");
	insert (root, 11, "");
	insert (root, 14, "");
	*/

	// smaz (root, 7);
	remove (&root, 5);

	//prvek * p = search (root, 
	write (root);
	cout << "-----------------------------" << endl;
	cout << "Setridene" << endl;
	write2 (root);
	cout << endl;
	cout << "------------------------------" << endl;
	write3 (root);
	cout << "Hotovo" << endl;
	system ("pause");

	return 0;

	return 0;
}