summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2/data_structures
diff options
context:
space:
mode:
Diffstat (limited to 'I_anno/Programmazione_2/data_structures')
-rw-r--r--I_anno/Programmazione_2/data_structures/bst.cc225
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;
+}