API tools faq
paste
Advertisement
ElooEminem

Untitled

ElooEminem
Dec 10th, 2018
101
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 23.19 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <sstream>
  3. #include <conio.h>
  4. #include <vector.h>
  5.  
  6. using namespace std;
  7.  
  8. int max(int a,int b){
  9. return (a>b) ? a : b;
  10. }
  11.  
  12. class Node{
  13. public:
  14. int key;
  15. int h;
  16. char *key_char;
  17. Node *left;
  18. Node *right;
  19. Node(int key){
  20. h=1;
  21. key_char=new char[10];
  22. this->key=key;
  23. this->left=NULL;
  24. this->right=NULL;
  25. stringstream tmp;
  26. tmp<<key;
  27. tmp>>this->key_char;
  28. }
  29. ~Node(){
  30. delete [] this->key_char;
  31. }
  32. };
  33.  
  34. class Tree_BST{
  35. public:
  36. Node *root;
  37. Tree_BST(){
  38. this->root=NULL;
  39. }
  40.  
  41. bool Insert(int key){
  42. cout<<endl<<"Dodaje "<<key;
  43. if(!this->root){ //Drzewo puste
  44. this->root=new Node(key);
  45. return true;
  46. }
  47. else{ //Drzewo niepuste
  48. Node *it=this->root;
  49. Node *NewNode;
  50. while(true){
  51. if(key < it->key)
  52. if(it->left)
  53. it=it->left; //Juz istnieje it->left, idziemy w lewo
  54. else{
  55. NewNode=it->left=new Node(key); //Dodanie Node z key jako it->left
  56. break;
  57. }
  58. else if(key > it->key)
  59. if(it->right)
  60. it=it->right; //Juz istnieje it->right, idziemy w prawo
  61. else{
  62. NewNode=it->right=new Node(key); //Dodanie Node z key jako it->right
  63. break;
  64. }
  65. else{
  66. return false; //Klucz key juz istnieje
  67. }
  68. }
  69. //Scope tu = dodano jakis node, jazda z wywazaniem !!!
  70. vector < Node* > stack=this->Find(this->root,NewNode->key);
  71. for(int i=stack.size()-2 ; i >= 0 ; i--)
  72. stack[i]->h=Nmax(stack[i]->left,stack[i]->right)+1;
  73. int imb=-1;
  74. for(int i=stack.size()-2 ; i >= 0 ; i-- ){
  75. if( stack[i]->left && stack[i]->right ){
  76. if( abs( stack[i]->left->h - stack[i]->right->h ) > 1){
  77. imb=i;
  78. break;
  79. }
  80. }
  81. else if( stack[i]->left ){
  82. if( abs( stack[i]->left->h - 1 ) > 1){
  83. imb=i;
  84. break;
  85. }
  86. }
  87. else{
  88. if( abs( stack[i]->right->h - 1 ) > 1){
  89. imb=i;
  90. break;
  91. }
  92. }
  93. }
  94. if(stack[imb]==this->root){
  95. cout<<"\n*-------------------------------*\n\nRoot: (lewy,prawy) = "<<this->root->left<<"\t"<<this->root->right << "\n\t\t "<<this->root->left->key<<"\t"<<this->root->right->key<<"\n"<< "\n\t\t "<<this->root->left->h<<"\t"<<this->root->right->h<<"\n";
  96. cout<<endl<< (stack[imb]->left && stack[imb]->right);
  97. }
  98. if( imb != -1 ){
  99. if( stack[imb]->left == stack[imb+1] ){ //Lewo...
  100. if(stack[imb+1]->left==stack[imb+2]) //Lewo ... lewo
  101. this->LL(stack,imb);
  102. else //Lewo ... prawo
  103. this->LR(stack,imb);
  104. }
  105. else{ //Prawo...
  106. if(stack[imb+1]->left==stack[imb+2]) //Prawo ... lewo
  107. this->RL(stack,imb);
  108. else //Prawo ... prawo
  109. this->RR(stack,imb);
  110. }
  111. }
  112. stack.clear();
  113. return true;
  114. }
  115. }
  116.  
  117. void Insert_multiple(int n){
  118. for(int i=0;i<n;i++)
  119. this->Insert( rand()%90001 + 9999 );
  120. }
  121.  
  122. void DFS_preorder(){
  123. int n=0;
  124. this->DFS_preorder_rec(this->root,&n);
  125. cout<<"\nPrzeszukano "<<n<<" elementow.";
  126. return;
  127. }
  128.  
  129. void DFS_inorder(){
  130. int n=0;
  131. this->DFS_inorder_rec(this->root,&n);
  132. cout<<"\nPrzeszukano "<<n<<" elementow.";
  133. return;
  134. }
  135.  
  136. void DFS_postorder(){
  137. int n=0;
  138. this->DFS_postorder_rec(this->root,&n);
  139. cout<<"\nPrzeszukano "<<n<<" elementow.";
  140. return;
  141. }
  142.  
  143. vector < Node* > Find(Node *root,int key){
  144. vector < Node* > stack;
  145. if(!root) //Drzewo puste, zwacam pusty stos
  146. return stack;
  147. if(root->key==key){ //Korzen - elementem szukanym, zwracam stos z 1 elementem
  148. stack.push_back(this->root);
  149. return stack;
  150. }
  151. Node *it=root;
  152. while(true){
  153. if(!it){ // Prawda <=> nie ma key w drzewie, zwracam pusty stos
  154. stack.clear();
  155. return stack;
  156. }
  157. stack.push_back(it);
  158. if(key < it->key) //Idziemy w lewo
  159. it=it->left;
  160. else if(key > it->key) //Idziemy w prawo
  161. it=it->right;
  162. else //It jest szukanym nodem - bedzie na wierzchu stosu
  163. return stack;
  164. }
  165. }
  166.  
  167. bool Delete(int key){
  168. Node *x=NULL;
  169. vector < Node* > stack=Find(this->root,key); //Tak btw to o ile istnieje: stack[ stack.size()-1 ] , jest to node do usuniecia,
  170. Node *tmp; //a o ile istnieje: stack[ stack.size()-2 ] , jest to jego parent node!
  171. if( !stack.size() ) //W drzewie nie ma noda z takim kluczem
  172. return false;
  173. if( !stack[ stack.size()-1 ]->left && !stack[ stack.size()-1 ]->right ) //Node do usuniecia nie ma potomkow
  174. if( stack.size() == 1 ){ //Node do usuniecia jest rootem
  175. delete this->root;
  176. this->root=NULL;
  177. }
  178. else{ //Node do usuniecia nie jest rootem
  179. if( stack[ stack.size()-2 ]->left == stack[ stack.size()-1 ] ) //Node do usuniecia jest lewym potomkiem swojego parent noda
  180. stack[ stack.size()-2 ]->left=NULL;
  181. else //Node do usuniecia jest prawym potomkiem swojego parent noda
  182. stack[ stack.size()-2 ]->right=NULL;
  183. x=stack[ stack.size()-2 ];
  184. delete stack[ stack.size()-1 ];
  185. }
  186. else if( !stack[ stack.size()-1 ]->left || !stack[ stack.size()-1 ]->left ){ //Node do usuniecia ma dokladnie jednego potomka
  187. if( stack[ stack.size()-1 ]->left ) //Ten potomek jest lewym
  188. tmp=stack[ stack.size()-1 ]->left;
  189. else //Ten potomek jest prawym
  190. tmp=stack[ stack.size()-1 ]->right;
  191. if( stack.size() == 1 ){ //Node do usuniecia jest rootem
  192. this->root=tmp;
  193. delete stack[ stack.size()-1 ];
  194. }
  195. else{ //Node do usuniecia nie jest rootem
  196. if( stack[ stack.size()-2 ]->left == stack[ stack.size()-1 ] ) //Node do usuniecia jest lewym potomkiem swojego parent noda
  197. stack[ stack.size()-2 ]->left=tmp;
  198. else //Node do usuniecia jest prawym potomkiem swojego parent noda
  199. stack[ stack.size()-2 ]->right=tmp;
  200. delete stack[ stack.size()-1 ];
  201. x=stack[ stack.size()-2 ];
  202. }
  203. }
  204. else{ //Node do usuniecia ma 2 potomkow
  205. Node *tmp_up=stack[ stack.size()-1 ];
  206. Node *tmp=tmp_up->left;
  207. while(tmp->right){ //tmp - najwiekszy element lewego poddrzewa, zastapi usunietego noda
  208. tmp_up=tmp; //tmp_up - parent node tmp
  209. tmp=tmp->right;
  210. }
  211. x=tmp_up;
  212. if( stack.size() == 1 ){ //Node do usuniecia jest rootem
  213. if(tmp == tmp_up->left) //tmp jest lewym potomkiem tmp_up
  214. tmp_up->left=NULL;
  215. else //tmp jest prawym potomkiem tmp_up
  216. tmp_up->right=NULL;
  217. tmp->left=this->root->left;
  218. tmp->right=this->root->right;
  219. Node *tmp_root=this->root;
  220. this->root=tmp;
  221. delete tmp_root;
  222. }
  223. else{ //Node do usuniecia nie jest rootem
  224. if(tmp == tmp_up->left) //tmp jest lewym potomkiem tmp_up
  225. tmp_up->left=NULL;
  226. else //tmp jest prawym potomkiem tmp_up
  227. tmp_up->right=NULL;
  228. tmp->left=stack[ stack.size()-1 ]->left;
  229. tmp->right=stack[ stack.size()-1 ]->right;
  230. Node *tmp_root=stack[ stack.size()-1 ];
  231. if( stack[ stack.size()-1 ] == stack[ stack.size()-2 ]->left ) //Node do usuniecia jest lewym potomkiem swojego parent noda
  232. stack[ stack.size()-2 ]->left=tmp;
  233. else //Node do usuniecia jest prawym potomkiem swojego parent noda
  234. stack[ stack.size()-2 ]->right=tmp;
  235. stack[ stack.size()-1 ]=tmp;
  236. delete tmp_root;
  237. }
  238. }
  239. stack.clear();
  240. stack=this->Find(this->root,x->key);
  241. for(int i=stack.size()-2 ; i >= 0 ; i--)
  242. stack[i]->h=Nmax(stack[i]->left,stack[i]->right)+1;
  243. int imb=-1;
  244. cout<<"\nSzukam disbalancow:";
  245. for(int i=stack.size()-2 ; i >= 0 ; i-- ){
  246. cout<<" ; "<<stack[i]->key<<" "<<stack[i]->h;
  247. if( stack[i]->left && stack[i]->right ){
  248. if( abs( stack[i]->left->h - stack[i]->right->h ) > 1){
  249. cout<<"\nMam disballanca (l,r): "<<stack[i]->key<<" , "<<stack[i]->h<<" lewy: "<<stack[i]->left->key<<" , "<<stack[i]->left->h<<" prawy : "<<stack[i]->right->key<<" , "<<stack[i]->right->h;
  250. imb=i;
  251. break;
  252. }
  253. }
  254. else if( stack[i]->left ){
  255. if( abs( stack[i]->left->h - 1 ) > 1){
  256. cout<<"\nMam disballanca (l): "<<stack[i]->key<<" , "<<stack[i]->h<<" lewy: "<<stack[i]->left->key<<" , "<<stack[i]->left->h<<" prawy : "<<stack[i]->right;
  257. imb=i;
  258. break;
  259. }
  260. }
  261. else{
  262. if( abs( stack[i]->right->h - 1 ) > 1){
  263. cout<<"\nMam disballanca (r): "<<stack[i]->key<<" , "<<stack[i]->h<<" prawy : "<<stack[i]->right->key<<" , "<<stack[i]->right->h<<" lewy : "<<stack[i]->left;
  264. imb=i;
  265. break;
  266. }
  267. }
  268. }
  269. if(stack[imb]==this->root){
  270. cout<<"\n*-------------------------------*\n\nRoot: (lewy,prawy) = "<<this->root->left<<"\t"<<this->root->right << "\n\t\t "<<this->root->left->key<<"\t"<<this->root->right->key<<"\n"<< "\n\t\t "<<this->root->left->h<<"\t"<<this->root->right->h<<"\n";
  271. cout<<endl<< (stack[imb]->left && stack[imb]->right);
  272. }
  273. if( imb != -1 ){
  274. if( stack[imb]->left == stack[imb+1] ){ //Lewo...
  275. if(stack[imb+1]->left==stack[imb+2]) //Lewo ... lewo
  276. this->LL(stack,imb);
  277. else //Lewo ... prawo
  278. this->LR(stack,imb);
  279. }
  280. else{ //Prawo...
  281. if(stack[imb+1]->left==stack[imb+2]) //Prawo ... lewo
  282. this->RL(stack,imb);
  283. else //Prawo ... prawo
  284. this->RR(stack,imb);
  285. }
  286. }
  287. stack.clear();
  288. return true;
  289. }
  290.  
  291. ~Tree_BST(){
  292. this->Delete_whole();
  293. }
  294.  
  295. void Delete_whole(){
  296. this->Delete_whole_rec(this->root);
  297. this->root=NULL;
  298. }
  299.  
  300. private:
  301.  
  302. int Nmax(Node *a,Node *b){
  303. int arg1 = (a) ? a->h : 1;
  304. int arg2 = (b) ? b->h : 1;
  305. return max(arg1,arg2);
  306. }
  307.  
  308. void LL(vector < Node* > stack,int imb){ //Rotacja lewo ... lewo
  309. Node *c=stack[imb];
  310. Node *b=c->left;
  311. Node *a=b->left;
  312. Node *T0=a->left;
  313. Node *T1=a->right;
  314. Node *T2=b->right;
  315. Node *T3=c->right;
  316. a->h=Nmax(T0,T1)+1; //Te wysokosci sie zmienia
  317. c->h=Nmax(T2,T3)+1;
  318. b->h=Nmax(a,c)+1;
  319. if(this->root==c) //c jest rootem, trzeba ustawic nowy
  320. this->root=b;
  321. else //c nie jest rootem
  322. if(stack[imb] == stack[imb-1]->left)
  323. stack[imb-1]->left=b;
  324. else
  325. stack[imb-1]->right=b;
  326. b->left=a; //Rotacja
  327. b->right=c;
  328. c->left=T2;
  329. cout<<"\nLL";
  330. return;
  331. }
  332.  
  333. void LR(vector < Node* > stack,int imb){ //Rotacja lewo ... prawo
  334. Node *c=stack[imb];
  335. Node *a=c->left;
  336. Node *b=a->right;
  337. Node *T0=a->left;
  338. Node *T1=b->left;
  339. Node *T2=b->right;
  340. Node *T3=c->right;
  341. a->h=Nmax(T0,T1)+1;
  342. c->h=Nmax(T2,T3)+1; //Te wysokosci sie zmienia
  343. b->h=Nmax(a,c)+1;
  344. if(this->root==c) //c jest rootem, trzeba ustawic nowy
  345. this->root=b;
  346. else //c nie jest rootem
  347. if(stack[imb] == stack[imb-1]->left)
  348. stack[imb-1]->left=b;
  349. else
  350. stack[imb-1]->right=b;
  351. b->left=a; //Rotacja
  352. b->right=c;
  353. a->right=T1;
  354. c->left=T2;
  355. cout<<"\nLR";
  356. return;
  357. }
  358.  
  359. void RL(vector < Node* > stack,int imb){ //Rotacja prawo ... lewo
  360. Node *a=stack[imb];
  361. Node *c=a->right;
  362. Node *b=c->left;
  363. Node *T0=a->left;
  364. Node *T1=b->left;
  365. Node *T2=b->right;
  366. Node *T3=c->right;
  367. a->h=Nmax(T0,T1)+1;
  368. c->h=Nmax(T2,T3)+1; //Te wysokosci sie zmienia
  369. b->h=Nmax(a,c)+1;
  370. if(this->root==a) //a jest rootem, trzeba ustawic nowy
  371. this->root=b;
  372. else //a nie jest rootem
  373. if(stack[imb] == stack[imb-1]->left)
  374. stack[imb-1]->left=b;
  375. else
  376. stack[imb-1]->right=b;
  377. b->left=a; //Rotacja
  378. b->right=c;
  379. a->right=T1;
  380. c->left=T2;
  381. cout<<"\nRL";
  382. return;
  383. }
  384.  
  385. void RR(vector < Node* > stack,int imb){ //Rotacja prawo ... prawo
  386. Node *a=stack[imb];
  387. Node *b=a->right;
  388. Node *c=b->right;
  389. Node *T0=a->left;
  390. Node *T1=b->left;
  391. Node *T2=c->left;
  392. Node *T3=c->right;
  393. a->h=Nmax(T0,T1)+1;
  394. c->h=Nmax(T2,T3)+1; //Te wysokosci sie zmienia
  395. b->h=Nmax(a,c)+1;
  396. if(this->root==a) //a jest rootem, trzeba ustawic nowy
  397. this->root=b;
  398. else //a nie jest rootem
  399. if(stack[imb] == stack[imb-1]->left)
  400. stack[imb-1]->left=b;
  401. else
  402. stack[imb-1]->right=b;
  403. b->left=a; //Rotacja
  404. b->right=c;
  405. a->right=T1;
  406. cout<<"\nRR";
  407. return;
  408. }
  409.  
  410. void Delete_whole_rec(Node *it){
  411. if(it){
  412. if(it->left)
  413. Delete_whole_rec(it->left);
  414. if(it->right)
  415. Delete_whole_rec(it->right);
  416. delete it;
  417. }
  418. return;
  419. }
  420.  
  421. void DFS_preorder_rec(Node *it,int *n){
  422. if(it){
  423. *n+=1;
  424. cout<<endl<<it->key<<"\t"<<it->h;
  425. if(it->left){
  426. cout<<"\t<-";
  427. DFS_preorder_rec(it->left,n);
  428. }
  429. if(it->right){
  430. cout<<"\t->";
  431. DFS_preorder_rec(it->right,n);
  432. }
  433. }
  434. return;
  435. }
  436.  
  437. void DFS_inorder_rec(Node *it,int *n){
  438. if(it){
  439. if(it->left)
  440. DFS_inorder_rec(it->left,n);
  441. *n+=1;
  442. cout<<endl<<it->key;
  443. if(it->right)
  444. DFS_inorder_rec(it->right,n);
  445. }
  446. }
  447.  
  448. void DFS_postorder_rec(Node *it,int *n){
  449. if(it){
  450. if(it->left)
  451. DFS_inorder_rec(it->left,n);
  452. if(it->right)
  453. DFS_inorder_rec(it->right,n);
  454. *n+=1;
  455. cout<<endl<<it->key;
  456. }
  457. }
  458. };
  459.  
  460. int main(){
  461. Tree_BST *Tree=new Tree_BST();
  462.  
  463. Tree->Delete_whole();
  464.  
  465. Tree->Insert(0);
  466.  
  467. cout<<endl<<endl<<"Drzewko preorder:";
  468.  
  469. Tree->DFS_preorder();
  470.  
  471. Tree->Insert(-10);
  472.  
  473. cout<<endl<<endl<<"Drzewko preorder:";
  474.  
  475. Tree->DFS_preorder();
  476.  
  477. Tree->Insert(5);
  478.  
  479. cout<<endl<<endl<<"Drzewko preorder:";
  480.  
  481. Tree->DFS_preorder();
  482.  
  483. Tree->Insert(4);
  484.  
  485. cout<<endl<<endl<<"Drzewko preorder:";
  486.  
  487. Tree->DFS_preorder();
  488.  
  489. Tree->Insert(-6);
  490.  
  491. cout<<endl<<endl<<"Drzewko preorder:";
  492.  
  493. Tree->DFS_preorder();
  494.  
  495. Tree->Insert(1);
  496.  
  497. cout<<endl<<endl<<"Drzewko preorder:";
  498.  
  499. Tree->DFS_preorder();
  500.  
  501. Tree->Insert(2);
  502.  
  503. cout<<endl<<endl<<"Drzewko preorder:";
  504.  
  505. Tree->DFS_preorder();
  506.  
  507. Tree->Insert(-13);
  508.  
  509. cout<<endl<<endl<<"Drzewko preorder:";
  510.  
  511. Tree->DFS_preorder();
  512.  
  513. Tree->Insert(13);
  514.  
  515. cout<<endl<<endl<<"Drzewko preorder:";
  516.  
  517. Tree->DFS_preorder();
  518.  
  519. Tree->Insert(-7);
  520.  
  521. cout<<endl<<endl<<"Drzewko preorder:";
  522.  
  523. Tree->DFS_preorder();
  524.  
  525. Tree->Insert(65);
  526.  
  527. cout<<endl<<endl<<"Drzewko preorder:";
  528.  
  529. Tree->DFS_preorder();
  530.  
  531. Tree->Insert(8);
  532.  
  533. cout<<endl<<endl<<"Drzewko preorder:";
  534.  
  535. Tree->DFS_preorder();
  536.  
  537. Tree->Insert(-12);
  538.  
  539. cout<<endl<<endl<<"Drzewko preorder:";
  540.  
  541. Tree->DFS_preorder();
  542.  
  543. Tree->Insert(6);
  544.  
  545. cout<<"\nUsuwam cos...";
  546.  
  547. Tree->Delete(0);
  548.  
  549. cout<<endl<<endl<<"Drzewko preorder:";
  550.  
  551. Tree->DFS_preorder();
  552.  
  553. delete Tree;
  554.  
  555. getche();
  556. return 0;
  557. }
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!