binary_search_tree.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * HUC - Hurna Core
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #ifndef MODULE_DATA_STRUCTURES_BST_HXX
21 #define MODULE_DATA_STRUCTURES_BST_HXX
22 
23 #include <memory>
24 
25 namespace huc
26 {
54  template <typename IT, typename Compare, typename IsEqual>
55  class BST
56  {
57  typedef typename std::iterator_traits<IT>::value_type Value;
58  public:
69  static std::unique_ptr<BST> Build(const IT& begin, const IT& end)
70  {
71  if (begin >= end)
72  return nullptr;
73 
74  // Create root node
75  auto root = std::unique_ptr<BST>(new BST(*begin));
76 
77  // Insert all remaining elements within the tree
78  for (auto it = begin + 1; it != end; ++it)
79  root->Insert(*it);
80 
81  return root;
82  }
83 
100  static std::unique_ptr<BST> BuildFromSorted(const IT& begin, const IT& end)
101  {
102  if (begin >= end)
103  return nullptr;
104 
105  const auto middle = begin + (std::distance(begin,end) / 2);
106  auto root = std::unique_ptr<BST>(new BST(*middle));
107 
108  // Recursively insert both children
109  root->SetLeftChild(std::move(BuildFromSorted(begin, middle)));
110  root->SetRightChild(std::move(BuildFromSorted(middle + 1, end)));
111 
112  return root;
113  }
114 
124  const BST* Find(const Value& data)
125  {
126  // Key found returns node
127  if (IsEqual()(this->data, data))
128  return this;
129 
130  // Key is less than current node - search in left subtree
131  if (Compare()(data, this->data))
132  return this->leftChild ? this->leftChild->Find(data) : nullptr;
133 
134  // Search in right subtree
135  return this->rightChild ? this->rightChild->Find(data) : nullptr;
136  }
137 
147  void Insert(const Value& data)
148  {
149  // Key is lower or equal than current root - Insert on the left side
150  if (Compare()(data, this->data))
151  {
152  if (!this->leftChild)
153  this->SetLeftChild(std::move(std::unique_ptr<BST>(new BST(data))));
154  else
155  this->leftChild->Insert(data);
156  }
157  // Key is greater than current root - Insert on the right side
158  else
159  {
160  if (!this->rightChild)
161  this->SetRightChild(std::move(std::unique_ptr<BST>(new BST(data))));
162  else
163  this->rightChild->Insert(data);
164  }
165  }
166 
171  bool IsBlanced() const { return this->MaxHeight() - this->MinHeight() <= 1; }
172 
185  bool IsValid() const
186  {
187  auto previousNode = std::unique_ptr<const BST*>(new const BST*);
188  *previousNode = nullptr;
189  return this->IsValid(previousNode);
190  }
191 
197  std::size_t MaxHeight() const
198  {
199  return 1 + std::max(((this->leftChild) ? this->leftChild->MaxHeight() : 0),
200  ((this->rightChild) ? this->rightChild->MaxHeight() : 0));
201  }
202 
208  std::size_t MinHeight() const
209  {
210  return 1 + std::min(((this->leftChild) ? this->leftChild->MinHeight() : 0),
211  ((this->rightChild) ? this->rightChild->MinHeight() : 0));
212  }
213 
227  static const BST* Remove(std::unique_ptr<BST>& bst, const Value& data)
228  {
229  // Break on empty unique_ptr
230  if (!bst)
231  return nullptr;
232 
233  // Reach node matching the value
234  if (!IsEqual()(bst->data, data))
235  {
236  if (Compare()(data, bst->data))
237  Remove(bst->leftChild, data);
238  else
239  Remove(bst->rightChild, data);
240  }
241  // Proceed removal
242  else
243  {
244  // Recursively delete all subnodes containing the same value
245  if (bst->leftChild && IsEqual()(bst->data, bst->leftChild->data))
246  Remove(bst->leftChild, data);
247 
248  // No child - Simply remove node
249  if (!bst->leftChild && !bst->rightChild)
250  bst.reset();
251  // Both children:
252  // - Swap node value with its predecessor
253  // - Remove predecessor node and replace it with its child
254  else if (bst->leftChild && bst->rightChild)
255  {
256  auto& predecessor = bst->GetPredecessor();
257  std::swap(bst->data, predecessor->data);
258  predecessor.reset(predecessor->leftChild.release());
259  }
260  // Left node is unique child - remove node and replace it with its child.
261  else if (bst->leftChild)
262  bst.reset(bst->leftChild.release());
263  // Right node is unique child - remove node and replace it with its child.
264  else if (bst->rightChild)
265  bst.reset(bst->rightChild.release());
266  }
267 
268  // Return pointer handled by bst.
269  return bst.get();
270  }
271 
277  std::size_t Size() const
278  {
279  return 1 + ((this->leftChild) ? this->leftChild->Size() : 0)
280  + ((this->rightChild) ? this->rightChild->Size() : 0);
281  }
282 
283  Value GetData() const { return this->data; }
284  const BST* GetLeftChild() const { return this->leftChild.get(); }
285  const BST* GetRightChild() const { return this->rightChild.get(); }
286 
287  private:
288  BST(const Value& data) : data(data) {}
289  BST(BST&) {} // Not Implemented
290  BST operator=(BST&) {} // Not Implemented
291 
306  bool IsValid(std::unique_ptr<const BST*>& previousNode) const
307  {
308  // Recurse on left child without breaking if not failing
309  if (this->leftChild &&!this->leftChild->IsValid(previousNode))
310  return false;
311 
312  // First node retrieve - assign
313  if (!*previousNode)
314  *previousNode = this;
315  // Previous data does not compare well to the current one - BST not valid
316  else if (!Compare()((*previousNode)->data, this->data))
317  return false;
318 
319  // Set current node
320  *previousNode = this;
321 
322  // Recurse on right child
323  if (this->rightChild && !this->rightChild->IsValid(previousNode))
324  return false;
325 
326  return true;
327  }
328 
334  std::unique_ptr<BST>& GetPredecessor()
335  {
336  // Cannot get predecessor if no left child exists
337  assert(("GetPredecessor should not be called if no left child exists.", this->leftChild));
338 
339  // Left child is the predecessor
340  if (!this->leftChild->rightChild)
341  return this->leftChild;
342 
343  // Return Right Most Child
344  return this->leftChild->GetRightMostChild();
345  }
346 
352  std::unique_ptr<BST>& GetRightMostChild()
353  {
354  // Cannot get predecessor if no left child exists
355  assert(("GetRightMostChild should not be called if no right child exists.", this->rightChild));
356 
357  if (this->rightChild && !this->rightChild->rightChild)
358  return this->rightChild;
359 
360  return this->rightChild->GetRightMostChild();
361  }
362 
363  void SetLeftChild(std::unique_ptr<BST> bst) { this->leftChild = std::move(bst); }
364  void SetRightChild(std::unique_ptr<BST> bst) { this->rightChild = std::move(bst); }
365 
366  typename std::iterator_traits<IT>::value_type data;
367  std::unique_ptr<BST> leftChild;
368  std::unique_ptr<BST> rightChild;
369  };
370 }
371 
372 #endif // MODULE_DATA_STRUCTURES_BST_HXX
std::size_t MaxHeight() const
static std::unique_ptr< BST > Build(const IT &begin, const IT &end)
void SetRightChild(std::unique_ptr< BST > bst)
bool IsBlanced() const
Value GetData() const
const BST * GetRightChild() const
std::iterator_traits< IT >::value_type Value
const BST * Find(const Value &data)
std::iterator_traits< IT >::value_type data
void SetLeftChild(std::unique_ptr< BST > bst)
static const BST * Remove(std::unique_ptr< BST > &bst, const Value &data)
static std::unique_ptr< BST > BuildFromSorted(const IT &begin, const IT &end)
std::size_t Size() const
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > & GetRightMostChild()
const BST * GetLeftChild() const
std::unique_ptr< BST > rightChild
std::unique_ptr< BST > & GetPredecessor()
BST(const Value &data)
BST operator=(BST &)
bool IsValid(std::unique_ptr< const BST * > &previousNode) const
void Insert(const Value &data)
std::size_t MinHeight() const
bool IsValid() const