Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <time.h>
- #include <exception>
- #include <random>
- 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 = 0;
- kolor color = kolor::czerwony;
- };
- template< typename T>
- struct drzewo {
- wezel<T>* korzen = nullptr;
- int rozmiar = 0;
- void dodajNowyWezel(T datas) {
- wezel<T>* dziecko = new wezel<T>;
- dziecko->dane = datas;
- dziecko->indeks = rozmiar;
- if (rozmiar == 0) {
- dziecko->wskaznikNaRodzica = nullptr;
- dziecko->wskaznikNaPrawegoPotomka = nullptr;
- dziecko->wskaznikNaLewegoPotomka = nullptr;
- korzen = dziecko;
- korzen->color = kolor::czarny;
- }
- else {
- wezel<T>* tymczasowy = korzen;
- //szukamy gdzie jest miejsce dla dziecka
- //sprawdzamy czy datas jest wieksze czy mniejsze od danych w tymczasowym
- while (tymczasowy != nullptr) {
- //prawa odnoga
- if (tymczasowy->dane <= datas)
- {
- //przechodzimy do kolejnego wezła
- if (tymczasowy->wskaznikNaPrawegoPotomka == nullptr) {
- tymczasowy->wskaznikNaPrawegoPotomka = dziecko;
- dziecko->wskaznikNaRodzica = tymczasowy;
- tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka->wskaznikNaPrawegoPotomka;
- }
- else {
- tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka;
- }
- }
- //lewa odnoga
- else if (tymczasowy->dane > datas) {
- //przechodzimy do kolejnego wezła
- if (tymczasowy->wskaznikNaLewegoPotomka == nullptr) {
- tymczasowy->wskaznikNaLewegoPotomka = dziecko;
- dziecko->wskaznikNaRodzica = tymczasowy;
- tymczasowy = tymczasowy->wskaznikNaLewegoPotomka->wskaznikNaLewegoPotomka;
- }
- else {
- tymczasowy = tymczasowy->wskaznikNaLewegoPotomka;
- }
- }
- else
- std::cout << "COS NIE TAK!!!";
- }
- sprawdzKolory(dziecko);
- }
- rozmiar++;
- }
- void sprawdzKolory(wezel<T>* ostatni) {
- while (ostatni != korzen && ostatni->wskaznikNaRodzica->color == kolor::czerwony) {
- wezel<T>* wujek = new wezel<T>;
- //ustalenie czy wujek jest z prawej czy lewej strony(pochodzenie wujka)
- if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
- wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka;
- }
- else if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka)
- {
- wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka;
- }
- else {
- std::cout << "Cos nie tak z wujkiem!!!" << std::endl;
- }
- if (wujek->color == kolor::czerwony) {
- ostatni->wskaznikNaRodzica->color = kolor::czarny;
- wujek->color = kolor::czarny;
- ostatni = ostatni->wskaznikNaRodzica->wskaznikNaRodzica;
- }
- if (wujek->color == kolor::czarny) {
- //Left Left Case
- if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
- RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
- ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
- ostatni->wskaznikNaRodzica->color = kolor::czarny;
- }
- //Left Right Case
- if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
- RotacjaLewa(ostatni->wskaznikNaRodzica, ostatni);
- //wywołanie Left Left Case
- RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
- ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
- ostatni->wskaznikNaRodzica->color = kolor::czarny;
- }
- //Right Right Case
- if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
- RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
- ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
- ostatni->wskaznikNaRodzica->color = kolor::czarny;
- }
- // Right Left Case
- if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
- RotacjaPrawa(ostatni->wskaznikNaRodzica, ostatni);
- //Right Right Case
- RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
- ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
- ostatni->wskaznikNaRodzica->color = kolor::czarny;
- }
- }
- }
- }
- void RotacjaPrawa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
- naRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka = naRodzica->wskaznikNaLewegoPotomka;
- naRodzica->wskaznikNaRodzica = naDziecko;
- naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
- naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
- }
- void RotacjaLewa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
- naRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka = naRodzica->wskaznikNaPrawegoPotomka;
- naRodzica->wskaznikNaRodzica = naDziecko;
- naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;
- naDziecko->wskaznikNaLewegoPotomka = 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;
- }
- }
- void wysokosc() {
- int wysokosc = wysokoscRek(korzen);
- std::cout << "wysokosc drzewa: " << wysokosc << std::endl;
- }
- int wysokoscRek(wezel<T> * cos) {
- int prawa;
- int lewa;
- // sprawdzamy prawa odnoge
- if (cos->wskaznikNaPrawegoPotomka != nullptr) {
- prawa = wysokoscRek(cos->wskaznikNaPrawegoPotomka);
- }
- else {
- prawa = 0;
- }
- //sprawdzamy lewa odnoge
- if (cos->wskaznikNaLewegoPotomka != nullptr) {
- lewa = wysokoscRek(cos->wskaznikNaLewegoPotomka);
- }
- else {
- lewa = 0;
- }
- //zwracamy wieksza
- if (lewa < prawa) {
- return prawa;
- }
- else
- {
- return lewa;
- }
- }
- //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 wyswietlDrzewo() {
- wyswietlRek(korzen);
- }
- void wyswietlRek(wezel<T>* korzen) {
- if (korzen != nullptr) {
- std::cout << " dane " << korzen->dane << " indeks " << korzen->indeks;
- }
- if (korzen->color == kolor::czerwony)
- {
- std::cout << " czerwony ";
- }
- else {
- std::cout << " czarny ";
- }
- if (korzen->wskaznikNaLewegoPotomka == nullptr) {
- std::cout << " LP: brak ";
- }
- if (korzen->wskaznikNaLewegoPotomka != nullptr) {
- std::cout << " LP: " << korzen->wskaznikNaLewegoPotomka->indeks;
- }
- if (korzen->wskaznikNaPrawegoPotomka == nullptr) {
- std::cout << " PP: brak " << std::endl;
- }
- if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
- std::cout << " PP: " << korzen->wskaznikNaPrawegoPotomka->indeks << std::endl;
- }
- if (korzen->wskaznikNaLewegoPotomka != nullptr) {
- wyswietlRek(korzen->wskaznikNaLewegoPotomka);
- }
- if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
- wyswietlRek(korzen->wskaznikNaPrawegoPotomka);
- }
- }
- };
- int main() {
- std::random_device rd;
- std::mt19937 gen(rd());
- std::uniform_int_distribution<> losowa(1, 10000);
- drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
- CzerwonoCzarne->dodajNowyWezel(3);
- CzerwonoCzarne->wyswietlDrzewo();
- std::cout << std::endl;
- CzerwonoCzarne->dodajNowyWezel(1);
- CzerwonoCzarne->wyswietlDrzewo();
- std::cout << std::endl;
- CzerwonoCzarne->dodajNowyWezel(5);
- CzerwonoCzarne->wyswietlDrzewo();
- std::cout << std::endl;
- CzerwonoCzarne->dodajNowyWezel(2);
- CzerwonoCzarne->wyswietlDrzewo();
- std::cout << std::endl;
- CzerwonoCzarne->dodajNowyWezel(7);
- CzerwonoCzarne->dodajNowyWezel(6);
- CzerwonoCzarne->dodajNowyWezel(4);
- //CzerwonoCzarne->dodajNowyWezel(8);
- //CzerwonoCzarne->wyswietlDrzewo();
- //delete CzerwonoCzarne;
- getchar();
- /*std::cout << std::endl;
- CzerwonoCzarne->wyswietlDrzewo();
- CzerwonoCzarne->dodajNowyWezel(8);
- std::cout << std::endl;
- CzerwonoCzarne->wyswietlDrzewo();
- CzerwonoCzarne->dodajNowyWezel(9);
- std::cout << std::endl;
- CzerwonoCzarne->wyswietlDrzewo();
- CzerwonoCzarne->dodajNowyWezel(10);*/
- //const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
- //drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
- //for (int o = 1; o <= MAX_ORDER; o++)
- //{
- // const int n = pow(10, o); // rozmiar danych
- // // dodawanie do drzewa
- // clock_t t1 = clock();
- // for (int i = 0; i < n; i++)
- // {
- // int liczba = losowa(gen);
- // CzerwonoCzarne->dodajNowyWezel(liczba);
- // }
- // clock_t t2 = clock();
- // double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
- // std::cout << "Czas dodawania " << n << " elemenow: " << time << std::endl;
- /*CzerwonoCzarne->wyswietlDrzewo();
- CzerwonoCzarne->wysokosc();
- */
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement