Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<string>
- typedef long long ll;
- using namespace std;
- const ll negativeINF = -0xFFFFFFFFF;
- const ll INF = 0xFFFFFFFFF;
- class BST {
- struct node {
- ll data;
- node* left;
- node* right;
- node(ll val) {
- data = val;
- left = right = NULL;
- }
- };
- node* insert(ll x, node* t)
- {
- if (t == NULL)
- {
- t = new node(0);
- t->data = x;
- t->left = t->right = NULL;
- }
- else if (x < t->data)
- t->left = insert(x, t->left);
- else if (x > t->data)
- t->right = insert(x, t->right);
- return t;
- }
- node* findMin(node* t)
- {
- if (t == NULL)
- return NULL;
- else if (t->left == NULL)
- return t;
- else
- return findMin(t->left);
- }
- node* findMax(node* t) {
- if (t == NULL)
- return NULL;
- else if (t->right == NULL)
- return t;
- else
- return findMax(t->right);
- }
- node* remove(ll x, node* t) {
- node* temp;
- if (t == NULL)
- return NULL;
- else if (x < t->data)
- t->left = remove(x, t->left);
- else if (x > t->data)
- t->right = remove(x, t->right);
- else if (t->left && t->right)
- {
- temp = findMin(t->right);
- t->data = temp->data;
- t->right = remove(t->data, t->right);
- }
- else
- {
- temp = t;
- if (t->left == NULL)
- t = t->right;
- else if (t->right == NULL)
- t = t->left;
- delete temp;
- }
- return t;
- }
- public:
- node* root;
- node* newNode(ll data);
- vector <ll> arr;
- void inorder(node* node) {
- if (!node || node == NULL) return;
- inorder(node->left);
- arr.push_back(node->data);
- inorder(node->right);
- }
- node* construct(ll low, ll high) {
- if (low > high) return NULL;
- ll mid = low + (high - low) / 2;
- node* root = new node(arr[mid]);
- root->left = construct(low, mid - 1);
- root->right = construct(mid + 1, high);
- return root;
- }
- node* balanceBST(node* root) {
- inorder(root);
- return construct(0, (ll)arr.size() - 1);
- }
- BST() {
- root = NULL;
- }
- void insert(ll x) {
- root = insert(x, root);
- }
- void remove(ll x) {
- root = remove(x, root);
- }
- node* sortedArrayToBST(vector<ll>arr,
- ll start, ll end)
- {
- if (start > end)
- return NULL;
- ll mid = (start + end) / 2;
- node* root = new node(arr[mid]);
- root->left = sortedArrayToBST(arr, start,
- mid - 1);
- root->right = sortedArrayToBST(arr, mid + 1, end);
- return root;
- }
- void preOrder(node* node, vector<ll>& new_tree)
- {
- if (node == NULL)
- return;
- new_tree.push_back(node->data);
- preOrder(node->left, new_tree);
- preOrder(node->right, new_tree);
- }
- void next(ll& ans, node* t, ll x, bool metka, bool& metka2, ll previous = INF) {
- if (t == NULL && t != root) {
- if (x < previous && previous != INF) {
- if (previous == 0)
- metka2 = 1;
- ans = previous;
- }
- else
- ans = 0;
- }
- else if (t == NULL) {
- ans = 0;
- }
- else {
- if (t->data > x) {
- if (t->data > previous) {
- next(ans, t->left, x, metka, metka2, previous);
- }
- else
- next(ans, t->left, x, metka, metka2, t->data);
- }
- else {
- if (previous > t->data && metka && t->data > x) {
- metka = false;
- next(ans, t->right, x, metka, metka2, t->data);
- }
- else
- next(ans, t->right, x, metka, metka2, previous);
- }
- }
- }
- void prev(ll &ans, node* t, ll x, bool metka,bool& metka2, ll previous = negativeINF) {
- if (t == NULL && t != root) {
- if (x > previous && previous != negativeINF) {
- if (previous == 0)
- metka2 = 1;
- ans = previous;
- }
- else
- ans = 0;
- }
- else if (t == NULL) {
- ans = 0;
- }
- else {
- if (t->data < x) {
- if (previous < t->data) {
- prev(ans, t->right, x, metka, metka2, t->data);
- }
- else
- prev(ans, t->right, x, metka, metka2, previous);
- }
- else {
- if (previous > t->data) {
- prev(ans, t->left, x, metka, metka2, t->data);
- }
- else
- prev(ans, t->left, x, metka, metka2, previous);
- }
- }
- }
- BST Balance_Tree(vector<ll>& new_arr) {
- BST t;
- for (ll i : new_arr) {
- t.insert(i);
- }
- return t;
- }
- node* find(node* t, ll x) {
- if (t == NULL)
- return NULL;
- else if (x < t->data)
- return find(t->left, x);
- else if (x > t->data)
- return find(t->right, x);
- else
- return t;
- }
- void search(ll x) {
- root = find(root, x);
- }
- };
- int main() {
- BST t;
- string q = "";
- ll x;
- bool is_edit = 0;
- while (cin >> q >> x) {
- if (q == "insert") {
- t.insert(x);
- is_edit = 1;
- }
- else if (q == "exists") {
- if (t.find(t.root, x) == NULL) {
- cout << "false\n";
- }
- else {
- cout << "true\n";
- }
- }
- else if (q == "delete") {
- t.remove(x);
- is_edit = 1;
- }
- else if (q == "next") {
- if (is_edit) {
- vector<ll>new_tree;
- t.preOrder(t.balanceBST(t.root), new_tree);
- t = t.Balance_Tree(new_tree);
- }
- bool is_null = 0;
- is_edit = 0;
- ll ans = 0;
- t.next(ans, t.root, x, true, is_null);
- if (is_null) {
- cout << 0 << "\n";
- }
- else if(ans != 0) {
- cout << ans << '\n';
- }
- else {
- cout << "none" << '\n';
- }
- }
- else if (q == "prev") {
- if (is_edit) {
- vector<ll>new_tree;
- t.preOrder(t.root, new_tree);
- t = t.Balance_Tree(new_tree);
- }
- bool is_null = 0;
- is_edit = 0;
- ll ans = 0;
- t.prev(ans, t.root, x, true, is_null);
- if (is_null) {
- cout << 0 << "\n";
- }
- else if (ans != 0) {
- cout << ans << '\n';
- }
- else {
- cout << "none" << '\n';
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement