API tools faq
paste
Guest User

Untitled

a guest
Jun 21st, 2018
73
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.59 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. #include<string>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct wezelek{string slowo;
  7. int wysokosc;
  8. struct wezelek *left,*right,*parent;}X;
  9.  
  10. class Wierzba{
  11. public:
  12. Wierzba(){a.root=NULL;}
  13.  
  14. int wyw2 (X* ble){
  15. if(!ble->left&&!ble->right)return 0;
  16. if(!ble->right)return 1;
  17. if(!ble->left)return -1;
  18. else return ble->left->wysokosc-ble->right->wysokosc;
  19.  
  20. }
  21. /////////ROT1LEFT
  22. void rot1l(X*dziecie,X*rodzic){
  23. X * gdzies,*gdziesindziej;
  24.  
  25. gdzies=dziecie->left;
  26. gdziesindziej=rodzic->parent;
  27.  
  28. dziecie->left=rodzic;
  29. rodzic->parent=dziecie;
  30. rodzic->right=gdzies;
  31. if(gdzies!=NULL)gdzies->parent=rodzic;
  32. dziecie->parent=gdziesindziej;
  33. if(gdziesindziej!=NULL) {
  34. if(gdziesindziej->right == rodzic)
  35. gdziesindziej->right=dziecie;
  36. else
  37. gdziesindziej->left=dziecie;
  38. }
  39.  
  40. if(a.root==rodzic)a.root=dziecie;
  41.  
  42.  
  43. rodzic->wysokosc=dziecie->wysokosc=0;
  44.  
  45.  
  46. }
  47.  
  48.  
  49.  
  50. /////////ROT1RIGHT
  51. void rot1p(X*dziecie,X*rodzic){
  52. X* gdzies,*gdziesindziej;
  53. gdzies=dziecie->right;
  54. gdziesindziej=rodzic->parent;
  55. dziecie->right=rodzic;
  56. rodzic->parent=dziecie;
  57. rodzic->left=gdzies;
  58. if(gdzies!=NULL){gdzies->parent=rodzic;}
  59. dziecie->parent=gdziesindziej;
  60. if(gdziesindziej!=NULL) {
  61. if(gdziesindziej->right == rodzic)
  62. gdziesindziej->right=dziecie;
  63. else
  64. gdziesindziej->left=dziecie;
  65. }
  66. if(a.root==rodzic)a.root=dziecie;
  67.  
  68. rodzic->wysokosc=dziecie->wysokosc=0;
  69.  
  70.  
  71.  
  72. }
  73.  
  74. ////////////ROT2LEFT
  75. void rot2l(X* rodzic,X*dziecie,X*senior){
  76. X *gdziesindziej,*gdziesleft,*gdziesright;
  77. int cos=dziecie->wysokosc;
  78.  
  79. gdziesindziej=senior->parent;
  80. gdziesleft=dziecie->left;
  81. gdziesright=dziecie->right;
  82.  
  83. dziecie->left=senior;
  84. senior->parent=dziecie;
  85. dziecie->right=rodzic;
  86. rodzic->parent=dziecie;
  87. rodzic->left=gdziesright;
  88. if(gdziesright!=NULL)gdziesright->parent=rodzic;
  89. senior->right=gdziesleft;
  90. if(gdziesleft!=NULL)gdziesleft->parent=senior;
  91. dziecie->parent=gdziesindziej;
  92. if(gdziesindziej!=NULL) {
  93. if(gdziesindziej->right == senior)
  94. gdziesindziej->right=dziecie;
  95. else
  96. gdziesindziej->left=dziecie;
  97. }
  98. if (a.root==senior) a.root=dziecie;
  99.  
  100.  
  101. if(dziecie->wysokosc==0){rodzic->wysokosc=0;senior->wysokosc=0;}
  102. else if(dziecie->wysokosc==-1){rodzic->wysokosc=0;senior->wysokosc=1;}
  103. else {rodzic->wysokosc=-1;senior->wysokosc=0;}
  104. dziecie->wysokosc=0;
  105.  
  106. }
  107.  
  108.  
  109. ///////////ROT2RIGHT
  110. void rot2p(X* rodzic,X*dziecie,X*senior){
  111. X *gdziesindziej,*gdziesleft,*gdziesright;
  112. gdziesindziej=senior->parent;
  113. gdziesleft=dziecie->left;
  114. gdziesright=dziecie->right;
  115.  
  116. dziecie->left=rodzic;
  117. rodzic->parent=dziecie;
  118. dziecie->right=senior;
  119. senior->parent=dziecie;
  120. rodzic->right=gdziesleft;
  121. if(gdziesleft!=NULL)gdziesleft->parent=rodzic;
  122. senior->left=gdziesright;
  123. if(gdziesright!=NULL)gdziesright->parent=senior;
  124. dziecie->parent=gdziesindziej;
  125. if(gdziesindziej!=NULL) {
  126. if(gdziesindziej->right == senior)
  127. gdziesindziej->right=dziecie;
  128. else
  129. gdziesindziej->left=dziecie;
  130. }
  131. if (a.root==senior) a.root=dziecie;
  132.  
  133.  
  134.  
  135. if(dziecie->wysokosc==0){rodzic->wysokosc=0;senior->wysokosc=0;}
  136. else if(dziecie->wysokosc==-1){rodzic->wysokosc=1;senior->wysokosc=0;}
  137. else {rodzic->wysokosc=0;senior->wysokosc=-1;}
  138. dziecie->wysokosc=0;
  139.  
  140. }
  141.  
  142.  
  143. //////DODAWNIE
  144. void dodajble(string dodawany,X*nowy){
  145. if (szukaj(dodawany)){}
  146. else {
  147. dodaj(dodawany,nowy);
  148. if(nowy==a.root){
  149. szukaj(dodawany);
  150. X*tmp=aktualny;
  151. do {
  152. if(tmp->parent==NULL)
  153. break;
  154. if(tmp->parent->left!=NULL && tmp->parent->left->slowo==tmp->slowo){
  155. tmp=tmp->parent;
  156. tmp->wysokosc++;
  157. if (tmp->wysokosc==0) {
  158. break;
  159. }
  160. else if(tmp->wysokosc==2&&tmp->left->wysokosc==1){
  161. rot1p(tmp->left,tmp);
  162. break;
  163. }
  164. else {
  165. if(tmp->wysokosc==2&&tmp->left!=NULL&&tmp->left->wysokosc==-1){
  166. rot2p(tmp->left,tmp->left->right,tmp);
  167. break;
  168. }
  169. }
  170. }
  171. else if(tmp->parent->right->slowo==tmp->slowo){
  172. tmp=tmp->parent;
  173. tmp->wysokosc--;
  174.  
  175. if(tmp->wysokosc==0){
  176. break;
  177. }
  178. else if (tmp->wysokosc==-2&&tmp->right->wysokosc==-1){
  179. rot1l(tmp->right,tmp);break;
  180. }
  181. else {
  182. if(tmp->wysokosc==-2&&tmp->right!=NULL&&tmp->right->wysokosc==1){
  183. rot2l(tmp->right,tmp->right->left,tmp);
  184. break;
  185. }
  186. }
  187. }
  188. }
  189. while(tmp->parent!=NULL);
  190. }
  191. }
  192.  
  193.  
  194. }
  195.  
  196. //trzeba wywolac z korzeniem
  197. void dodaj(string dodawany,X *nowy){
  198. if (a.root==NULL){
  199. nowy=new X;
  200. nowy->slowo=dodawany;
  201. nowy->left=NULL;
  202. nowy->right=NULL;
  203. nowy->wysokosc=0;
  204. a.root=nowy;
  205. (a.root)->left=(a.root)->right=(a.root)->parent=NULL;
  206. }
  207. else{
  208. if(nowy==NULL){
  209. nowy=new X;
  210. nowy->slowo=dodawany;
  211. nowy->left=NULL;
  212. nowy->right=NULL;
  213. nowy->wysokosc=0;
  214. nowy->parent=aktualny;
  215. if(aktualny!=NULL){
  216. if(aktualny->slowo>nowy->slowo) aktualny->left=nowy;
  217. else aktualny->right=nowy;
  218. }
  219. }
  220. else{
  221. if(dodawany<nowy->slowo){
  222. dodaj(dodawany,nowy->left);
  223. }
  224. else {
  225. dodaj(dodawany,nowy->right);
  226.  
  227. }
  228. }
  229.  
  230. }
  231. }
  232.  
  233. //////////////USUNBLE
  234. void usunble(string usuwany,X* stary){
  235. if(!szukaj(usuwany)){}
  236. else{X* tmp=aktualny,*potem;
  237.  
  238.  
  239. potem=usun(a.root,tmp);
  240. // potem->parent=potem->right=potem->left=NULL;
  241. potem=NULL;
  242. delete potem;
  243. }
  244.  
  245.  
  246. }
  247.  
  248. /////USUWANIE
  249.  
  250. X * usun(X*korzen,X*stary){
  251. X*raz=stary->parent,*dwa;
  252. bool wywazac;
  253. if((stary->left)&&(stary->right))
  254. {
  255. wywazac=false;
  256. dwa=usun(korzen,pred(stary));
  257. dwa->left=stary->left;
  258. if(dwa->left) dwa->left->parent=dwa;
  259. dwa->right=stary->right;
  260. if(dwa->right) dwa->right->parent=dwa;
  261. dwa->wysokosc=wyw(dwa);
  262. }
  263. else {dwa=(stary->left)?stary->left:stary->right;
  264. wywazac=true;
  265. }
  266. if(dwa) dwa->parent=raz;
  267. if(!raz) {korzen=dwa;
  268. a.root=dwa;
  269. }
  270. else {if(raz->left==stary) raz->left=dwa;
  271. else raz->right=dwa;
  272. }
  273.  
  274.  
  275. X*pomo;
  276. if(wywazac){
  277. if(raz) raz->wysokosc = wyw(raz);
  278. raz = stary->parent;
  279.  
  280. while(raz){
  281.  
  282. if(raz->wysokosc == 1 || raz->wysokosc == -1) break;
  283. else if (raz->wysokosc == 0) {
  284. raz = raz->parent;
  285. if(raz) raz->wysokosc = wyw(raz);
  286. }
  287. else{
  288. //rotejszyns
  289. if(raz->wysokosc == 2){
  290. if(raz->left){
  291. if (raz->left->wysokosc == 1 || raz->left->wysokosc == 0) {
  292. rot1p(raz->left,raz);
  293. }
  294. else {
  295. rot2p(raz->left,raz->left->right,raz);
  296. }
  297. }
  298. }
  299. else {
  300. if (raz->wysokosc == -2){
  301. if (raz->right){
  302. if(raz->right->wysokosc == -1 || raz->right->wysokosc == 0) {
  303. rot1l(raz->right,raz);
  304. }
  305. else {
  306. rot2l(raz->right,raz->right->left,raz);
  307. }
  308. }
  309. }
  310. }
  311. raz = raz->parent;
  312. if(raz) raz->wysokosc=wyw(raz);
  313. }
  314. }
  315. }
  316. return stary;
  317. }
  318.  
  319. int wyw(X * dow){
  320. if (!dow->left&&!dow->right) return 0;
  321. if (dow->left==NULL)return dow->wysokosc-1;
  322. else if(dow->right==NULL) return dow->wysokosc+1;
  323. else return dow->left->wysokosc-dow->right->wysokosc;
  324. }
  325.  
  326. X * min(X *wezelek){
  327. X *x=wezelek;
  328. while(x->left) x=x->left;
  329. return x;
  330. }
  331.  
  332. X *succ(X *x){
  333. if(x->right) return min(x->right);
  334. X *y;
  335. do{y=x;
  336. x=x->parent;}while (x&&(x->left!=y));
  337. return x;
  338. }
  339. X * max(X *wezelek){
  340. X *x=wezelek;
  341. while(x->right) x=x->right;
  342. return x;
  343. }
  344.  
  345. X *pred(X *x){
  346. if(x->left) return max(x->left);
  347. X *y;
  348. do{y=x;
  349. x=x->parent;}while (x&&(x->right!=y));
  350. return x;
  351. }
  352.  
  353.  
  354. void przejdzin(X *wezelek, int d){
  355. if(a.root==NULL)cout<<"pusto";
  356. else {
  357. if(wezelek->left!=NULL) przejdzin(wezelek->left, d+1);
  358. for(int i = 0; i < d; ++i)
  359. cout << " ";
  360. cout<<wezelek->slowo<<" "<<wezelek->wysokosc<<endl;
  361. if (wezelek->right!=NULL) przejdzin(wezelek->right, d+1);
  362.  
  363. }
  364. }
  365.  
  366. bool szukaj(string szukany){
  367. X *wezelek=a.root;
  368. bool jest=false;
  369. while(wezelek!=NULL){
  370. if(wezelek->slowo==szukany) {jest=true;
  371. aktualny=wezelek;break;}
  372. else {
  373. if(wezelek->slowo<szukany) {aktualny=wezelek;wezelek=wezelek->right;}
  374. else {aktualny=wezelek;wezelek=wezelek->left;}
  375. }
  376. }
  377.  
  378. return jest;}
  379.  
  380. X* getroot(){return a.root;}
  381. X* getaktualny(){return aktualny;}
  382. private:
  383. X *aktualny;
  384. bool wywazac;
  385. typedef struct{X *root;}INFO;
  386. INFO a;
  387. };
  388.  
  389. int main(){
  390. Wierzba Avl;
  391.  
  392. string jakistam;
  393. int wybor=0;
  394. while(wybor!=4){
  395. cin>>wybor;
  396. switch(wybor){
  397. case 1:{
  398. cin>>jakistam;
  399. Avl.dodajble(jakistam,Avl.getroot());
  400. break;}
  401. case 2:{
  402. cin>>jakistam;
  403. if(Avl.szukaj(jakistam)) cout<<"SI"<<endl;else cout<<"NO"<<endl;
  404. break;}
  405. case 3:{
  406. cin>>jakistam;
  407. Avl.usunble(jakistam,Avl.getroot());
  408. break;}
  409. case 5: {Avl.przejdzin(Avl.getroot(), 0);
  410. cout << endl;
  411. break;}
  412. }
  413.  
  414. }
  415. return 0;}
Add Comment
Please, Sign In to add comment
Public Pastes
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!