diff options
Diffstat (limited to 'Year_1/Programming_2/exercises/exam_08_10_14.cc')
| -rw-r--r-- | Year_1/Programming_2/exercises/exam_08_10_14.cc | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/Year_1/Programming_2/exercises/exam_08_10_14.cc b/Year_1/Programming_2/exercises/exam_08_10_14.cc new file mode 100644 index 0000000..c9c33be --- /dev/null +++ b/Year_1/Programming_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; +} |