API tools faq
paste
Advertisement
Guest User

Untitled

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