AVLSample.cpp

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

struct AVL {
    struct Node { int key; int height; Node* left; Node* right; Node(int k): key(k), height(1), left(nullptr), right(nullptr) {} };
    Node* root = nullptr;
    int h(Node* n) { return n ? n->height : 0; }
    void upd(Node* n) { n->height = 1 + max(h(n->left), h(n->right)); }
    int bf(Node* n) { return n ? h(n->left) - h(n->right) : 0; }
    Node* rotL(Node* x) { Node* y = x->right; Node* t = y->left; y->left = x; x->right = t; upd(x); upd(y); return y; }
    Node* rotR(Node* y) { Node* x = y->left; Node* t = x->right; x->right = y; y->left = t; upd(y); upd(x); return x; }
    Node* reb(Node* n) { upd(n); int d = bf(n); if (d > 1) { if (bf(n->left) < 0) n->left = rotL(n->left); return rotR(n); } if (d < -1) { if (bf(n->right) > 0) n->right = rotR(n->right); return rotL(n); } return n; }
    Node* insert(Node* n, int k) { if (!n) return new Node(k); if (k < n->key) n->left = insert(n->left, k); else if (k > n->key) n->right = insert(n->right, k); else return n; return reb(n); }
    void insert(int k) { root = insert(root, k); }
    Node* minNode(Node* n) { while (n->left) n = n->left; return n; }
    Node* erase(Node* n, int k) { if (!n) return n; if (k < n->key) n->left = erase(n->left, k); else if (k > n->key) n->right = erase(n->right, k); else { if (!n->left || !n->right) { Node* t = n->left ? n->left : n->right; delete n; n = t; } else { Node* t = minNode(n->right); n->key = t->key; n->right = erase(n->right, t->key); } } if (!n) return n; return reb(n); }
    void erase(int k) { root = erase(root, k); }
    bool contains(int k) { Node* n = root; while (n) { if (k < n->key) n = n->left; else if (k > n->key) n = n->right; else return true; } return false; }
    void inorder(Node* n) { if (!n) return; inorder(n->left); cout << n->key << ' '; inorder(n->right); }
    void print() { inorder(root); cout << '\n'; }
    int height() { return h(root); }
    void destroy(Node* n) { if (!n) return; destroy(n->left); destroy(n->right); delete n; }
    ~AVL() { destroy(root); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    AVL T;
    vector<int> a = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
    for (int x : a) T.insert(x);
    cout << "Inorder ";
    T.print();
    cout << "Height " << T.height() << '\n';
    cout << (T.contains(7) ? "Found 7\n" : "NotFound 7\n");
    T.erase(16);
    T.erase(14);
    T.erase(3);
    cout << "AfterDelete ";
    T.print();
    cout << "Height " << T.height() << '\n';
    return 0;
}