SHARE
TWEET

Untitled

a guest Dec 8th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2.  
  3. #include <optional>
  4. #include <stack>
  5.  
  6. template<typename Key, typename Data>
  7. class BinarySearchTree
  8. {
  9. private:
  10.     struct node
  11.     {
  12.         Key key;
  13.         Data data;
  14.         node* left;
  15.         node* right;
  16.  
  17.         node(const Key& k, const Data& d) : key(k), data(d), left(nullptr), right(nullptr)
  18.         {
  19.  
  20.         }
  21.     };
  22.  
  23.     node* root;
  24.     size_t count;
  25.  
  26.     node** _find(const Key& key)
  27.     {
  28.         node** p = &root;
  29.  
  30.         while (*p != nullptr && (*p)->key != key)
  31.         {
  32.             p = (*p)->key < key ? &((*p)->right) : &((*p)->left);
  33.         }
  34.  
  35.         return p;
  36.     }
  37.  
  38. public:
  39.     BinarySearchTree();
  40.  
  41.     std::optional<Data> find(const Key& key);
  42.  
  43.     void insert(const Key& key, const Data& data);
  44.  
  45.     ~BinarySearchTree();
  46. };
  47.  
  48. template<typename Key, typename Data>
  49. BinarySearchTree<Key, Data>::BinarySearchTree() :root(nullptr), count(0)
  50. {
  51.  
  52. }
  53.  
  54. template<typename Key, typename Data>
  55. std::optional<Data> BinarySearchTree<Key, Data>::find(const Key& key)
  56. {
  57.     std::optional<Data> res = std::nullopt;
  58.  
  59.     node** p = _find(key);
  60.  
  61.     if (*p)
  62.     {
  63.         res = (*p)->data;
  64.     }
  65.  
  66.     return res;
  67. }
  68.  
  69. template<typename Key, typename Data>
  70. void BinarySearchTree<Key, Data>::insert(const Key& key, const Data& data)
  71. {
  72.     node** p = _find(key);
  73.  
  74.     if (*p)
  75.     {
  76.         (*p)->data = data;
  77.     }
  78.     else
  79.     {
  80.         (*p) = new node(key, data);
  81.     }
  82. }
  83.  
  84. template<typename Key, typename Data>
  85. BinarySearchTree<Key, Data>::~BinarySearchTree()
  86. {
  87.     std::stack<node*> s;
  88.  
  89.     s.push(root);
  90.  
  91.     while (s.size())
  92.     {
  93.         auto top = s.top();
  94.         s.pop();
  95.  
  96.         if (top)
  97.         {
  98.             s.push(top->left);
  99.             s.push(top->right);
  100.             delete top;
  101.         }
  102.     }
  103. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top