diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-05-14 22:25:18 +0200 |
---|---|---|
committer | Santo Cariotti <dcariotti24@gmail.com> | 2020-05-14 22:25:18 +0200 |
commit | 3abe1723e3cb3a6cdf189db47cc8936ff4c32141 (patch) | |
tree | 396dd5771adb8391d6041bf1188b0340e0e97758 /I_anno/Programmazione_2 | |
parent | 81d68a2807241848a9f96ae9f0f0b405f348154f (diff) |
feat: binary search tree
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r-- | I_anno/Programmazione_2/data_structures/bst.cc | 225 |
1 files changed, 225 insertions, 0 deletions
diff --git a/I_anno/Programmazione_2/data_structures/bst.cc b/I_anno/Programmazione_2/data_structures/bst.cc new file mode 100644 index 0000000..9223e04 --- /dev/null +++ b/I_anno/Programmazione_2/data_structures/bst.cc @@ -0,0 +1,225 @@ +#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; +} |