Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- #define int long long
- #define TASKNAME "bstsimple"
- using namespace std;
- struct bts{
- struct Node {
- Node *l , *r ;
- int val;
- Node(int x) {
- l = nullptr;
- r = nullptr;
- val = x;
- }
- };
- Node *root = nullptr;
- bool exists(int x) {
- Node *cur = root;
- while (cur) {
- if (x > cur->val) {
- cur = cur->r;
- } else if (x < cur->val) {
- cur = cur->l;
- } else {
- return true;
- }
- }
- return false;
- }
- void push(int x) {
- if (root == nullptr) {
- root = new Node(x);
- return;
- }
- Node *cur = root;
- while (cur) {
- if (x > cur->val) {
- if (cur->r == nullptr) {
- cur->r = new Node(x);
- return;
- }
- cur = cur->r;
- } else if (x < cur->val) {
- if (cur->l == nullptr) {
- cur->l = new Node(x);
- return;
- }
- cur = cur->l;
- } else {
- return;
- }
- }
- return;
- }
- void rem(int x) {
- Node *to_delete = root;
- Node *parent = nullptr;
- bool left = false;
- while (to_delete) {
- if (x > to_delete->val) {
- parent = to_delete;
- left = false;
- to_delete = to_delete->r;
- } else if (x < to_delete->val) {
- parent = to_delete;
- left = true;
- to_delete = to_delete->l;
- } else {
- break;
- }
- }
- if (to_delete == nullptr || to_delete->val != x) return;
- if (to_delete->l != nullptr) {
- Node *r_node = to_delete->r;
- Node *temp = to_delete->l;
- while (temp->r != nullptr) {
- temp = temp->r;
- }
- temp->r = r_node;
- to_delete = to_delete->l;
- } else if (to_delete->l == nullptr) {
- to_delete = to_delete->r;
- }
- if (parent != nullptr) {
- if (left) {
- parent->l = to_delete;
- } else {
- parent->r = to_delete;
- }
- } else {
- root = to_delete;
- }
- }
- int next(int x) {
- if (root == nullptr) {
- return INT_MIN;
- }
- Node *cur = root;
- int ans = INT_MAX;
- while (cur) {
- if (x >= cur->val) {
- if (cur->r == nullptr) {
- return ans;
- }
- cur = cur->r;
- } else if (x < cur->val) {
- ans = cur->val;
- if (cur->l == nullptr) {
- return ans;
- }
- cur = cur->l;
- } else {
- return ans;
- }
- }
- return ans;
- }
- int prev(int x) {
- if (root == nullptr) {
- return INT_MIN;
- }
- Node *cur = root;
- int ans = INT_MIN;
- while (cur) {
- if (x > cur->val) {
- ans = cur->val;
- if (cur->r == nullptr) {
- return ans;
- }
- cur = cur->r;
- } else if (x <= cur->val) {
- if (cur->l == nullptr) {
- return ans;
- }
- cur = cur->l;
- } else {
- return ans;
- }
- }
- return ans;
- }
- };
- // #define DEV
- int32_t main() {
- #ifndef DEV
- freopen(TASKNAME".in", "r", stdin);
- freopen(TASKNAME".out", "w", stdout);
- #endif
- string s;
- bts kek;
- while (cin >> s) {
- if (s == "insert") {
- int x; cin >> x;
- kek.push(x);
- }
- if (s == "delete") {
- int x; cin >> x;
- kek.rem(x);
- }
- if (s == "exists") {
- int x;
- cin >> x;
- if (kek.exists(x)) {
- cout << "true" << endl;
- } else {
- cout << "false" << endl;
- }
- }
- if (s == "next") {
- int x;
- cin >> x;
- int ans = kek.next(x);
- if (ans == INT_MIN || ans == INT_MAX) {
- cout << "none\n";
- } else {
- cout << ans << endl;
- }
- }
- if (s == "prev") {
- int x;
- cin >> x;
- int ans = kek.prev(x);
- if (ans == INT_MIN || ans == INT_MAX) {
- cout << "none\n";
- } else {
- cout << ans << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement