API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
134
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.71 KB | None | 0 0
raw download clone embed print report
  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::czerwony) {
  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.  
  87. if (wujek->color == kolor::czerwony) {
  88. ostatni->wskaznikNaRodzica->color = kolor::czarny;
  89. wujek->color = kolor::czarny;
  90. ostatni = ostatni->wskaznikNaRodzica->wskaznikNaRodzica;
  91. break;
  92. }
  93.  
  94. else if (wujek->color == kolor::czarny) {
  95. //Left Left Case
  96. if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  97. RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  98. ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  99. ostatni->wskaznikNaRodzica->color = kolor::czarny;
  100. }
  101. //Left Right Case
  102. if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
  103. RotacjaLewa(ostatni->wskaznikNaRodzica, ostatni);
  104. //wywołanie Left Left Case
  105. RotacjaPrawa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  106. ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  107. ostatni->wskaznikNaRodzica->color = kolor::czarny;
  108. }
  109. //Right Right Case
  110. if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaPrawegoPotomka) {
  111. RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  112. ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  113. ostatni->wskaznikNaRodzica->color = kolor::czarny;
  114. }
  115. // Right Left Case
  116. if (ostatni->wskaznikNaRodzica == ostatni->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka && ostatni == ostatni->wskaznikNaRodzica->wskaznikNaLewegoPotomka) {
  117. RotacjaPrawa(ostatni->wskaznikNaRodzica, ostatni);
  118. //Right Right Case
  119. RotacjaLewa(ostatni->wskaznikNaRodzica->wskaznikNaRodzica, ostatni->wskaznikNaRodzica);
  120. ostatni->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
  121. ostatni->wskaznikNaRodzica->color = kolor::czarny;
  122. }
  123. }
  124. }
  125. }
  126. void RotacjaPrawa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
  127. naRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka = naRodzica->wskaznikNaLewegoPotomka;
  128. naRodzica->wskaznikNaRodzica = naDziecko;
  129. naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
  130. naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
  131. }
  132. void RotacjaLewa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
  133. naRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka = naRodzica->wskaznikNaPrawegoPotomka;
  134. naRodzica->wskaznikNaRodzica = naDziecko;
  135. naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;
  136. naDziecko->wskaznikNaLewegoPotomka = naRodzica;
  137. }
  138. wezel<T>* znajdzDane(T datas) {
  139. wezel<T>* cos = korzen;
  140. while (cos) {
  141. if (cos->dane == datas) {
  142. return cos;
  143. }
  144. if (datas > cos->dane) {
  145. cos = cos->wskaznikNaPrawegoPotomka;
  146. }
  147. else {
  148. cos = cos->wskaznikNaLewegoPotomka;
  149. }
  150. return nullptr;
  151. }
  152. }
  153. void wyczyscDrzewo() {
  154. wezel<T>* kasownik = korzen;
  155. wyczyscDrzewoRek(kasownik);
  156. }
  157. void wyczyscDrzewoRek(wezel<T>* kasownik) {
  158. if (kasownik == nullptr) {
  159. return;
  160. }
  161. else {
  162. wyczyscDrzewoRek(kasownik->wskaznikNaLewegoPotomka);
  163. wyczyscDrzewoRek(kasownik->wskaznikNaPrawegoPotomka);
  164. delete kasownik;
  165. }
  166. }
  167. void wysokosc() {
  168. int wysokosc = wysokoscRek(korzen);
  169. std::cout << "wysokosc drzewa: " << wysokosc << std::endl;
  170. }
  171. int wysokoscRek(wezel<T> * cos) {
  172. int prawa;
  173. int lewa;
  174. // sprawdzamy prawa odnoge
  175. if (cos->wskaznikNaPrawegoPotomka != nullptr) {
  176. prawa = wysokoscRek(cos->wskaznikNaPrawegoPotomka);
  177. }
  178. else {
  179. prawa = 0;
  180. }
  181. //sprawdzamy lewa odnoge
  182. if (cos->wskaznikNaLewegoPotomka != nullptr) {
  183. lewa = wysokoscRek(cos->wskaznikNaLewegoPotomka);
  184. }
  185. else {
  186. lewa = 0;
  187. }
  188. //zwracamy wieksza
  189. if (lewa < prawa) {
  190. return prawa;
  191. }
  192. else
  193. {
  194. return lewa;
  195. }
  196. }
  197. //przechodzenie przez wezły
  198. void InOrder(wezel<T>* drzewo) {
  199. InOrder(drzewo->wskaznikNaLewegoPotomka);
  200. std::cout << drzewo->dane << ' ';
  201. InOrder(drzewo->wskaznikNaPrawegoPotomka);
  202. }
  203. //PreOrder służy do kopiowania drzewa
  204. void PreOrder(wezel<T>* drzewo) {
  205. std::cout << drzewo->dane << ' ';
  206. PreOrder(drzewo->wskaznikNaLewegoPotomka);
  207. PreOrder(drzewo->wskaznikNaPrawegoPotomka);
  208. }
  209. void wyswietlDrzewo() {
  210. wyswietlRek(korzen);
  211. }
  212. void wyswietlRek(wezel<T>* korzen) {
  213. if (korzen != nullptr) {
  214. std::cout << " dane " << korzen->dane << " indeks " << korzen->indeks;
  215. }
  216. if (korzen->color == kolor::czerwony)
  217. {
  218. std::cout << " czerwony ";
  219. }
  220. else {
  221. std::cout << " czarny ";
  222. }
  223. if (korzen->wskaznikNaLewegoPotomka == nullptr) {
  224. std::cout << " LP: brak ";
  225. }
  226. if (korzen->wskaznikNaLewegoPotomka != nullptr) {
  227. std::cout << " LP: " << korzen->wskaznikNaLewegoPotomka->indeks;
  228. }
  229. if (korzen->wskaznikNaPrawegoPotomka == nullptr) {
  230. std::cout << " PP: brak " << std::endl;
  231. }
  232. if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
  233. std::cout << " PP: " << korzen->wskaznikNaPrawegoPotomka->indeks << std::endl;
  234. }
  235. if (korzen->wskaznikNaLewegoPotomka != nullptr) {
  236. wyswietlRek(korzen->wskaznikNaLewegoPotomka);
  237. }
  238. if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
  239. wyswietlRek(korzen->wskaznikNaPrawegoPotomka);
  240. }
  241.  
  242. }
  243. };
  244. int main() {
  245. std::random_device rd;
  246. std::mt19937 gen(rd());
  247. std::uniform_int_distribution<> losowa(1, 10000);
  248.  
  249. drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
  250. CzerwonoCzarne->dodajNowyWezel(3);
  251.  
  252. CzerwonoCzarne->dodajNowyWezel(1);
  253.  
  254.  
  255. CzerwonoCzarne->dodajNowyWezel(5);
  256.  
  257.  
  258. CzerwonoCzarne->dodajNowyWezel(2);
  259.  
  260.  
  261. CzerwonoCzarne->dodajNowyWezel(7);
  262. CzerwonoCzarne->wyswietlDrzewo();
  263. std::cout << std::endl;
  264. CzerwonoCzarne->dodajNowyWezel(6);
  265.  
  266. CzerwonoCzarne->dodajNowyWezel(4);
  267.  
  268. //CzerwonoCzarne->dodajNowyWezel(8);
  269. //CzerwonoCzarne->wyswietlDrzewo();
  270. //delete CzerwonoCzarne;
  271. getchar();
  272.  
  273. /*std::cout << std::endl;
  274. CzerwonoCzarne->wyswietlDrzewo();
  275. CzerwonoCzarne->dodajNowyWezel(8);
  276. std::cout << std::endl;
  277. CzerwonoCzarne->wyswietlDrzewo();
  278. CzerwonoCzarne->dodajNowyWezel(9);
  279. std::cout << std::endl;
  280. CzerwonoCzarne->wyswietlDrzewo();
  281.  
  282. CzerwonoCzarne->dodajNowyWezel(10);*/
  283. //const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
  284. //drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
  285. //for (int o = 1; o <= MAX_ORDER; o++)
  286. //{
  287. // const int n = pow(10, o); // rozmiar danych
  288. // // dodawanie do drzewa
  289. // clock_t t1 = clock();
  290. // for (int i = 0; i < n; i++)
  291. // {
  292. // int liczba = losowa(gen);
  293. // CzerwonoCzarne->dodajNowyWezel(liczba);
  294. // }
  295. // clock_t t2 = clock();
  296. // double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
  297. // std::cout << "Czas dodawania " << n << " elemenow: " << time << std::endl;
  298. /*CzerwonoCzarne->wyswietlDrzewo();
  299. CzerwonoCzarne->wysokosc();
  300. */
  301.  
  302. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!