API tools faq
paste
Advertisement
ElooEminem

Untitled

ElooEminem
Apr 3rd, 2018
85
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.76 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <conio.h>
  3. #include <stdio.h>
  4. #include <time.h>
  5. using namespace std;
  6.  
  7. struct node{
  8. int val;
  9. int bf;
  10. node *left;
  11. node *right;
  12. node *up;
  13. };
  14.  
  15. void dfs_inorder(node *tree){
  16. if(tree){
  17. dfs_inorder(tree->left);
  18. cout<<endl<<tree->val;
  19. dfs_inorder(tree->right);
  20. }
  21. return;
  22. }
  23.  
  24. void dfs_preorder(node *tree){
  25. if(tree){
  26. cout<<endl<<tree->val;
  27. dfs_preorder(tree->left);
  28. dfs_preorder(tree->right);
  29. }
  30. return;
  31. }
  32.  
  33. void dfs_postorder(node *tree){
  34. if(tree){
  35. dfs_postorder(tree->left);
  36. dfs_postorder(tree->right);
  37. delete tree;
  38. }
  39. }
  40.  
  41. void lr(node *&root,node *A){
  42. node *B=A->left;
  43. node *C=B->right;
  44. node *D=A->up;
  45. B->right=C->left;
  46. if(B->right) B->right->up=B;
  47. A->left=C->right;
  48. if(A->left) A->left->up = A;
  49. C->right = A;
  50. C->left = B;
  51. A->up=B->up=C;
  52. C->up=D;
  53. if(D){
  54. if(D->left == A) D->left = C;
  55. else D->right = C;
  56. }
  57. else root=C;
  58. if(C->bf==1) A->bf=-1;
  59. else A->bf=0;
  60. if(C->bf==-1) B->bf=1;
  61. else B->bf = 0;
  62. C->bf = 0;
  63. return;
  64. }
  65.  
  66. void ll(node *&root,node *A){
  67. node *B=A->left;
  68. node *C=A->up;
  69. A->left=B->right;
  70. if(A->left) A->left->up=A;
  71. B->right=A;
  72. B->up=C;
  73. A->up=B;
  74. if(C){
  75. if(C->left==A) C->left=B;
  76. else C->right=B;
  77. }
  78. else root=B;
  79. if(B->bf==1) A->bf=B->bf=0;
  80. else{
  81. A->bf=1;
  82. B->bf=-1;
  83. }
  84. return;
  85. }
  86.  
  87. void rl(struct node *&root,struct node *A){
  88. node *B=A->right;
  89. node *C=B->left;
  90. node *D=A->up;
  91. B->left=C->right;
  92. if(B->left) B->left->up=B;
  93. A->right=C->left;
  94. if(A->right) A->right->up=A;
  95. C->left=A;
  96. C->right=B;
  97. A->up=B->up=C;
  98. C->up=D;
  99. if(D){
  100. if(D->left==A) D->left=C;
  101. else D->right=C;
  102. }
  103. else root=C;
  104. if(C->bf==-1) A->bf=1;
  105. else A->bf=0;
  106. if(C->bf==1) B->bf=-1;
  107. else B->bf=0;
  108. C->bf = 0;
  109. return;
  110. }
  111.  
  112. void rr(struct node *&root,struct node *A){
  113. node *B=A->right;
  114. node *C=A->up;
  115. A->right=B->left;
  116. if(A->right) A->right->up=A;
  117. B->left=A;
  118. B->up=C;
  119. A->up=B;
  120. if(C){
  121. if(C->left==A) C->left=B;
  122. else C->right=B;
  123. }
  124. else root=B;
  125. if(B->bf==-1) A->bf=B->bf=0;
  126. else{
  127. A->bf=-1;
  128. B->bf=1;
  129. }
  130. return;
  131. }
  132.  
  133. node *node_find(node *elem,int b){
  134. cout<<"Sciezka do elementu "<<b<<" ...";;
  135. while((elem)&&(elem->val!=b)){
  136. cout<<endl<<elem->val;
  137. if(b>=elem->val) elem=elem->right;
  138. else elem=elem->left;
  139. }
  140. return elem;
  141. }
  142.  
  143. node *node_find_prim(node *elem,int b){
  144. while((elem)&&(elem->val!=b)){
  145. if(b>=elem->val) elem=elem->right;
  146. else elem=elem->left;
  147. }
  148. return elem;
  149. }
  150.  
  151. node *node_up(node *elem){
  152. node *tmp;
  153. if(elem){
  154. if(elem->left){
  155. elem=elem->left;
  156. while(elem->right) elem=elem->right;
  157. }
  158. else
  159. do{
  160. tmp=elem;
  161. elem=elem->up;
  162. }while((elem)&&(elem->right!=tmp));
  163. }
  164. return elem;
  165. }
  166.  
  167. node *node_erase(node *&root,node *del){
  168. node *tmp;
  169. node *del1;
  170. node *del2;
  171. bool cor;
  172. if(del->left && del->right){
  173. del1=node_erase(root,node_up(del));
  174. cor=false;
  175. }
  176. else{
  177. if(del->left){
  178. del1=del->left;
  179. del->left=NULL;
  180. }
  181. else{
  182. del1=del->right;
  183. del->right=NULL;
  184. }
  185. del->bf=0;
  186. cor=true;
  187. }
  188. if(del1){
  189. del1->up=del->up;
  190. del1->left=del->left;
  191. if(del1->left) del1->left->up=del1;
  192. del1->right=del->right;
  193. if(del1->right) del1->right->up=del1;
  194. del1->bf=del->bf;
  195. }
  196. if(del->up){
  197. if(del->up->left==del) del->up->left=del1;
  198. else del->up->right=del1;
  199. }
  200. else root=del1;
  201. if(cor){
  202. del2=del1;
  203. del1=del->up;
  204. while(del1){
  205. if(!del1->bf){
  206. if(del1->left==del2) del1->bf=-1;
  207. else del1->bf = 1;
  208. break;
  209. }
  210. else{
  211. if(((del1->bf==1) && (del1->left==del2)) || ((del1->bf==-1) && (del1->right==del2))){
  212. del1->bf=0;
  213. del2=del1;
  214. del1=del1->up;
  215. }
  216. else{
  217. if(del1->left==del2) tmp = del1->right;
  218. else tmp = del1->left;
  219. if(!tmp->bf){
  220. if(del1->bf==1) ll(root,del1);
  221. else rr(root,del1);
  222. break;
  223. }
  224. else if(del1->bf==tmp->bf){
  225. if(del1->bf==1) ll(root,del1);
  226. else rr(root,del1);
  227. del2=tmp;
  228. del1=tmp->up;
  229. }
  230. else{
  231. if(del1->bf==1) lr(root,del1);
  232. else rl(root,del1);
  233. del2=del1->up;
  234. del1=del2->up;
  235. }
  236. }
  237. }
  238. }
  239. }
  240. return del;
  241. }
  242.  
  243. node *root4ever;
  244.  
  245. void node_add(struct node *&tree,int b){
  246. struct node *add=new struct node;
  247. add->val=b;
  248. add->left=NULL;
  249. add->right=NULL;
  250. add->bf=0;
  251. struct node *tmp;
  252. struct node *root=tree;
  253. bool t;
  254. if(tree==NULL){
  255. tree=new struct node;
  256. tree->left=NULL;
  257. tree->right=NULL;
  258. tree->up=NULL;
  259. tree->val=b;
  260. return;
  261. }
  262. while(true){
  263. if(b>=tree->val){
  264. if(tree->right==NULL){
  265. tree->right=add;
  266. add->up=tree;
  267. break;
  268. }
  269. else tree=tree->right;
  270. }
  271. else{
  272. if(tree->left==NULL){
  273. tree->left=add;
  274. add->up=tree;
  275. break;
  276. }
  277. else tree=tree->left;
  278. }
  279. }
  280. if(tree->bf) tree->bf=0;
  281. else{
  282. if(tree->left==add) tree->bf=1;
  283. else tree->bf=-1;
  284. tmp=tree->up;
  285. t=false;
  286. while(tmp){
  287. if(tmp->bf){
  288. t=true;
  289. break;
  290. }
  291. if(tmp->left==tree) tmp->bf=1;
  292. else tmp->bf=-1;
  293.  
  294. tree=tmp;
  295. tmp=tmp->up;
  296. }
  297. if(t){
  298. if(tmp->bf==1){
  299. if(tmp->right==tree) tmp->bf=0;
  300. else if(tree->bf==-1) lr(root,tmp);
  301. else ll(root,tmp);
  302. }
  303. else{
  304. if(tmp->left==tree) tmp->bf=0;
  305. else if(tree->bf==1) rl(root,tmp);
  306. else rr(root,tmp);
  307. }
  308. }
  309. }
  310. while(root->up) root=root->up;
  311. dfs_preorder(root);
  312. return;
  313. }
  314.  
  315. void com(int comm,node *&root){
  316.  
  317. return;
  318. }
  319.  
  320. int *dane(int n){
  321. int index1;
  322. int index2;
  323. int tmp;
  324. int *tab=new int[n];
  325. for(int i=0;i<n;i++) tab[i]=i;
  326. for(int i=0;i<n*10;i++){
  327. index1=rand()%n;
  328. index2=rand()%n;
  329. tmp=tab[index1];
  330. tab[index1]=tab[index2];
  331. tab[index2]=tmp;
  332. }
  333. return tab;
  334. }
  335.  
  336. void dane_delete(int *tab,int n){
  337. delete []tab;
  338. return;
  339. }
  340.  
  341. int main(){
  342. srand(time(NULL));
  343. int cmd;
  344. node *root=NULL;
  345. cout<<"1. dodaj elem (int)\n";
  346. cout<<"2. usun elem (int wartosc)\n";
  347. cout<<"3. znajdz elem (int wartosc)\n";
  348. cout<<"4. dfs preorder, post order\n";
  349. cout<<"5. stworz drzewo losowych (int ilosc)\n";
  350. cout<<"6. usun drzewo\n";
  351. //while(cin>>cmd) com(cmd,root);
  352.  
  353. clock_t start;
  354. int *tab;
  355. system("cls");
  356. for(int i=500000;i<=5000000;i=i+500000) cout<<i<<" ";
  357. getche();
  358. system("cls");
  359. for(int i=500000;i<=5000000;i=i+500000){
  360. tab=dane(i);
  361.  
  362. getche();
  363.  
  364. start=clock();
  365. for(int j=0;j<i;j++) node_add(root,tab[j]);
  366. cout<<endl<<clock()-start;
  367.  
  368. getche();
  369. //TUTAJ DZIKIE DRUKOWANIA
  370. start=clock();
  371. for(int j=0;j<i/10;j++) node_find_prim(root,j);
  372. cout<<endl<<clock()-start;
  373.  
  374. getche();
  375.  
  376. start=clock();
  377. dfs_postorder(root);
  378. cout<<endl<<clock()-start;
  379.  
  380. cout<<endl<<endl;
  381. dane_delete(tab,i);
  382.  
  383. root=NULL;
  384. }
  385.  
  386. getche();
  387. return 0;
  388. }
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!