SHARE
TWEET

Untitled

a guest Nov 19th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <time.h>
  3. #include <exception>
  4. #include <random>
  5. enum class kolor
  6. {
  7.     czarny, czerwony
  8. };
  9. template  <typename T>
  10. struct wezel {
  11.     T dane;
  12.     wezel<T>* wskaznikNaRodzica = nullptr;
  13.     wezel<T>* wskaznikNaPrawegoPotomka = nullptr;
  14.     wezel<T>* wskaznikNaLewegoPotomka = nullptr;
  15.     unsigned int indeks = 0;
  16.  
  17.     kolor color = kolor::czerwony;
  18. };
  19. template< typename T>
  20. struct drzewo {
  21.     wezel<T>* korzen = nullptr;
  22.     int rozmiar = 0;
  23.     void dodajNowyWezel(T datas) {
  24.         wezel<T>* dziecko = new wezel<T>;
  25.         dziecko->dane = datas;
  26.         dziecko->indeks = rozmiar;
  27.         if (rozmiar == 0) {
  28.             dziecko->wskaznikNaRodzica = nullptr;
  29.             dziecko->wskaznikNaPrawegoPotomka = nullptr;
  30.             dziecko->wskaznikNaLewegoPotomka = nullptr;
  31.             korzen = dziecko;
  32.             korzen->color = kolor::czarny;
  33.         }
  34.         else {
  35.             wezel<T>* tymczasowy = korzen;
  36.             //szukamy gdzie jest miejsce dla dziecka
  37.             //sprawdzamy czy datas jest wieksze czy mniejsze od danych w tymczasowym
  38.             while (tymczasowy != nullptr) {
  39.                 //prawa odnoga
  40.                 if (tymczasowy->dane <= datas)
  41.                 {
  42.                     //przechodzimy do kolejnego wezła 
  43.                     if (tymczasowy->wskaznikNaPrawegoPotomka == nullptr) {
  44.                         tymczasowy->wskaznikNaPrawegoPotomka = dziecko;
  45.                         dziecko->wskaznikNaRodzica = tymczasowy;
  46.                         tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka->wskaznikNaPrawegoPotomka;
  47.                     }
  48.                     else {
  49.                         tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka;
  50.                     }
  51.                 }
  52.                 //lewa odnoga
  53.                 else if (tymczasowy->dane > datas) {
  54.                     //przechodzimy do kolejnego wezła
  55.                     if (tymczasowy->wskaznikNaLewegoPotomka == nullptr) {
  56.                         tymczasowy->wskaznikNaLewegoPotomka = dziecko;
  57.                         dziecko->wskaznikNaRodzica = tymczasowy;
  58.                         tymczasowy = tymczasowy->wskaznikNaLewegoPotomka->wskaznikNaLewegoPotomka;
  59.                     }
  60.                     else {
  61.                         tymczasowy = tymczasowy->wskaznikNaLewegoPotomka;
  62.                     }
  63.                 }
  64.                 else
  65.                     std::cout << "COS NIE TAK!!!";
  66.             }
  67.             sprawdzKolory(dziecko);
  68.         }
  69.         rozmiar++;
  70.  
  71.     }
  72.     void sprawdzKolory(wezel<T>* ostatni) {
  73.         while (ostatni != korzen && ostatni->wskaznikNaRodzica->color != kolor::czarny) {
  74.             wezel<T>* wujek = new wezel<T>;
  75.             //ustalenie czy wujek jest z prawej czy lewej strony(pochodzenie wujka)
  76.             if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  77.                 wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka;
  78.             }
  79.             else if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka)
  80.             {
  81.                 wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka;
  82.             }
  83.             else {
  84.                 std::cout << "Cos nie tak z wujkiem!!!" << std::endl;
  85.             }
  86.             if (wujek->color == kolor::czerwony) {
  87.                 ostatni->wskaznikNaRodzica->color = kolor::czarny;
  88.                 wujek->color = kolor::czarny;
  89.                 ostatni = ostatni->wskaznikNaRodzica->wskaznikNaRodzica;
  90.             }
  91.         }
  92.  
  93.         wezel<T>* wujek = new wezel<T>;
  94.         //ustalenie czy wujek jest z prawej czy lewej strony(pochodzenie wujka)
  95.         if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  96.             wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka;
  97.         }
  98.         else if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka)
  99.         {
  100.             wujek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka;
  101.         }
  102.         else {
  103.             std::cout << "Cos nie tak z wujkiem!!!" << std::endl;
  104.         }
  105.         if (wujek->color == kolor::czarny) {
  106.             //Left Left Case
  107.             if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  108.                 RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  109.                 ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  110.                 ostatni->wskaznikNaRodzica->color = kolor::czarny;
  111.             }
  112.             //Left Right Case
  113.             if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
  114.                 RotacjaLewa(ostatni->wskaznikNaRodzica, ostatni);
  115.                 //wywołanie Left Left Case
  116.                 RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  117.                 ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  118.                 ostatni->wskaznikNaRodzica->color = kolor::czarny;
  119.             }
  120.             //Right Right Case
  121.             if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
  122.                 RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  123.                 ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  124.                 ostatni->wskaznikNaRodzica->color = kolor::czarny;
  125.             }
  126.             // Right Left Case
  127.             if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  128.                 RotacjaPrawa(ostatni->wskaznikNaRodzica, ostatni);
  129.                 //Right Right Case
  130.                 RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  131.                 ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  132.                 ostatni->wskaznikNaRodzica->color = kolor::czarny;
  133.             }
  134.         }
  135.     }
  136.     void RotacjaPrawa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
  137.         naRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka = naRodzica->wskaznikNaLewegoPotomka;
  138.         naRodzica->wskaznikNaRodzica = naDziecko;
  139.         naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
  140.         naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
  141.     }
  142.     void RotacjaLewa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
  143.         naRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka = naRodzica->wskaznikNaPrawegoPotomka;
  144.         naRodzica->wskaznikNaRodzica = naDziecko;
  145.         naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;
  146.         naDziecko->wskaznikNaLewegoPotomka = naRodzica;
  147.     }
  148.     wezel<T>* znajdzDane(T datas) {
  149.         wezel<T>* cos = korzen;
  150.         while (cos) {
  151.             if (cos->dane == datas) {
  152.                 return cos;
  153.             }
  154.             if (datas > cos->dane) {
  155.                 cos = cos->wskaznikNaPrawegoPotomka;
  156.             }
  157.             else {
  158.                 cos = cos->wskaznikNaLewegoPotomka;
  159.             }
  160.             return nullptr;
  161.         }
  162.     }
  163.     void wyczyscDrzewo() {
  164.         wezel<T>* kasownik = korzen;
  165.         wyczyscDrzewoRek(kasownik);
  166.     }
  167.     void wyczyscDrzewoRek(wezel<T>* kasownik) {
  168.         if (kasownik == nullptr) {
  169.             return;
  170.         }
  171.         else {
  172.             wyczyscDrzewoRek(kasownik->wskaznikNaLewegoPotomka);
  173.             wyczyscDrzewoRek(kasownik->wskaznikNaPrawegoPotomka);
  174.             delete kasownik;
  175.         }
  176.     }
  177.     void wysokosc() {
  178.         int wysokosc = wysokoscRek(korzen);
  179.         std::cout << "wysokosc drzewa: " << wysokosc << std::endl;
  180.     }
  181.     int wysokoscRek(wezel<T> * cos) {
  182.         int prawa;
  183.         int lewa;
  184.         // sprawdzamy prawa odnoge
  185.         if (cos->wskaznikNaPrawegoPotomka != nullptr) {
  186.             prawa = wysokoscRek(cos->wskaznikNaPrawegoPotomka);
  187.         }
  188.         else {
  189.             prawa = 0;
  190.         }
  191.         //sprawdzamy lewa odnoge
  192.         if (cos->wskaznikNaLewegoPotomka != nullptr) {
  193.             lewa = wysokoscRek(cos->wskaznikNaLewegoPotomka);
  194.         }
  195.         else {
  196.             lewa = 0;
  197.         }
  198.         //zwracamy wieksza
  199.         if (lewa < prawa) {
  200.             return prawa;
  201.         }
  202.         else
  203.         {
  204.             return lewa;
  205.         }
  206.     }
  207.     //przechodzenie przez wezły
  208.     void InOrder(wezel<T>* drzewo) {
  209.         InOrder(drzewo->wskaznikNaLewegoPotomka);
  210.         std::cout << drzewo->dane << ' ';
  211.         InOrder(drzewo->wskaznikNaPrawegoPotomka);
  212.     }
  213.     //PreOrder służy do kopiowania drzewa
  214.     void PreOrder(wezel<T>* drzewo) {
  215.         std::cout << drzewo->dane << ' ';
  216.         PreOrder(drzewo->wskaznikNaLewegoPotomka);
  217.         PreOrder(drzewo->wskaznikNaPrawegoPotomka);
  218.     }
  219.     void wyswietlDrzewo() {
  220.         wyswietlRek(korzen);
  221.     }
  222.     void wyswietlRek(wezel<T>* korzen) {
  223.         if (korzen != nullptr) {
  224.             std::cout << " dane " << korzen->dane << " indeks " << korzen->indeks;
  225.         }
  226.         if (korzen->color == kolor::czerwony)
  227.         {
  228.             std::cout << " czerwony ";
  229.         }
  230.         else {
  231.             std::cout << " czarny ";
  232.         }
  233.         if (korzen->wskaznikNaLewegoPotomka == nullptr) {
  234.             std::cout << " LP: brak ";
  235.         }
  236.         if (korzen->wskaznikNaLewegoPotomka != nullptr) {
  237.             std::cout << " LP: " << korzen->wskaznikNaLewegoPotomka->indeks;
  238.         }
  239.         if (korzen->wskaznikNaPrawegoPotomka == nullptr) {
  240.             std::cout << " PP: brak " << std::endl;
  241.         }
  242.         if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
  243.             std::cout << " PP: " << korzen->wskaznikNaPrawegoPotomka->indeks << std::endl;
  244.         }
  245.         if (korzen->wskaznikNaLewegoPotomka != nullptr) {
  246.             wyswietlRek(korzen->wskaznikNaLewegoPotomka);
  247.         }
  248.         if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
  249.             wyswietlRek(korzen->wskaznikNaPrawegoPotomka);
  250.         }
  251.  
  252.     }
  253. };
  254. int main() {
  255.     std::random_device rd;
  256.     std::mt19937 gen(rd());
  257.     std::uniform_int_distribution<> losowa(1, 10000);
  258.  
  259.     drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
  260.     CzerwonoCzarne->dodajNowyWezel(3);
  261.  
  262.     CzerwonoCzarne->dodajNowyWezel(1);
  263.  
  264.     CzerwonoCzarne->dodajNowyWezel(5);
  265.     CzerwonoCzarne->wyswietlDrzewo();
  266.  
  267.     CzerwonoCzarne->dodajNowyWezel(2);
  268.  
  269.     CzerwonoCzarne->dodajNowyWezel(7);
  270.  
  271.     CzerwonoCzarne->dodajNowyWezel(6);
  272.  
  273.     CzerwonoCzarne->dodajNowyWezel(4);
  274.  
  275.     //CzerwonoCzarne->dodajNowyWezel(8);
  276.     //CzerwonoCzarne->wyswietlDrzewo();
  277.     //delete CzerwonoCzarne;
  278.     getchar();
  279.  
  280.     /*std::cout << std::endl;
  281.     CzerwonoCzarne->wyswietlDrzewo();
  282.     CzerwonoCzarne->dodajNowyWezel(8);
  283.     std::cout << std::endl;
  284.     CzerwonoCzarne->wyswietlDrzewo();
  285.     CzerwonoCzarne->dodajNowyWezel(9);
  286.     std::cout << std::endl;
  287.     CzerwonoCzarne->wyswietlDrzewo();
  288.  
  289.     CzerwonoCzarne->dodajNowyWezel(10);*/
  290.     //const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
  291.     //drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
  292.     //for (int o = 1; o <= MAX_ORDER; o++)
  293.     //{
  294.     //  const int n = pow(10, o); // rozmiar danych
  295.     //  // dodawanie do drzewa
  296.     //  clock_t t1 = clock();
  297.     //  for (int i = 0; i < n; i++)
  298.     //  {
  299.     //      int liczba = losowa(gen);
  300.     //      CzerwonoCzarne->dodajNowyWezel(liczba);
  301.     //  }
  302.     //  clock_t t2 = clock();
  303.     //  double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
  304.     //  std::cout << "Czas dodawania " << n << " elemenow: " << time << std::endl;
  305.     /*CzerwonoCzarne->wyswietlDrzewo();
  306.     CzerwonoCzarne->wysokosc();
  307. */
  308.  
  309. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top