diff options
Diffstat (limited to 'I_anno/Programmazione_2/data_structures/bst.cc')
-rw-r--r-- | I_anno/Programmazione_2/data_structures/bst.cc | 225 |
1 files changed, 0 insertions, 225 deletions
diff --git a/I_anno/Programmazione_2/data_structures/bst.cc b/I_anno/Programmazione_2/data_structures/bst.cc deleted file mode 100644 index 9223e04..0000000 --- a/I_anno/Programmazione_2/data_structures/bst.cc +++ /dev/null @@ -1,225 +0,0 @@ -#include<iostream> - -using namespace std; - -template<class T> -struct node { - T key; - node<T>* prev; - node<T>* right; - node<T>* left; -}; - -template<class T> -class bst { -public: - bst() : root{nullptr} {} - - ~bst() { - // TODO - } - - bst<T>* insert(initializer_list<T>&& list) { - for(auto const& i : list) - insert(i); - - return this; - } - - bst<T>* insert(T k) { - node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr}; - node<T>* iter = root; - node<T>* prev = nullptr; - - while(iter) { - prev = iter; - iter = (k < iter->key) ? iter->left : iter->right; - } - - nodus->prev = prev; - if(!prev) - root = nodus; - else if(k < prev->key) - prev->left = nodus; - else - prev->right = nodus; - - return this; - } - - bst<T>* remove(initializer_list<T>&& list) { - for(auto const& i : list) - remove(i); - - return this; - } - - bst<T>* remove(T k) { - node<T>* nodus = search(k); - if(!nodus) return this; - - if(!nodus->left) { - _transplant(nodus, nodus->right); - } else if(!nodus->right) { - _transplant(nodus, nodus->left); - } else { - node<T>* iter = _min(nodus->right); - if(iter->prev != nodus) { - _transplant(iter, iter->right); - iter->right = nodus->right; - iter->right->prev = iter; - } - _transplant(nodus, iter); - iter->left = nodus->left; - iter->left->prev = iter; - } - - delete nodus; - return this; - } - - node<T>* min() { - return _min(root); - } - - node<T>* min(node<T>* nodus) { - return _min(nodus); - } - - node<T>* max() { - return _max(root); - } - - node<T>* max(node<T>* nodus) { - return _max(nodus); - } - - node<T>* search(T k) { - node<T>* iter = root; - while(iter && iter->key != k) - iter = (iter->key > k) ? iter->left : iter->right; - - return iter; - } - - node<T>* successor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->right) - return min(nodus->right); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->right) { - nodus = prev; - prev = prev->prev; - } - - return prev; - - } - node<T>* predecessor(T k) { - node<T>* nodus = search(k); - if(!nodus) return nullptr; - - if(nodus->left) - return max(nodus->left); - - node<T>* prev = nodus->prev; - while(prev && nodus == prev->left) { - nodus = prev; - prev = prev->prev; - } - - return prev; - } - - friend ostream& operator<<(ostream& os, bst<T>* tree) { - tree->_preorder(os, tree->root); - return os; - } -private: - void _transplant(node<T>* u, node<T>* v) { - if(!u->prev) { - root = v; - } else if(u == u->prev->left) { - u->prev->left = v; - } else { - u->prev->right = v; - } - - if(v) - v->prev = u->prev; - } - - node<T>* _min(node<T>* root) { - node<T>* iter = root; - while(iter && iter->left) - iter = iter->left; - - return iter; - } - - node<T>* _max(node<T>* root) { - node<T>* iter = root; - while(iter && iter->right) - iter = iter->right; - - return iter; - } - - void _inorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - os << root->key << ' '; - _inorder(os, root->right); - } - } - - void _preorder(ostream& os, node<T>* root) { - if(root) { - os << root->key << ' '; - _inorder(os, root->left); - _inorder(os, root->right); - } - } - - void _postorder(ostream& os, node<T>* root) { - if(root) { - _inorder(os, root->left); - _inorder(os, root->right); - os << root->key << ' '; - } - } - node<T>* root; -}; - -int main() { - bst<int>* b = new bst<int>{}; - - // b->insert(12)->insert(5)->insert(18)->insert(2)->insert(9); - // b->insert(15)->insert(13)->insert(17)->insert(19); - - b->insert({12, 5, 18, 2, 9, 15, 13, 17, 19}); - cout << b << endl; - cout << (b->search(5) != nullptr) << endl; - cout << (b->search(1) != nullptr) << endl; - cout << b->max()->key << ' ' << b->min()->key << endl; - for(auto const& i : {12, 9, 14, 18}) { - auto elem = b->successor(i); - if(elem) - cout << "(" << i << ", " << elem->key << ") "; - } - cout << endl; - - for(auto const& i : {9, 2, 5, 15, 18, 12, 19}) { - auto elem = b->predecessor(i); - if(elem) - cout << "(" << i << ", " << elem->key << ") "; - } - cout << endl; - b->remove({5, 12}); - cout << b << endl; - - return 0; -} |