feat: add exam 08/10/2014

1 files changed, 202 insertions, 0 deletions

diff --git a/I_anno/Programmazione_2/exercises/exam_08_10_14.cc b/I_anno/Programmazione_2/exercises/exam_08_10_14.cc
new file mode 100644
index 0000000..c9c33be
--- /dev/null
+++ b/I_anno/Programmazione_2/exercises/exam_08_10_14.cc
@@ -0,0 +1,202 @@
+#include<iostream>
+
+using namespace std;
+
+template<class H> class MultiBST {
+    virtual MultiBST<H>* ins(H x) = 0;
+    virtual int multiplicity(H x) = 0;
+    virtual void inorder() = 0;
+};
+
+template<class H>
+class node {
+public:
+    node(H val) : _key{val}, _parent{nullptr}, _left{nullptr}, _right{nullptr}, _rk{1} {}
+    H& key() { return _key; }  
+    const H& key() const { return _key; }  
+    node<H>*& parent() { return _parent; }
+    const node<H>*& parent() const { return _parent; }
+    node<H>*& left() { return _left; }
+    const node<H>*& left() const { return _left; }
+    node<H>*& right() { return _right; }
+    const node<H>*& right() const { return _right; }
+    int& rk() { return _rk; }
+    const int& rk() const { return _rk; }
+private:
+    H _key;
+    node<H>* _parent;
+    node<H>* _left;
+    node<H>* _right;
+    int _rk;
+};
+
+template<class H>
+class MyMultiBST : public MultiBST<H> {
+public:
+    MyMultiBST() : _root{nullptr} {}
+    node<H>*& root() { return _root; }
+    const node<H>*& root() const { return _root; }
+    int multiplicity(H x) {
+        auto elem = _search(x);
+        if(elem)
+            return elem->rk();
+        return 0;
+    }
+    MyMultiBST<H>* ins(H x) {
+        auto iter = _search(x);
+        if(iter) {
+            iter->rk() = iter->rk()+1;
+        } else {
+            iter = _root;
+            node<H>* y{nullptr};
+
+            while(iter) {
+                y = iter;
+                if(iter->key() > x) 
+                    iter = iter->left();
+                else
+                    iter = iter->right();
+            }
+
+            node<H>* nodus = new node<H>{x};
+            nodus->parent() = y;
+            if(!y) {
+                _root = nodus;
+            } else if(y->key() > x) {
+                y->left() = nodus;
+            } else {
+                y->right() = nodus;
+            }
+        }
+
+        return this;
+    }
+    void inorder() {
+       _inorder(_root);
+    }
+    MyMultiBST<H>* del(H x) {
+        node<H>* y;
+        node<H>* z = _search(x);
+
+        if(!z) return this;
+
+        if(z->rk() > 1) {
+            z->rk() = z->rk()-1;
+        } else {
+            if(!z->left()) {
+                _transplant(z, z->right());
+            } else if(!z->right()) {
+                _transplant(z, z->left());
+            } else {
+                y = _min(z->right());
+                if(y->parent() != z) {
+                    _transplant(y, y->right());
+                    y->right() = z->right();
+                    y->right()->parent() = y;
+                }
+                _transplant(z, y);
+                y->left() = z->left();
+                y->left()->parent() = y;
+                delete z;
+            }
+        }
+
+        return this;
+    }
+    node<H>* predecessor(H x) {
+        auto iter = _search(x);
+        if(!iter) return nullptr;
+        if(iter->left())
+            return _max(iter->left());
+
+        auto y = iter->parent();
+        while(y && iter == y->left()) {
+            iter = y;
+            y = y->parent();
+        }
+
+        return y;
+    }
+    int rank(H x) {
+        auto iter = predecessor(x);
+        int sum{1};
+        while(iter) {
+            sum+=iter->rk();
+            iter = predecessor(iter->key());
+        }
+        return sum;
+    }
+private:
+    void _transplant(node<H>* u, node<H>* v) {
+        if(!u->parent()) _root = v;
+        else if(u == u->parent()->left())
+            u->parent()->left() = v;
+        else
+            u->parent()->right() = v;
+
+        if(v)
+            v->parent() = u->parent();
+    }
+    node<H>* _max(node<H>* x) {
+        if(!x) return nullptr;
+
+        auto iter = x;
+        while(iter->right()) {
+            iter = iter->right();
+        }
+
+        return iter;
+    }
+    node<H>* _min(node<H>* x) {
+        if(!x) return nullptr;
+
+        auto iter = x;
+        while(iter->left()) {
+            iter = iter->left();
+        }
+
+        return iter;
+    }
+    void _inorder(node<H>* p) {
+        if(p) {
+            _inorder(p->left());
+            for(int i = 0; i < p->rk(); ++i) {
+                cout << p->key() << ' ';
+            }
+            _inorder(p->right());
+        }
+    }
+    node<H>* _search(H val) {
+        auto iter = _root;
+        while(iter && iter->key() != val) {
+            if(iter->key() > val)
+                iter = iter->left();
+            else
+                iter = iter->right();
+        }
+
+        return iter;
+    }
+    node<H>* _root;
+};
+
+int main() {
+    MyMultiBST<int>* t = new MyMultiBST<int>{};
+
+    for(auto const& i : {10, 7, 7, 23, 30, 4, 1, 5, 9, 5, 1, 7, 1, 9})
+        t->ins(i);
+
+    t->inorder();
+    cout << '\n';
+    for(auto const& i : {5, 7, 17})
+        cout << i << ": " << t->multiplicity(i) << endl;
+
+    for(auto const& i : {7, 4, 23, 7, 7})
+        t->del(i);
+    t->inorder();
+    cout << '\n';
+    for(auto const& i: {5, 9, 30})
+        cout << t->rank(i) << ' ';
+    delete t;
+    return 0;
+}