#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <ctime>


using namespace std;

struct drzewo
{
	drzewo *left, *right, *up;
	int data_urodzenia;
	string imie;
};


void dodaj_wartosc(drzewo *&root, string x, int y)
{
	drzewo *w, *p;

	w = new drzewo;
	w->right = NULL;
	w->left = NULL;
	w->imie = x;
	w->data_urodzenia = y;
	p = root;

	if (!p)
	{
		root=w;
	}
	else
	{
		while (true)
		{
			if (y < p->data_urodzenia)
			{
				if (!p->left)
				{
					p->left=w;
					break;
				}
				else
				{
					p = p->left;
				}
			}
			else
			{
				if (!p->right)
				{
					p->right=w;
					break;
				}
				else
				{
					p = p->right;
				}
			}
		}
	}
	w->up = p;
}

void usun_drzewo(drzewo *v)
{
	if (v)
	{
		usun_drzewo(v->left);   // usuwamy lewe poddrzewo
		usun_drzewo(v->right);  // usuwamy prawe poddrzewo
		delete v;              // usuwamy sam węzeł
	}
}

void drukuj_drzewo(drzewo *root, int odleglosc)
{
	if (root)
	{
		drukuj_drzewo(root->right, odleglosc + 5);
		cout << setw(odleglosc) << root->data_urodzenia<< " "<< root->imie << endl;
		drukuj_drzewo(root->left, odleglosc + 5);
	}
}

drzewo *najpozniej_urodzony(drzewo *p)
{
	if (p) while (p->right) p = p->right;

	return p ;
}

drzewo *najwczesniej_urodzony(drzewo *p)
{
	if (p) while (p->left) p = p->left;

	return p;
}

void wypisz(drzewo *x)
{
	cout << x->imie << ", rocznik "<< x->data_urodzenia << endl;
}

drzewo *nastepnik(drzewo * p)
{
	drzewo * r;

	if (p)
	{
		if (p->right) return najwczesniej_urodzony(p->right);
		else
		{
			r = p->up;
			while (r && (p == r->right))
			{
				p = r;
				r = r->up;
			}
			return r;
		}
	}
	return p;
}

drzewo *szukaj(drzewo *p, int k)
{
	while(p && p->data_urodzenia != k)
		p = (k < p->data_urodzenia)? p->left : p->right;

	return p;
}

void usun_dany_element(drzewo *&root, drzewo *X)
{
	drzewo *Y, *Z;

	if (X)
	{
		Y = !X->left || !X->right ? X : nastepnik(X);

		Z = Y->left ? Y->left : Y->right;

		if (Z) Z->up = Y->up;

		if (!Y->up) root = Z;
		else if (Y == Y->up->left) Y->up->left = Z;
		else Y->up->right = Z;

		if (Y != X)
		{
			X->data_urodzenia = Y->data_urodzenia;
			X->imie = Y->imie;
		}
		delete Y;
	}
}

int main()
{
	drzewo *head = NULL;
	drzewo *x, *d, *e, *a;

	srand(time(NULL));

	dodaj_wartosc(head, "syn", 1999);
	dodaj_wartosc(head, "mama", 1973);
	dodaj_wartosc(head, "tata", 1974);
	dodaj_wartosc(head, "babcia", 1952);
	dodaj_wartosc(head, "dziadek", 1942);
	dodaj_wartosc(head, "corka", 1996);
	dodaj_wartosc(head, "wnuk", 2009);
	dodaj_wartosc(head, "wnuczka", 2008);
	dodaj_wartosc(head, "pies", 2017);

	drukuj_drzewo(head, 0);
	cout << endl;
	x = najpozniej_urodzony(head);
	d = najwczesniej_urodzony(head);
	cout << "Najstarszy czlonek rodziny to: "; wypisz(d);
	cout << "Najmlodszy czlonek rodziny to: "; wypisz(x);
	cout << endl;
	int q;
	cin >> q;
	a = szukaj(head, q);
	wypisz(a);
	cout << endl;

	usun_dany_element(head, a);
	drukuj_drzewo(head, 0);

	usun_drzewo(head);
	cin.get();
	return 0;
}