AVL tree

7785번: 회사에 있는 사람

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define Elem string
 
using namespace std;
 
class Node
{
private:
    Node *parent, *left, *right;
    Elem elem;
    int height;
    bool height_update();
    int left_height() { return ((left == nullptr)? -1: left->height); }
    int right_height() { return ((right == nullptr)? -1: right->height); }
    bool unbalance() { return abs(left_height() - right_height()) >= 2; }
 
public:
    Node() = delete;
    Node(Elem elem) : elem{elem}, height{0} { parent = left = right = nullptr; }
    ~Node() = default; 
    friend class AVL_tree;
};
 
class AVL_tree
{
private:
    Node* root;
    int n; // size
    void release(Node* node);
    void link(Node* u, Node* v);
    Node* tree_minimum(Node* node);
    Node* restructure(Node* node); // return z->parent
    void rotate_right(Node* p, Node* c);
    void rotate_left(Node* p , Node* c);
    void print(Node* node) const;
 
public:
    AVL_tree() : root{nullptr}, n{0} {}
    ~AVL_tree() { if(root != nullptr) release(root); }
    Node* find(Elem elem);
    bool empty() const { return n == 0; }
    int size() const { return n; }
    void insert(Elem elem);
    void erase(Elem elem);
    void print() const;
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int N; cin >> N;
    AVL_tree avl{};
    for(int i = 0; i < N; i++){
        Elem name;
        string flag;
        cin >> name >> flag;
        auto pos = avl.find(name);
        if(flag == "enter" && pos == nullptr) 
            avl.insert(name);
        else if(flag == "leave" && pos != nullptr) 
            avl.erase(name);
    }
 
     avl.print();
 
    return 0;
}
 
bool Node::height_update()
{
    int new_height = -1;
    if(left != nullptr) new_height = left->height;
    if(right != nullptr) new_height = max(new_height, right->height);
    if(height == new_height + 1) return false;
    else{
        height = new_height + 1;
        return true;
    }
}
 
void AVL_tree::release(Node* node)
{
    if(node->left != nullptr) release(node->left);
    if(node->right != nullptr) release(node->right);
    delete node; node = nullptr;
}
 
Node* AVL_tree::find(Elem elem)
{
    if(empty()) return nullptr;
 
    Node* cur = root;
    while(cur != nullptr){
        if(cur->elem == elem) return cur;
        cur = ((cur->elem <= elem)? cur->right: cur->left);
    }
 
    return nullptr;
}
 
void AVL_tree::link(Node* u, Node* v)
{
    if(u->parent == nullptr) root = v;
    else if(u->parent->left == u) u->parent->left = v;
    else u->parent->right = v;
 
    if(v != nullptr){
        v->parent = u->parent;
    }
}
 
Node* AVL_tree::tree_minimum(Node* node)
{
    while(node->left != nullptr) node = node->left;
    return node;
}
 
Node* AVL_tree::restructure(Node* node) // return z->parent
{
    Node* z = nullptr;
    while(node != nullptr){
        node->height_update();
        if(node->unbalance()) {
            z = node;
            break;
        }
        else node = node->parent;
    }
 
    if(z == nullptr) return nullptr;
    else{
        Node* y = ((z->left_height() < z->right_height())? z->right: z->left);
        Node* x = ((y->left_height() < y->right_height())? y->right: y->left);
 
        if(z->left == y && y->left == x) 
            rotate_right(z, y);
        else if(z->left == y && y->right == x){
            rotate_left(y, x);
            rotate_right(z, x);
        }
        else if(z->right == y && y->left == x){
            rotate_right(y, x);
            rotate_left(z, x);
        }
        else
            rotate_left(z, y);
 
        return z->parent;
    }
}
 
void AVL_tree::rotate_right(Node* p, Node* c)
{
    p->left = c->right;
    if(c->right != nullptr) c->right->parent = p;
 
    link(p, c);
 
    c->right = p;
    p->parent = c;
 
    while(p != nullptr && p->height_update())
        p = p->parent;
}
 
void AVL_tree::rotate_left(Node* p , Node* c)
{
    p->right = c->left;
    if(c->left != nullptr) c->left->parent = p;
 
    link(p, c);
 
    c->left = p;
    p->parent = c;
 
    while(p != nullptr && p->height_update())
        p = p->parent;
}
 
void AVL_tree::insert(Elem elem)
{
    Node* node = new Node{elem};
    if(empty()) root = node;
    else{
        Node *c = root, *p = nullptr;
        while(c != nullptr){
            p = c;
            c = ((c->elem <= elem)? c->right: c->left);
        }
 
        if(p->elem <= elem) p->right = node;
        else p->left = node;
 
        node->parent = p;
    }
    restructure(node);
 
    n += 1;
}
 
void AVL_tree::erase(Elem elem)
{
    Node* u = find(elem);
    if(u == nullptr) throw "erase non existing element";
 
    Node* restore = nullptr;
    if(u->left == nullptr) {
        link(u, u->right);
        if(u->right != nullptr) restore = u->right;
        else restore = u->parent; // restore == nullptr 이면 resturcture에서 아무것도 안함
    }
    else if(u->right == nullptr) {
        link(u, u->left);
        restore = u->left;
    }
    else{
        Node* v = tree_minimum(u->right);
        
        if(u->right == v){
            restore = v;
        }
        else{
            if(v->right != nullptr) restore = v->right;
            else restore = v->parent;
        }
 
        if(u->right != v){
            link(v, v->right);
            v->right = u->right;
            u->right->parent = v;
        }
        link(u, v);
        u->left->parent = v;
        v->left = u->left;
 
    }
 
    delete u; u = nullptr;
    while(restore != nullptr) {
        restore = restructure(restore);
    }
 
    n -= 1;
}
 
void AVL_tree::print(Node* node) const
{
    if(node->right != nullptr) print(node->right);
    cout << node->elem << endl;
    if(node->left != nullptr) print(node->left);
}
 
void AVL_tree::print() const
{
    if(!empty()) print(root);
}cs

 

7662번: 이중 우선순위 큐

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define Elem int
 
using namespace std;
 
class Node
{
private:
    Node *parent, *left, *right;
    Elem elem;
    int height;
    bool height_update();
    int left_height() { return ((left == nullptr)? -1: left->height); }
    int right_height() { return ((right == nullptr)? -1: right->height); }
    bool unbalance() { return abs(left_height() - right_height()) >= 2; }
 
public:
    Node() = delete;
    Node(Elem elem) : elem{elem}, height{0} { parent = left = right = nullptr; }
    ~Node() = default; 
    friend class AVL_tree;
};
 
class AVL_tree
{
private:
    Node* root;
    int n; // size
    void release(Node* node);
    void link(Node* u, Node* v);
    Node* tree_maximum(Node* node) const;
    Node* tree_minimum(Node* node) const;
    Node* restructure(Node* node); // return z->parent
    void rotate_right(Node* p, Node* c);
    void rotate_left(Node* p , Node* c);
 
public:
    AVL_tree() : root{nullptr}, n{0} {}
    ~AVL_tree() { if(root != nullptr) release(root); }
    Node* find(Elem elem);
    bool empty() const { return n == 0; }
    int size() const { return n; }
    void insert(Elem elem);
    void erase(Node* u);
    void erase_max();
    void erase_min();
    Elem tree_maximum() const;
    Elem tree_minimum() const;
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while(T--){
        AVL_tree avl{};
        int K; cin >> K;
        for(int i = 0; i < K; i++){
            char cmd;
            int tmp;
            cin >> cmd >> tmp;
            switch(cmd) {
            case 'I':
                avl.insert(tmp);
                break;
        
            case 'D':
                if(!avl.empty()){
                    if(tmp == 1)
                        avl.erase_max();
                    else 
                        avl.erase_min();
                }
            }
        }
 
        if(avl.empty()) cout << "EMPTY" << endl;
        else cout << avl.tree_maximum() << ' ' << avl.tree_minimum() << endl;
    }
 
    return 0;
}
 
bool Node::height_update()
{
    int new_height = -1;
    if(left != nullptr) new_height = left->height;
    if(right != nullptr) new_height = max(new_height, right->height);
    if(height == new_height + 1) return false;
    else{
        height = new_height + 1;
        return true;
    }
}
 
void AVL_tree::release(Node* node)
{
    if(node->left != nullptr) release(node->left);
    if(node->right != nullptr) release(node->right);
    delete node; node = nullptr;
}
 
Node* AVL_tree::find(Elem elem)
{
    if(empty()) return nullptr;
 
    Node* cur = root;
    while(cur != nullptr){
        if(cur->elem == elem) return cur;
        cur = ((cur->elem <= elem)? cur->right: cur->left);
    }
 
    return nullptr;
}
 
void AVL_tree::link(Node* u, Node* v)
{
    if(u->parent == nullptr) root = v;
    else if(u->parent->left == u) u->parent->left = v;
    else u->parent->right = v;
 
    if(v != nullptr){
        v->parent = u->parent;
    }
}
 
Node* AVL_tree::tree_maximum(Node* node) const
{
    while(node->right != nullptr) node = node->right;
    return node;
}
 
Node* AVL_tree::tree_minimum(Node* node) const
{
    while(node->left != nullptr) node = node->left;
    return node;
}
 
Node* AVL_tree::restructure(Node* node) // return z->parent
{
    Node* z = nullptr;
    while(node != nullptr){
        node->height_update();
        if(node->unbalance()) {
            z = node;
            break;
        }
        else node = node->parent;
    }
 
    if(z == nullptr) return nullptr;
    else{
        Node* y = ((z->left_height() < z->right_height())? z->right: z->left);
        Node* x = ((y->left_height() < y->right_height())? y->right: y->left);
 
        if(z->left == y && y->left == x) 
            rotate_right(z, y);
        else if(z->left == y && y->right == x){
            rotate_left(y, x);
            rotate_right(z, x);
        }
        else if(z->right == y && y->left == x){
            rotate_right(y, x);
            rotate_left(z, x);
        }
        else
            rotate_left(z, y);
 
        return z->parent;
    }
}
 
void AVL_tree::rotate_right(Node* p, Node* c)
{
    p->left = c->right;
    if(c->right != nullptr) c->right->parent = p;
 
    link(p, c);
 
    c->right = p;
    p->parent = c;
 
    while(p != nullptr && p->height_update())
        p = p->parent;
}
 
void AVL_tree::rotate_left(Node* p , Node* c)
{
    p->right = c->left;
    if(c->left != nullptr) c->left->parent = p;
 
    link(p, c);
 
    c->left = p;
    p->parent = c;
 
    while(p != nullptr && p->height_update())
        p = p->parent;
}
 
void AVL_tree::insert(Elem elem)
{
    Node* node = new Node{elem};
    if(empty()) root = node;
    else{
        Node *c = root, *p = nullptr;
        while(c != nullptr){
            p = c;
            c = ((c->elem <= elem)? c->right: c->left);
        }
 
        if(p->elem <= elem) p->right = node;
        else p->left = node;
 
        node->parent = p;
    }
    restructure(node);
 
    n += 1;
}
 
void AVL_tree::erase(Node* u)
{
    if(u == nullptr) throw "erase non existing element";
 
    Node* restore = nullptr;
    if(u->left == nullptr) {
        link(u, u->right);
        if(u->right != nullptr) restore = u->right;
        else restore = u->parent; // restore == nullptr 이면 resturcture에서 아무것도 안함
    }
    else if(u->right == nullptr) {
        link(u, u->left);
        restore = u->left;
    }
    else{
        Node* v = tree_minimum(u->right);
        
        if(u->right == v){
            restore = v;
        }
        else{
            if(v->right != nullptr) restore = v->right;
            else restore = v->parent;
        }
 
        if(u->right != v){
            link(v, v->right);
            v->right = u->right;
            u->right->parent = v;
        }
        link(u, v);
        u->left->parent = v;
        v->left = u->left;
 
    }
 
    delete u; u = nullptr;
    while(restore != nullptr) {
        restore = restructure(restore);
    }
 
    n -= 1;
}
 
void AVL_tree::erase_max()
{
    if(empty()) throw "empty";
    erase(tree_maximum(root));
}
 
void AVL_tree::erase_min()
{
    if(empty()) throw "empty";
    erase(tree_minimum(root));
}
 
Elem AVL_tree::tree_maximum() const
{
    if(empty()) throw "empty";
    return tree_maximum(root)->elem;
}
 
Elem AVL_tree::tree_minimum() const
{
    if(empty()) throw "empty";
    return tree_minimum(root)->elem;
}cs