#include <iostream>
enum class kolor
{
	czarny, czerwony
};
template  <typename T>
struct wezel {
	T dane;
	wezel<T>* wskaznikNaRodzica = nullptr;
	wezel<T>* wskaznikNaPrawegoPotomka = nullptr;
	wezel<T>* wskaznikNaLewegoPotomka = nullptr;
	unsigned int indeks;

	kolor color = kolor::czerwony;
};
template< typename T>
struct drzewo {
	wezel<T>* korzen;
	int rozmiar = 0;
	void dodajNowyWezel(T datas) {
		wezel<T>* dziecko = new wezel<T>;
		if (rozmiar == 0) {
			dziecko->wskaznikNaRodzica = nullptr;
			dziecko->wskaznikNaPrawegoPotomka = nullptr;
			dziecko->wskaznikNaLewegoPotomka = nullptr;
			dziecko->indeks = 0;
			korzen = dziecko;
			korzen->color = kolor::czarny;
		}
		else {
			wezel<T>* tymczasowy;
			tymczasowy = korzen;
			while (tymczasowy != nullptr) {
				if (tymczasowy->dane > datas) {
					if (tymczasowy->wskaznikNaPrawegoPotomka == nullptr) {
						tymczasowy->wskaznikNaPrawegoPotomka = dziecko;
						dziecko->wskaznikNaRodzica = tymczasowy;
					}
					else
					{
						tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka;
					}
				}
				else {
					if (tymczasowy->dane > datas) {
						if (tymczasowy->wskaznikNaLewegoPotomka == nullptr) {
							tymczasowy->wskaznikNaLewegoPotomka = dziecko;
							dziecko->wskaznikNaRodzica = tymczasowy;
						}
						else
						{
							tymczasowy = tymczasowy->wskaznikNaLewegoPotomka;
						}
					}
				}

			}
		}
		dziecko->indeks = rozmiar;
		dziecko->dane = datas;
		rozmiar++;

	}
	void sprawdzKolory(wezel<T>* ostatni) {
		while (ostatni->wskaznikNaRodzica->color == ostatni->color) {
			wezel<T>* wujek = nullptr;
			wezel<T>* dziadek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica;
			if (ostatni->wskaznikNaRodzica == dziadek->wskaznikNaLewegoPotomka) {
				if (dziadek->wskaznikNaPrawegoPotomka) {
					wujek = dziadek->wskaznikNaPrawegoPotomka;
				}
				if (wujek->color == kolor::czerwony) {
					ostatni->wskaznikNaRodzica->color = kolor::czarny;
					wujek->color = kolor::czarny;
					dziadek->color = kolor::czerwony;
					if (dziadek->dane != korzen->dane) {
						ostatni = dziadek;
					}
					/*else {
						break;
					}*/
				}
				if (ostatni == dziadek->wskaznikNaLewegoPotomka->wskaznikNaPrawegoPotomka) {
					RotacjaLewa(ostatni->wskaznikNaRodzica, ostatni);
				}
				else {
					ostatni->wskaznikNaRodzica->color = kolor::czarny;
					dziadek->color = kolor::czerwony;
					RotacjaPrawa(dziadek->wskaznikNaRodzica, dziadek);
					if (dziadek->dane != korzen->dane) {
						ostatni = dziadek;
					}
					/*else {
						break;
					}*/
				}
			}
			else {
				if (dziadek->wskaznikNaLewegoPotomka) {
					wujek = dziadek->wskaznikNaLewegoPotomka;
				}
				if (wujek->color == kolor::czerwony) {
					ostatni->wskaznikNaRodzica->color = kolor::czarny;
					wujek->color = kolor::czarny;
					dziadek->color = kolor::czerwony;
					if (dziadek->dane != korzen->dane) {
						ostatni = dziadek;
					}
					/*else {
						break;
					}*/
				}
				if (ostatni == dziadek->wskaznikNaPrawegoPotomka->wskaznikNaLewegoPotomka) {
					RotacjaPrawa(ostatni->wskaznikNaRodzica, ostatni);
				}
				else {
					ostatni->wskaznikNaRodzica->color = kolor::czarny;
					dziadek->color = kolor::czerwony;
					RotacjaLewa(dziadek->wskaznikNaRodzica, dziadek);
					if (dziadek->dane != korzen->dane) {
						ostatni = dziadek;
					}
					/*else {
						break;
					}*/
				}
			}
		}
		korzen->color = kolor::czarny;
	}
	void RotacjaPrawa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
		//Rodzicem elementu naRodzica staje się element naDziecko,
		naRodzica->wskaznikNaRodzica = naDziecko;

		//lewy syn elementu naDziecko staje się prawym synem elementu naRodzica.
		naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;

		//lewym dzieckiem elementu naDziecko staje się element naRodzica.
		naDziecko->wskaznikNaLewegoPotomka = naRodzica;
	}
	void RotacjaLewa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
		naRodzica->wskaznikNaRodzica = naDziecko;
		naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
		naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
	}
	wezel<T>* znajdzDane(T datas) {
		wezel<T>* cos = korzen;
		while (cos) {
			if (cos->dane == datas) {
				return cos;
			}
			if (datas > cos->dane) {
				cos = cos->wskaznikNaPrawegoPotomka;
			}
			else {
				cos = cos->wskaznikNaLewegoPotomka;
			}
			return nullptr;
		}
	}
	void wyczyscDrzewo() {
		wezel<T>* kasownik = korzen;
		wyczyscDrzewoRek(kasownik);
	}
	void wyczyscDrzewoRek(wezel<T>* kasownik) {
		if (kasownik == nullptr) {
			return;
		}
		else {
			wyczyscDrzewoRek(kasownik->wskaznikNaLewegoPotomka);
			wyczyscDrzewoRek(kasownik->wskaznikNaPrawegoPotomka);
			delete kasownik;
		}
	}
	//przechodzenie przez wezły
	void InOrder(wezel<T>* drzewo) {
		InOrder(drzewo->wskaznikNaLewegoPotomka);
		std::cout << drzewo->dane << ' ';
		InOrder(drzewo->wskaznikNaPrawegoPotomka);
	}
	//PreOrder służy do kopiowania drzewa
	void PreOrder(wezel<T>* drzewo) {
		std::cout << drzewo->dane << ' ';
		PreOrder(drzewo->wskaznikNaLewegoPotomka);
		PreOrder(drzewo->wskaznikNaPrawegoPotomka);
	}
	void wysokoscDrzewa() {
		int wysokosc = 0;
		wysokoscLiczenie(korzen);
		wysokosc++;
	}
	void wysokoscLiczenie(wezel<T>* drzewo) {
		InOrder(drzewo->wskaznikNaLewegoPotomka);
		std::cout << drzewo->dane << ' ';
		InOrder(drzewo->wskaznikNaPrawegoPotomka);
	}
	void wyswietlDrzewo() {
		wyswietlRek(korzen);
	}
	void wyswietlRek(wezel<T>* korzen) {
		if (korzen != nullptr) {
			std::cout << " dane " << korzen->dane << " indeks " << korzen->indeks;
			if (korzen->wskaznikNaLewegoPotomka != nullptr) {
				wyswietlRek(korzen->wskaznikNaLewegoPotomka);
			}
			if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
				wyswietlRek(korzen->wskaznikNaPrawegoPotomka);
			}
			if (korzen->color == kolor::czerwony)
			{
				std::cout << "czerwony" << std::endl;
			}
			else {
				std::cout << "czarny" << std::endl;
			}
		}
	}
};
int main() {
	drzewo <int> CzerwonoCzarne;
	CzerwonoCzarne.dodajNowyWezel(1);
	CzerwonoCzarne.dodajNowyWezel(2);
	CzerwonoCzarne.dodajNowyWezel(3);
	CzerwonoCzarne.dodajNowyWezel(4);
	CzerwonoCzarne.wyswietlDrzewo();
}