Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <optional>
- #include <stack>
- template<typename Key, typename Data>
- class BinarySearchTree
- {
- private:
- struct node
- {
- Key key;
- Data data;
- node* left;
- node* right;
- node(const Key& k, const Data& d) : key(k), data(d), left(nullptr), right(nullptr)
- {
- }
- };
- node* root;
- size_t count;
- node** _find(const Key& key)
- {
- node** p = &root;
- while (*p != nullptr && (*p)->key != key)
- {
- p = (*p)->key < key ? &((*p)->right) : &((*p)->left);
- }
- return p;
- }
- public:
- BinarySearchTree();
- std::optional<Data> find(const Key& key);
- void insert(const Key& key, const Data& data);
- ~BinarySearchTree();
- };
- template<typename Key, typename Data>
- BinarySearchTree<Key, Data>::BinarySearchTree() :root(nullptr), count(0)
- {
- }
- template<typename Key, typename Data>
- std::optional<Data> BinarySearchTree<Key, Data>::find(const Key& key)
- {
- std::optional<Data> res = nullopt;
- node** p = _find(key);
- if (*p)
- {
- res = (*p)->data;
- }
- return res;
- }
- template<typename Key, typename Data>
- void BinarySearchTree<Key, Data>::insert(const Key& key, const Data& data)
- {
- node** p = _find(key);
- if (*p)
- {
- (*p)->data = data;
- }
- else
- {
- (*p) = new node(key, data);
- }
- }
- template<typename Key, typename Data>
- BinarySearchTree<Key, Data>::~BinarySearchTree()
- {
- std::stack<node*> s;
- s.push(root);
- while (s.size())
- {
- auto top = s.top();
- s.pop();
- if (top)
- {
- s.push(top->left);
- s.push(top->right);
- delete top;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement