API tools faq
paste
Advertisement
Guest User

Untitled

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