Advanced Programming - Binary Search Tree
A simple Binary Search Tree implementation for the Advanced Programming 2019-2020 course @ SISSA.
BST.hpp
1 #ifndef BST_HPP
2 #define BST_HPP
3 
4 
81 #include <iostream>
82 #include <iomanip>
83 #include <memory>
84 #include <sstream>
85 #include <utility>
86 #include <vector>
87 #include "Iterator.hpp"
88 #include "Node.hpp"
89 
90 
97 namespace APbst {
98 
115  template <typename KT, typename VT, typename cmp = std::less<KT>>
116  class bst{
118  cmp op;
120  std::unique_ptr<APutils::Node<std::pair<const KT, VT>>> root;
121 
132  /* If root is nullptr we return a nullptr */
133  if (!root) return nullptr;
134  /* I descend in the tree as long as I have a left child */
135  auto tmp = root.get();
136  while (tmp->left) {
137  tmp = tmp->left.get();
138  }
139  return tmp;
140  }
141 
151  auto tmp = root.get();
152  while (tmp) {
153  if (op(x,tmp->data.first)) {
154  tmp = tmp->left.get();
155  } else if (op(tmp->data.first, x)) {
156  tmp = tmp->right.get();
157  } else {
158  return tmp;
159  }
160  }
161  // The tree is empty or the key doesn't exist, so I return the end of the tree (a nullptr)
162  return nullptr;
163  }
164 
177  void __copy(const bst& t, std::unique_ptr<APutils::Node<std::pair<const KT, VT>>>& a) {
178  this->emplace(a.get()->data);
179  if (a.get()->left) {
180  __copy(t, a.get()->left);
181  }
182  if (a.get()->right) {
183  __copy(t, a.get()->right);
184  }
185  return;
186  }
187 
201  void __balance(std::vector<std::pair<const KT, VT>>& v, long long int a, long long int b) {
202  if (b < a) {
203  return;
204  }
205  long long int mid{(b + a)/2};
206  #ifdef __DEBUG_AP_BST
207  std::cout << "Inserting " << v[mid].first << " in place " << mid << std::endl;
208  #endif
209  this->emplace(v[mid]);
210  __balance(v, a, mid-1);
211  __balance(v, mid+1, b);
212  return;
213  }
214 
215  public:
219  using key_type = KT;
223  using mapped_type = VT;
227  using pair_type = typename std::pair<const KT, VT>;
240 
247  bst() noexcept : op{}, root{nullptr} {}
248 
257  explicit bst(cmp x) noexcept : op{x}, root{nullptr} {}
258 
268  explicit bst(const bst& t) : op{t.op}, root{std::unique_ptr<node_type>(new node_type(t.root.get()->data, nullptr))} {
269  if (t.root.get()->left) {
270  __copy(t, t.root.get()->left);
271  }
272  if (t.root.get()->right) {
273  __copy(t, t.root.get()->right);
274  }
275  }
276 
286  bst(bst&& t) noexcept = default;
287 
297  bst& operator=(const bst& t) {
298  this->clear();
299  this->emplace(t.root.get()->data);
300  if (t.root.get()->left) {
301  __copy(t, t.root.get()->left);
302  }
303  if (t.root.get()->right) {
304  __copy(t, t.root.get()->right);
305  }
306  return *this;
307  }
308 
318  bst& operator=(bst&& t) noexcept = default;
319 
332  std::pair<iterator, bool> insert(const pair_type& x) {
333  #ifdef __DEBUG_AP_BST
334  std::cout << "CALL: COPY_INSERT: APbst::bst::insert(const pair_type& x)" << std::endl;
335  #endif
336  auto tmp = root.get();
337  while (tmp) {
338  if (op(x.first,tmp->data.first)) {
339  if (tmp->left) {
340  tmp = tmp->left.get();
341  } else {
342  tmp->left.reset(new node_type{x, tmp});
343  return std::make_pair<iterator, bool>(iterator{tmp->left.get()}, true);
344  }
345  } else if (op(tmp->data.first, x.first)) {
346  if (tmp->right) {
347  tmp = tmp->right.get();
348  } else {
349  tmp->right.reset(new node_type{x, tmp});
350  return std::make_pair<iterator, bool>(iterator{tmp->right.get()}, true);
351  }
352  } else {
353  return std::make_pair<iterator, bool>(iterator{tmp}, false);
354  }
355  }
356  // The tree is empty, so I put it in the root
357  root.reset(new node_type{x, nullptr});
358  return std::make_pair<iterator, bool>(iterator{tmp}, true);
359  }
360 
373  std::pair<iterator, bool> insert(pair_type&& x) {
374  #ifdef __DEBUG_AP_BST
375  std::cout << "CALL: MOVE_INSERT: APbst::bst::insert(pair_type&& x)" << std::endl;
376  #endif
377  auto tmp = root.get();
378  while (tmp) {
379  if (op(x.first,tmp->data.first)) {
380  if (tmp->left) {
381  tmp = tmp->left.get();
382  } else {
383  tmp->left.reset(new node_type{std::move(x), tmp});
384  return std::make_pair<iterator, bool>(iterator{tmp->left.get()}, true);
385  }
386  } else if (op(tmp->data.first, x.first)) {
387  if (tmp->right) {
388  tmp = tmp->right.get();
389  } else {
390  tmp->right.reset(new node_type{std::move(x), tmp});
391  return std::make_pair<iterator, bool>(iterator{tmp->right.get()}, true);
392  }
393  } else {
394  return std::make_pair<iterator, bool>(iterator{tmp}, false);
395  }
396  }
397  root.reset(new node_type{std::move(x), nullptr});
398  return std::make_pair<iterator, bool>(iterator{tmp}, true);
399  }
400 
414  template<class... Types> // variadic templates
415  std::pair<iterator,bool> emplace(Types&&... args) {
416  return insert(pair_type{std::forward<Types>(args)...});
417  }
418 
425  void clear() noexcept {
426  this->root.reset();
427  }
428 
438  iterator begin() noexcept {
439  #ifdef __DEBUG_AP_BST
440  std::cout << "CALL: NONCONST_BEGIN" << std::endl;
441  #endif
442  return iterator{__begin()};
443  }
444 
454  const_iterator begin() const noexcept {
455  #ifdef __DEBUG_AP_BST
456  std::cout << "CALL: CONST_BEGIN" << std::endl;
457  #endif
458  return const_iterator{__begin()};
459  }
460 
467  const_iterator cbegin() const noexcept {
468  return const_iterator{__begin()};
469  }
470 
479  iterator end() noexcept {
480  #ifdef __DEBUG_AP_BST
481  std::cout << "CALL: NONCONST_END" << std::endl;
482  #endif
483  return iterator{nullptr};
484  }
485 
494  const_iterator end() const noexcept {
495  #ifdef __DEBUG_AP_BST
496  std::cout << "CALL: CONST_END" << std::endl;
497  #endif
498  return const_iterator{nullptr};
499  }
500 
507  const_iterator cend() const noexcept {
508  return const_iterator{nullptr};
509  }
510 
519  iterator find(const key_type& x) {
520  #ifdef __DEBUG_AP_BST
521  std::cout << "CALL: NONCONST_FIND" << std::endl;
522  #endif
523  return iterator{__find(x)};
524  }
525 
534  const_iterator find(const key_type& x) const {
535  #ifdef __DEBUG_AP_BST
536  std::cout << "CALL: CONST_FIND" << std::endl;
537  #endif
538  return const_iterator{__find(x)};
539  }
540 
547  void balance() {
548  std::vector<pair_type> v{};
549  for (const auto& it : *this) {
550  v.push_back(it);
551  }
552  this->clear();
553  long long int mid{(static_cast<long long int> (v.size()))/2};
554  #ifdef __DEBUG_AP_BST
555  std::cout << "Inserting " << v[mid].first << " in palce " << mid << std::endl;
556  #endif
557  this->emplace(v[mid]);
558  __balance(v, 0, mid-1);
559  __balance(v, mid+1, v.size()-1);
560  return;
561  }
562 
571  mapped_type& operator[](const key_type& x) { // copy semantic
572  #ifdef __DEBUG_AP_BST
573  std::cout << "CALL: COPY_[]" << std::endl;
574  #endif
575  return insert(pair_type{x, mapped_type()}).first->second;
576  }
577 
586  mapped_type& operator[](key_type&& x) { // move semantic
587  #ifdef __DEBUG_AP_BST
588  std::cout << "CALL: MOVE_[]" << std::endl;
589  #endif
590  return insert(pair_type{std::move(x), mapped_type()}).first->second;
591  }
592 
618  friend std::ostream& operator<<(std::ostream& os, const bst& x) {
619  //for (const auto& it : x) {
620  // os << "[Key: " << std::setw(4) << it.first << ", Value: " << std::setw(4) << it.second << "]" << std::endl;
621  //}
622  auto itStop = x.cend();
623  for (auto it = x.cbegin(); it != itStop; ++it) {
624  // os << "[" << it.currentNode << "] "
625  // << "[Key: " << std::setw(4) << it->first << ", Value: " << std::setw(4) << it->second << "]" << std::endl;
626  it.printNode(os, true);
627  }
628  return os;
629  }
630 
648  void printRawTree(std::stringstream& ss) {
649  for (const auto& it : *this) {
650  ss << it.first << " : " << it.second << std::endl;
651  }
652  return;
653  }
654 
662  void erase(const key_type& x) {
663  auto __nodeToDeleteIt = find(x);
664 
665  auto __nodeToDelete = __nodeToDeleteIt.currentNode;
666 
667  /* If I am deleting a nullptr. */
668  if (!__nodeToDelete) return;
669 
670  /* If I'm deleting the root. */
671  if (__nodeToDelete == root.get()) {
672  if ((!__nodeToDelete->left) && (!__nodeToDelete->right)) { // If node has no children
673  root.reset();
674  } else if ( !(!__nodeToDelete->left) != !(!__nodeToDelete->right) ) { // If node has one child
675  if (__nodeToDelete->left) { // If the child is the left one
676  root.reset(__nodeToDelete->left.release());
677  __nodeToDelete->left->parent = nullptr;
678  } else { // If the child is the right one
679  root.reset(__nodeToDelete->right.release());
680  __nodeToDelete->right->parent = nullptr;
681  }
682  } else { // If node has two children
683  /* We find the successor 'S' (which, for sure, has NO left child)
684  * and copy the successor 'S' in place of the deleted node 'D'.
685  * If the successor 'S' has a right child 'R', we copy 'R'
686  * in place of 'S' and remove 'R'.
687  */
688  auto __nodeSuccessor = (++__nodeToDeleteIt).currentNode; // Find in-order successor
689  /* Create a new node with the data of 'S' and that points, to
690  * the left and to the right, to the left/right children of 'D',
691  * and that has nullptr as its parent.
692  */
693  //auto dummyNode = std::make_unique<node_type>(__nodeSuccessor->data, nullptr);
694  auto dummyNode = std::unique_ptr<node_type>(new node_type(__nodeSuccessor->data, nullptr));
695  dummyNode.get()->left .reset(__nodeToDelete->left .release());
696  dummyNode.get()->left .get()->parent = dummyNode.get();
697 
698  /* If successor 'S' is right child of 'D', special case */
699  if (__nodeToDelete->right.get() == __nodeSuccessor) {
700  dummyNode.get()->right.reset(__nodeSuccessor->right.release());
701  dummyNode.get()->right.get()->parent = dummyNode.get();
702  } else {
703  dummyNode.get()->right.reset(__nodeToDelete->right.release());
704  dummyNode.get()->right.get()->parent = dummyNode.get();
705  if (__nodeSuccessor->right) {
706  /* Extra case: 'S' has 'R'. */
707  __nodeSuccessor->right->parent = __nodeSuccessor->parent;
708  __nodeSuccessor->parent->left.reset(__nodeSuccessor->right.release());
709  } else {
710  __nodeSuccessor->parent->left.reset();
711  }
712  }
713 
714  root.reset(dummyNode.release());
715  }
716 
717  return;
718  }
719 
720  /* If I'm deleting any other node, that has in this case a parent. */
721  auto __nodeParent = __nodeToDelete->parent;
722 
723  if ((!__nodeToDelete->left) && (!__nodeToDelete->right)) { // If node has no children
724  if (__nodeParent->left.get() == __nodeToDelete) { // If node is left child of parent
725  __nodeParent->left.reset();
726  } else { // If node is right child of parent
727  __nodeParent->right.reset();
728  }
729  } else if ( !(!__nodeToDelete->left) != !(!__nodeToDelete->right) ) { // If node has one child
730  if (__nodeToDelete->left) { // If the child is the left one
731  __nodeToDelete->left.get()->parent = __nodeParent;
732  if (__nodeParent->left.get() == __nodeToDelete) { // If node is left child of parent
733  __nodeParent->left.reset(__nodeToDelete->left.release());
734  } else { // If node is right child of parent
735  __nodeParent->right.reset(__nodeToDelete->left.release());
736  }
737  } else { // If the child is the right one
738  __nodeToDelete->right.get()->parent = __nodeParent;
739  if (__nodeParent->left.get() == __nodeToDelete) { // If node is left child of parent
740  __nodeParent->left.reset(__nodeToDelete->right.release());
741  } else { // If node is right child of parent
742  __nodeParent->right.reset(__nodeToDelete->right.release());
743  }
744  }
745  } else { // If node has two children
746  /* We find the successor 'S' (which, for sure, has NO left child)
747  * and copy the successor 'S' in place of the deleted node 'D'.
748  * If the successor 'S' has a right child 'R', we copy 'R'
749  * in place of 'S' and remove 'R'.
750  */
751  auto __nodeSuccessor = (++__nodeToDeleteIt).currentNode; // Find in-order successor
752 
753  /* Create a new node with the data of 'S' and that points, to
754  * the left and to the right, to the left/right children of 'D',
755  * and that has __nodeParent as its parent.
756  */
757  //auto dummyNode = std::make_unique<node_type>(__nodeSuccessor->data, __nodeParent);
758  auto dummyNode = std::unique_ptr<node_type>(new node_type(__nodeSuccessor->data, __nodeParent));
759  dummyNode.get()->left .reset(__nodeToDelete->left .release());
760  dummyNode.get()->left .get()->parent = dummyNode.get();
761 
762  /* If successor 'S' is right child of 'D', special case */
763  if (__nodeToDelete->right.get() == __nodeSuccessor) {
764  dummyNode.get()->right.reset(__nodeSuccessor->right.release());
765  dummyNode.get()->right.get()->parent = dummyNode.get();
766  /* Let __nodeParent to point to dummyNode as well. */
767  if (__nodeParent->left.get() == __nodeToDelete) {
768  __nodeParent->left .reset(dummyNode.release());
769  } else {
770  __nodeParent->right.reset(dummyNode.release());
771  }
772  } else {
773  dummyNode.get()->right.reset(__nodeToDelete->right.release());
774  dummyNode.get()->right.get()->parent = dummyNode.get();
775  /* Let __nodeParent to point to dummyNode as well. */
776  if (__nodeParent->left.get() == __nodeToDelete) {
777  __nodeParent->left .reset(dummyNode.release());
778  } else {
779  __nodeParent->right.reset(dummyNode.release());
780  }
781  if (__nodeSuccessor->right) {
782  /* Extra case: 'S' has 'R'. */
783  __nodeSuccessor->right->parent = __nodeSuccessor->parent;
784  __nodeSuccessor->parent->left.reset(__nodeSuccessor->right.release());
785  } else {
786  __nodeSuccessor->parent->left.reset();
787  }
788  }
789 
790  }
791  // The tree is empty or the key doesn't exist, so I return.
792  return;
793  }
794 
795  };
796 
797 }
798 
799 #endif // BST_HPP
std::pair< iterator, bool > insert(pair_type &&x)
Inserts a APutils::Node by moving it in the tree, if not already present.
Definition: BST.hpp:373
Class that implements an iterator of a tree.
Definition: Iterator.hpp:19
const_iterator find(const key_type &x) const
Finds if a node just exists.
Definition: BST.hpp:534
const_iterator end() const noexcept
Returns a const_iterator to one-past the last element.
Definition: BST.hpp:494
VT mapped_type
The Value type of the Node of the tree.
Definition: BST.hpp:223
friend std::ostream & operator<<(std::ostream &os, const bst &x)
Put-to operator that prints the tree.
Definition: BST.hpp:618
const_iterator cend() const noexcept
The const version of end(), to be used when a const_iterator is needed.
Definition: BST.hpp:507
typename std::pair< const KT, VT > pair_type
The Pair type of the tree, i.e. std::pair<const Key,Value>.
Definition: BST.hpp:227
mapped_type & operator[](const key_type &x)
Subscripting operator performing a copy.
Definition: BST.hpp:571
void __copy(const bst &t, std::unique_ptr< APutils::Node< std::pair< const KT, VT >>> &a)
Internal helper function for the copy operations.
Definition: BST.hpp:177
const_iterator begin() const noexcept
Returns a const_iterator to the left-most APutils::Node.
Definition: BST.hpp:454
typename APutils::__iterator< node_type, const pair_type > const_iterator
The const iterator type.
Definition: BST.hpp:239
bst() noexcept
Empty constructor.
Definition: BST.hpp:247
const_iterator cbegin() const noexcept
The const version of begin(), to be used when a const_iterator is needed.
Definition: BST.hpp:467
typename APutils::Node< pair_type > node_type
The Node type of the tree, i.e. Node<Pair>.
Definition: BST.hpp:231
APutils::Node< std::pair< const KT, VT > > * __find(const KT &x) const
Internal helper function for find().
Definition: BST.hpp:150
std::pair< iterator, bool > emplace(Types &&... args)
Inserts a APutils::Node constructed in-place.
Definition: BST.hpp:415
iterator find(const key_type &x)
Finds a APutils::Node and possibly change its value.
Definition: BST.hpp:519
typename APutils::__iterator< node_type, pair_type > iterator
The non-const iterator type.
Definition: BST.hpp:235
bst(cmp x) noexcept
Empty constructor with an explicit comparison ("less than") operation.
Definition: BST.hpp:257
bst & operator=(const bst &t)
Copy assignment for bst.
Definition: BST.hpp:297
bst(const bst &t)
Copy constructor.
Definition: BST.hpp:268
APutils::Node< std::pair< const KT, VT > > * __begin() const
Internal helper function for begin().
Definition: BST.hpp:131
void erase(const key_type &x)
Removes the element (if it exists) with Key x.
Definition: BST.hpp:662
void clear() noexcept
Clears the content of the tree.
Definition: BST.hpp:425
mapped_type & operator[](key_type &&x)
Subscripting operator performing a move.
Definition: BST.hpp:586
iterator begin() noexcept
Returns an iterator to the left-most APutils::Node.
Definition: BST.hpp:438
void __balance(std::vector< std::pair< const KT, VT >> &v, long long int a, long long int b)
Internal helper function for balance().
Definition: BST.hpp:201
KT key_type
The Key type of the Node of the tree.
Definition: BST.hpp:219
Class that implements a node of a tree.
Definition: Node.hpp:26
std::pair< iterator, bool > insert(const pair_type &x)
Inserts a APutils::Node by copying it in the tree, if not already present.
Definition: BST.hpp:332
std::unique_ptr< APutils::Node< std::pair< const KT, VT > > > root
The root Node of the tree.
Definition: BST.hpp:120
Namespace for the Binary Search Tree.
Definition: BST.hpp:97
void balance()
Balances the tree.
Definition: BST.hpp:547
cmp op
Operator of comparison ("less than") for the Key type.
Definition: BST.hpp:118
void printRawTree(std::stringstream &ss)
Prints the tree in an easy way.
Definition: BST.hpp:648
Class that implements a Binary Search Tree.
Definition: BST.hpp:116
iterator end() noexcept
Returns an iterator to one-past the last element.
Definition: BST.hpp:479