İkili axtarış ağacı 2#4147

İkili axtarış ağacı 2 (Həll təhlili)

Solution

General Idea: We need to implement a balanced Binary Search Tree that supports the following operations efficiently:

insert x — insert value (x)
delete x — delete value (x)
exists x — check if (x) exists
next x — find the smallest value strictly greater than (x)
prev x — find the largest value strictly smaller than (x)
kth k — find the k-th smallest element

To achieve all operations in (O(n)), we use a **balanced tree with order statistics**.

We utilize:

A policy-based data structure (ordered_set) to support:
- Finding k-th element
- Finding rank of elements
A standard set to efficiently support:
- exists
- next
- prev

This guarantees all operations work efficiently within constraints.

—

Operations Handling

insert x: Insert into both trees.
delete x: Remove from both trees if it exists.
exists x: Check existence using set.
next x: Use upper_bound.
prev x: Use lower_bound and move iterator back.
kth k: Use find_by_order(k-1) from ordered tree.

—

Time Complexity

All operations work in:

[ O(n) ]

which is fast enough for (10^5) operations.

—

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
                  tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Tree<int> t;
    set<int> st;

    string s;
    int x;

    while (cin >> s >> x) {
        if (s == "insert") {
            t.insert(x);
            st.insert(x);
        }
        else if (s == "delete") {
            if (st.find(x) != st.end()) {
                t.erase(x);
                st.erase(x);
            }
        }
        else if (s == "exists") {
            if (st.find(x) != st.end())
                cout << "true\n";
            else
                cout << "false\n";
        }
        else if (s == "next") {
            auto it = st.upper_bound(x);
            if (it == st.end())
                cout << "none\n";
            else
                cout << *it << "\n";
        }
        else if (s == "prev") {
            auto it = st.lower_bound(x);
            if (it == st.begin())
                cout << "none\n";
            else {
                --it;
                cout << *it << "\n";
            }
        }
        else if (s == "kth") {
            int sz = t.size();
            if (x > sz)
                cout << "none\n";
            else {
                auto it = t.find_by_order(x - 1);
                cout << *it << "\n";
            }
        }
    }

    return 0;
}