Guest User

Untitled

a guest
Feb 19th, 2020
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #define INPUT_FILE "input.txt"
  5. #define OUTPUT_FILE "output.txt"
  6.  
  7. using namespace std;
  8.  
  9. fstream infile, outfile;
  10.  
  11. template <class H>
  12. struct Nodo
  13. {
  14. H val;
  15. Nodo<H>* padre;
  16. Nodo<H>* sinistro;
  17. Nodo<H>* destro;
  18. };
  19.  
  20. template <class H>
  21. class BST
  22. {
  23. private:
  24. Nodo<H>* radice;
  25. public:
  26. BST() : radice(NULL) {}
  27. void insert(H valore);
  28. void trapianta(Nodo<H>* u, Nodo<H>* v);
  29. Nodo<H>* find(H x);
  30. void cancella(Nodo<H>* z);
  31. Nodo<H>* minimo(Nodo<H>* x);
  32. Nodo<H>* _succ(Nodo<H>* aux);
  33. H succ(H valore);
  34. };
  35.  
  36. template <class H>
  37. void BST<H>::insert(H valore)
  38. {
  39. Nodo<H>* nuovo = new Nodo<H>;
  40. Nodo<H>* x = radice, *y = NULL;
  41. nuovo -> val = valore;
  42. nuovo -> sinistro = nuovo -> destro = NULL;
  43. while (x!=NULL)
  44. {
  45. y = x;
  46. if (valore < x->val)
  47. x = x->sinistro;
  48. else
  49. x = x->destro;
  50. }
  51.  
  52. nuovo -> padre = y;
  53. if (y==NULL)
  54. radice = nuovo;
  55. else if (valore < y->val)
  56. y -> sinistro = nuovo;
  57. else
  58. y -> destro = nuovo;
  59. }
  60.  
  61. template <class H>
  62. void BST<H>::trapianta(Nodo<H>* u, Nodo<H>* v)
  63. {
  64. if (u->padre==NULL)
  65. radice = v;
  66. else if (u==u->padre->sinistro)
  67. u->padre->sinistro = v;
  68. else
  69. u-> padre -> destro = v;
  70. if (v!=NULL)
  71. v->padre = u->padre;
  72. }
  73.  
  74. template <class H>
  75. Nodo<H>* BST<H>::minimo(Nodo<H>* x)
  76. {
  77. Nodo<H>* min = x;
  78. while (min->sinistro != NULL)
  79. min = min->sinistro;
  80. return min;
  81. }
  82.  
  83. template <class H>
  84. void BST<H>::cancella(Nodo<H>* z)
  85. {
  86. Nodo<H>* y;
  87. if (z->sinistro == NULL)
  88. trapianta(z, z->destro);
  89. else if (z->destro == NULL)
  90. trapianta(z, z->sinistro);
  91. else
  92. {
  93. y = minimo(z->destro);
  94. if (y->padre!=z)
  95. {
  96. trapianta(y, y->destro);
  97. y->destro = z->destro;
  98. y->destro->padre = y;
  99. }
  100. trapianta(z, y);
  101. y->sinistro = z->sinistro;
  102. y->sinistro->padre = y;
  103. }
  104. delete z;
  105. }
  106.  
  107. template <class H>
  108. Nodo<H>* BST<H>::find(H x)
  109. {
  110. Nodo<H>* iter = radice;
  111. while ((iter!=NULL)&&(x!=iter->val))
  112. {
  113. if (x<iter->val)
  114. iter = iter->sinistro;
  115. else
  116. iter = iter -> destro;
  117. }
  118. return iter;
  119. }
  120.  
  121. template <class H>
  122. Nodo<H>* BST<H>::_succ(Nodo<H>* aux)
  123. {
  124. if (aux==0)
  125. return 0;
  126. if (aux->destro)
  127. return minimo(aux->destro);
  128. }
  129.  
  130. template <class H>
  131. H BST<H>::succ(H val)
  132. {
  133. Nodo<H>* aux = _succ(find(val));
  134. if (aux)
  135. return aux->val;
  136. else
  137. return -1;
  138. }
  139.  
  140. int getDuePunti(string x)
  141. {
  142. for (int i=0; i<x.length(); i++)
  143. if (x[i]==':')
  144. return i;
  145. return 0;
  146. }
  147.  
  148. string getOp(string x)
  149. {
  150. return x.substr(0, getDuePunti(x));
  151. }
  152.  
  153. string _getValore(string x)
  154. {
  155. return x.substr(getDuePunti(x)+1, x.length());
  156. }
  157.  
  158. int main()
  159. {
  160. infile.open(INPUT_FILE, fstream::in);
  161. outfile.open(OUTPUT_FILE, fstream::out);
  162. for (int k=0; k<100; k++)
  163. {
  164. string tipo;
  165. int N, M;
  166. infile >> tipo >> N >> M;
  167. if (tipo=="int")
  168. {
  169. BST<int> tree;
  170. for (int j=0; j<N; j++)
  171. {
  172. string tmp, _valore, op;
  173. int x;
  174. infile >> tmp;
  175. op = getOp(tmp);
  176. _valore = _getValore(tmp);
  177. x = stoi(_valore);
  178.  
  179. if (op=="ins")
  180. tree.insert(x);
  181. else
  182. {
  183. Nodo<int>* elem = tree.find(x);
  184. tree.cancella(elem);
  185. }
  186. }
  187. for (int j=0; j<M; j++)
  188. {
  189. int chiave;
  190. infile >> chiave;
  191. int successore = tree.succ(chiave);
  192. outfile << successore << " ";
  193. }
  194. }
  195. else
  196. {
  197. BST<double> tree;
  198. for (int j=0; j<N; j++)
  199. {
  200. string tmp, _valore, op;
  201. double x;
  202. infile >> tmp;
  203. op = getOp(tmp);
  204. _valore = _getValore(tmp);
  205. x = stod(_valore);
  206.  
  207. if (op=="ins")
  208. tree.insert(x);
  209. else
  210. {
  211. Nodo<double>* elem = tree.find(x);
  212. tree.cancella(elem);
  213. }
  214. }
  215. for (int j=0; j<M; j++)
  216. {
  217. int chiave;
  218. infile >> chiave;
  219. int successore = tree.succ(chiave);
  220. outfile << successore << " ";
  221. }
  222. }
  223. outfile << endl;
  224. }
  225. cout << "end of program, exit" << endl;
  226. infile.close();
  227. outfile.close();
  228. }
RAW Paste Data