data_structure/binary_search_tree.hpp

• View this file on GitHub
• Last update: 2024-06-25 02:44:34+09:00
• Include: #include "data_structure/binary_search_tree.hpp"

Verified with

• verify/yosupo/yosupo_double_ended_priority_queue.test.cpp

Code

template<class T=int>
struct BinarySearchTree{
    struct Node{
        T val;
        Node* l = nullptr;
        Node* r = nullptr;
        Node* p = nullptr;
        Node(T x) : val(x) {}
    };

    Node* root = nullptr;

    Node* find(T x) {
        Node* cur = root;
        while(cur) {
            if(cur->val == x) return cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        return cur;
    }

    void insert(T x) {
        Node* new_node = new Node(x);
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        if(!pre) root = new_node;
        else if(pre->val < x) pre->r = new_node;
        else pre->l = new_node;
        new_node->p = pre;
    }

    bool erase(T x) {
        Node* del = find(x);
        if(!del) return false;
        if(!del->l) transplant(del, del->r);
        else if(!del->r) transplant(del, del->l);
        else {
            Node* nxt = del->r;
            while(nxt->l) nxt = nxt->l;
            if(del->r != nxt) {
                transplant(nxt, nxt->r);    
                nxt->r = del->r;
                nxt->r->p = nxt;
            }
            transplant(del, nxt);
            nxt->l = del->l;
            nxt->l->p = nxt;
        }
        delete del;
        return true;
    }

    void transplant(Node* u, Node* v) {
        if(u == root) root = v;
        else if(u == u->p->l) u->p->l = v;
        else u->p->r = v;
        if(v) v->p = u->p;
    }

    T minimum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->l;
        }
        if(!pre) return -1;
        return pre->val;
    }

    T maximum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->r;
        }
        if(!pre) return -1;
        return pre->val;
    }
};

#line 1 "data_structure/binary_search_tree.hpp"
template<class T=int>
struct BinarySearchTree{
    struct Node{
        T val;
        Node* l = nullptr;
        Node* r = nullptr;
        Node* p = nullptr;
        Node(T x) : val(x) {}
    };

    Node* root = nullptr;

    Node* find(T x) {
        Node* cur = root;
        while(cur) {
            if(cur->val == x) return cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        return cur;
    }

    void insert(T x) {
        Node* new_node = new Node(x);
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            if(cur->val < x) cur = cur->r;
            else cur = cur->l;
        }
        if(!pre) root = new_node;
        else if(pre->val < x) pre->r = new_node;
        else pre->l = new_node;
        new_node->p = pre;
    }

    bool erase(T x) {
        Node* del = find(x);
        if(!del) return false;
        if(!del->l) transplant(del, del->r);
        else if(!del->r) transplant(del, del->l);
        else {
            Node* nxt = del->r;
            while(nxt->l) nxt = nxt->l;
            if(del->r != nxt) {
                transplant(nxt, nxt->r);    
                nxt->r = del->r;
                nxt->r->p = nxt;
            }
            transplant(del, nxt);
            nxt->l = del->l;
            nxt->l->p = nxt;
        }
        delete del;
        return true;
    }

    void transplant(Node* u, Node* v) {
        if(u == root) root = v;
        else if(u == u->p->l) u->p->l = v;
        else u->p->r = v;
        if(v) v->p = u->p;
    }

    T minimum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->l;
        }
        if(!pre) return -1;
        return pre->val;
    }

    T maximum() {
        Node* cur = root;
        Node* pre = nullptr;
        while(cur) {
            pre = cur;
            cur = cur->r;
        }
        if(!pre) return -1;
        return pre->val;
    }
};

Back to top page