From ee95f53250a692a071e82a03091bb2ee3b708cf7 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <dcariotti24@gmail.com>
Date: Tue, 9 Jun 2020 18:02:55 +0200
Subject: feat: add exam 08/10/2014
---
I_anno/Programmazione_2/exercises/exam_08_10_14.cc | 202 +++++++++++++++++++++
1 file changed, 202 insertions(+)
create mode 100644 I_anno/Programmazione_2/exercises/exam_08_10_14.cc
(limited to 'I_anno/Programmazione_2')
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;
+}
--
cgit v1.2.3-18-g5258