SHARE
TWEET

Untitled

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