Guest User

Untitled

a guest
Dec 8th, 2019
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define TASKNAME "bstsimple"
  5. using namespace std;
  6.  
  7.  
  8.  
  9. struct bts{
  10. struct Node {
  11. Node *l , *r ;
  12. int val;
  13. Node(int x) {
  14. l = nullptr;
  15. r = nullptr;
  16. val = x;
  17. }
  18. };
  19.  
  20. Node *root = nullptr;
  21.  
  22. bool exists(int x) {
  23. Node *cur = root;
  24. while (cur) {
  25. if (x > cur->val) {
  26. cur = cur->r;
  27. } else if (x < cur->val) {
  28. cur = cur->l;
  29. } else {
  30. return true;
  31. }
  32. }
  33. return false;
  34. }
  35.  
  36.  
  37. void push(int x) {
  38. if (root == nullptr) {
  39. root = new Node(x);
  40. return;
  41. }
  42. Node *cur = root;
  43. while (cur) {
  44. if (x > cur->val) {
  45. if (cur->r == nullptr) {
  46. cur->r = new Node(x);
  47. return;
  48. }
  49. cur = cur->r;
  50. } else if (x < cur->val) {
  51. if (cur->l == nullptr) {
  52. cur->l = new Node(x);
  53. return;
  54. }
  55. cur = cur->l;
  56. } else {
  57. return;
  58. }
  59. }
  60. return;
  61. }
  62.  
  63.  
  64. void rem(int x) {
  65. Node *to_delete = root;
  66. Node *parent = nullptr;
  67. bool left = false;
  68. while (to_delete) {
  69. if (x > to_delete->val) {
  70. parent = to_delete;
  71. left = false;
  72. to_delete = to_delete->r;
  73. } else if (x < to_delete->val) {
  74. parent = to_delete;
  75. left = true;
  76. to_delete = to_delete->l;
  77. } else {
  78. break;
  79. }
  80. }
  81. if (to_delete == nullptr || to_delete->val != x) return;
  82. if (to_delete->l != nullptr) {
  83. Node *r_node = to_delete->r;
  84. Node *temp = to_delete->l;
  85. while (temp->r != nullptr) {
  86. temp = temp->r;
  87. }
  88. temp->r = r_node;
  89. to_delete = to_delete->l;
  90. } else if (to_delete->l == nullptr) {
  91. to_delete = to_delete->r;
  92. }
  93. if (parent != nullptr) {
  94. if (left) {
  95. parent->l = to_delete;
  96. } else {
  97. parent->r = to_delete;
  98. }
  99. } else {
  100. root = to_delete;
  101. }
  102. }
  103.  
  104. int next(int x) {
  105. if (root == nullptr) {
  106. return INT_MIN;
  107. }
  108. Node *cur = root;
  109. int ans = INT_MAX;
  110. while (cur) {
  111. if (x >= cur->val) {
  112. if (cur->r == nullptr) {
  113. return ans;
  114. }
  115. cur = cur->r;
  116. } else if (x < cur->val) {
  117. ans = cur->val;
  118. if (cur->l == nullptr) {
  119. return ans;
  120. }
  121. cur = cur->l;
  122. } else {
  123. return ans;
  124. }
  125. }
  126. return ans;
  127. }
  128.  
  129. int prev(int x) {
  130. if (root == nullptr) {
  131. return INT_MIN;
  132. }
  133. Node *cur = root;
  134. int ans = INT_MIN;
  135. while (cur) {
  136. if (x > cur->val) {
  137. ans = cur->val;
  138. if (cur->r == nullptr) {
  139. return ans;
  140. }
  141. cur = cur->r;
  142. } else if (x <= cur->val) {
  143. if (cur->l == nullptr) {
  144. return ans;
  145. }
  146. cur = cur->l;
  147. } else {
  148. return ans;
  149. }
  150. }
  151. return ans;
  152. }
  153. };
  154.  
  155.  
  156. // #define DEV
  157. int32_t main() {
  158. #ifndef DEV
  159. freopen(TASKNAME".in", "r", stdin);
  160. freopen(TASKNAME".out", "w", stdout);
  161. #endif
  162. string s;
  163. bts kek;
  164. while (cin >> s) {
  165. if (s == "insert") {
  166. int x; cin >> x;
  167. kek.push(x);
  168. }
  169. if (s == "delete") {
  170. int x; cin >> x;
  171. kek.rem(x);
  172. }
  173. if (s == "exists") {
  174. int x;
  175. cin >> x;
  176. if (kek.exists(x)) {
  177. cout << "true" << endl;
  178. } else {
  179. cout << "false" << endl;
  180. }
  181. }
  182. if (s == "next") {
  183. int x;
  184. cin >> x;
  185. int ans = kek.next(x);
  186. if (ans == INT_MIN || ans == INT_MAX) {
  187. cout << "none\n";
  188. } else {
  189. cout << ans << endl;
  190. }
  191. }
  192. if (s == "prev") {
  193. int x;
  194. cin >> x;
  195. int ans = kek.prev(x);
  196. if (ans == INT_MIN || ans == INT_MAX) {
  197. cout << "none\n";
  198. } else {
  199. cout << ans << endl;
  200. }
  201. }
  202.  
  203. }
RAW Paste Data