enum class kolor
{
	czarny, czerwony
};
struct wezel {
	wezel() {
		wezel* dziecko = new wezel;
	}
	int dane;
	wezel* wskaznikNaRodzica = nullptr;
	wezel* wskaznikNaPrawegoPotomka = nullptr;
	wezel* wskaznikNaLewegoPotomka = nullptr;
	unsigned int indeks;

	kolor color = kolor::czerwony;
};
struct drzewo {
	wezel* korzen;
	int rozmiar;
	void dodajNowyWezel(int datas) {
		wezel* dziecko = new wezel;;
		if (rozmiar == 0) {
			dziecko->wskaznikNaRodzica = nullptr;
			dziecko->wskaznikNaPrawegoPotomka = nullptr;
			dziecko->wskaznikNaLewegoPotomka = nullptr;
			dziecko->indeks = 0;
			korzen = dziecko;
			korzen->color = kolor::czarny;
		}
		else {
			wezel* 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->dane = datas;
		rozmiar++;
	}
	void sprawdzKolory(wezel* ostatni) {
		while (ostatni->wskaznikNaRodzica->color == ostatni->color) {
			wezel* wujek = nullptr;
			wezel* 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* naRodzica, wezel* 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* naRodzica, wezel* naDziecko) {
		naRodzica->wskaznikNaRodzica = naDziecko;
		naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
		naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
	}
	wezel* znalezienieElementu(int datas) {
		wezel* aktualny;
		aktualny = korzen;
		if (aktualny->dane == datas) {
			return aktualny;
		}
		while (aktualny != nullptr) {
			if (aktualny->wskaznikNaLewegoPotomka->dane == datas) {
				aktualny = aktualny->wskaznikNaLewegoPotomka;
				return aktualny;
			}
			if (aktualny->wskaznikNaPrawegoPotomka->dane == datas) {
				aktualny = aktualny->wskaznikNaPrawegoPotomka;
				return aktualny;
			}
			else {
				aktualny = aktualny->wskaznikNaLewegoPotomka;
			}
		}
	}
};

int main() {
}