API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
88
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.21 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::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. }
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!