SHA_DataStructures::BST< IT, Compare, IsEqual > Class Template Reference

#include <binary_search_tree.hxx>

Public Member Functions

const BSTFind (const Value &data)
 
void Insert (const Value &data)
 
bool IsBlanced () const
 
bool IsValid () const
 
std::size_t MaxHeight () const
 
std::size_t MinHeight () const
 
std::size_t Size () const
 
Value GetData () const
 
const BSTGetLeftChild () const
 
const BSTGetRightChild () const
 

Static Public Member Functions

static std::unique_ptr< BSTBuild (const IT &begin, const IT &end)
 
static std::unique_ptr< BSTBuildFromSorted (const IT &begin, const IT &end)
 
static const BSTRemove (std::unique_ptr< BST > &bst, const Value &data)
 

Private Types

typedef std::iterator_traits< IT >::value_type Value
 

Private Member Functions

 BST (const Value &data)
 
 BST (BST &)
 
BST operator= (BST &)
 
bool IsValid (std::unique_ptr< const BST * > &previousNode) const
 
std::unique_ptr< BST > & GetPredecessor ()
 
std::unique_ptr< BST > & GetRightMostChild ()
 
void SetLeftChild (std::unique_ptr< BST > bst)
 
void SetRightChild (std::unique_ptr< BST > bst)
 

Private Attributes

std::iterator_traits< IT >::value_type data
 
std::unique_ptr< BSTleftChild
 
std::unique_ptr< BSTrightChild
 

Detailed Description

template<typename IT, typename Compare, typename IsEqual>
class SHA_DataStructures::BST< IT, Compare, IsEqual >

A Binary Search Tree, Ordered Tree or Sorted Binary Tree divides all its sub-trees into two segments left sub-tree and right sub-tree that follow these rules:

  • The left sub-tree of a node has key that respect the Compare operator (e.g. less_equal) with its parent node's key.
  • The right sub-tree of a node has key that does not respect the Compare operator with its parent node's key.
  • Duplicates key are inserted of the left sub-tree with respect to the Compare operator.

It keeps their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees.

Advantages
  • Memory efficient and managed.
  • Use principe of binary search for insert, delete and lookup operations.
  • Represent well hierarchies.
  • Get all keys in sorted order by just doing Inorder Traversal.
  • Doing order statistics, closest lower/greater elements, range queries etc. operations are easy.
Drawbacks
  • The shape of the binary search tree depends entirely on the order of insertions and deletions, and can become degenerate.
  • When inserting or searching for an element in a binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.

Definition at line 55 of file binary_search_tree.hxx.

Member Typedef Documentation

template<typename IT , typename Compare , typename IsEqual >
typedef std::iterator_traits<IT>::value_type SHA_DataStructures::BST< IT, Compare, IsEqual >::Value
private

Definition at line 57 of file binary_search_tree.hxx.

Constructor & Destructor Documentation

template<typename IT , typename Compare , typename IsEqual >
SHA_DataStructures::BST< IT, Compare, IsEqual >::BST ( const Value data)
inlineprivate

Definition at line 288 of file binary_search_tree.hxx.

288 : data(data) {}
std::iterator_traits< IT >::value_type data
template<typename IT , typename Compare , typename IsEqual >
SHA_DataStructures::BST< IT, Compare, IsEqual >::BST ( BST< IT, Compare, IsEqual > &  )
inlineprivate

Definition at line 289 of file binary_search_tree.hxx.

289 {} // Not Implemented

Member Function Documentation

template<typename IT , typename Compare , typename IsEqual >
static std::unique_ptr<BST> SHA_DataStructures::BST< IT, Compare, IsEqual >::Build ( const IT &  begin,
const IT &  end 
)
inlinestatic

Build - Construct in a naive way a Binary Search Tree given an unordered sequence of elements.

Parameters
begin,end- ITs to the initial and final positions of the sequence used to build the tree. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Complexity
O(n * m).
Returns
Binary Search Tree pointer to be owned, nullptr if construction failed.

Definition at line 69 of file binary_search_tree.hxx.

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  }
template<typename IT , typename Compare , typename IsEqual >
static std::unique_ptr<BST> SHA_DataStructures::BST< IT, Compare, IsEqual >::BuildFromSorted ( const IT &  begin,
const IT &  end 
)
inlinestatic

BuildFromSorted - Construct a Balanced Binary Search Tree given an ordered sequence of elements.

Parameters
begin,end- ITs to the initial and final positions of the sequence used to build the tree. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Complexity
O(n).
Warning
the algorithm does not check the validity on data order; using this algorithm with unordored data will most likely result in an invalid BST. (Can be checked using IsValid method).
if the compare template argument is inverting the BST (e.g greater_equal), the sequence should be sorted given the same paradigme (e.g. greater value first).
Returns
Binary Search Tree pointer to be owned, nullptr if construction failed.

Definition at line 100 of file binary_search_tree.hxx.

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  }
static std::unique_ptr< BST > BuildFromSorted(const IT &begin, const IT &end)
template<typename IT , typename Compare , typename IsEqual >
const BST* SHA_DataStructures::BST< IT, Compare, IsEqual >::Find ( const Value data)
inline

Find the first a binary search tree for a specific key.

Complexity
O(h), where h may be n in worst case balancement. Equal to log(n) with a balanced tree.
Parameters
data,datavalue to be found within the current BST.
Remarks
this method may not find the data within an invalid binary search tree (cf. IsValid).
Returns
first BST node matching the data.

Definition at line 124 of file binary_search_tree.hxx.

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  }
std::iterator_traits< IT >::value_type data
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
Value SHA_DataStructures::BST< IT, Compare, IsEqual >::GetData ( ) const
inline

Definition at line 283 of file binary_search_tree.hxx.

283 { return this->data; }
std::iterator_traits< IT >::value_type data
template<typename IT , typename Compare , typename IsEqual >
const BST* SHA_DataStructures::BST< IT, Compare, IsEqual >::GetLeftChild ( ) const
inline

Definition at line 284 of file binary_search_tree.hxx.

284 { return this->leftChild.get(); }
std::unique_ptr< BST > leftChild
template<typename IT , typename Compare , typename IsEqual >
std::unique_ptr<BST>& SHA_DataStructures::BST< IT, Compare, IsEqual >::GetPredecessor ( )
inlineprivate

Retrieve the Predecessor unique_ptr reference.

Warning
this method should not be called if no left child exists [assert].
Returns
the predecessor unique_ptr reference.

Definition at line 334 of file binary_search_tree.hxx.

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  }
std::unique_ptr< BST > leftChild
template<typename IT , typename Compare , typename IsEqual >
const BST* SHA_DataStructures::BST< IT, Compare, IsEqual >::GetRightChild ( ) const
inline

Definition at line 285 of file binary_search_tree.hxx.

285 { return this->rightChild.get(); }
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
std::unique_ptr<BST>& SHA_DataStructures::BST< IT, Compare, IsEqual >::GetRightMostChild ( )
inlineprivate

Retrieve the Right Most Child unique_ptr reference.

Warning
this method should not be called if no right child exists [assert].
Returns
the right most child unique_ptr reference.

Definition at line 352 of file binary_search_tree.hxx.

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  }
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
void SHA_DataStructures::BST< IT, Compare, IsEqual >::Insert ( const Value data)
inline

Append a new Binary Search Tree node at the right position with current value.

Complexity
O(n).
Parameters
datadata value to be added to the current BST. Member type Value is the type of the elements in the BST, defined as an alias of its first template parameter Value (IT::Value).
Returns
void.

Definition at line 147 of file binary_search_tree.hxx.

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  }
void SetRightChild(std::unique_ptr< BST > bst)
std::iterator_traits< IT >::value_type data
void SetLeftChild(std::unique_ptr< BST > bst)
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
bool SHA_DataStructures::BST< IT, Compare, IsEqual >::IsBlanced ( ) const
inline

Check if the Binary Search Tree is balanced. Compare the smallest branch to the biggest one to determine the balancement.

Returns
wheter or not the tree is balanced (true) or not (false).

Definition at line 171 of file binary_search_tree.hxx.

171 { return this->MaxHeight() - this->MinHeight() <= 1; }
std::size_t MaxHeight() const
std::size_t MinHeight() const
template<typename IT , typename Compare , typename IsEqual >
bool SHA_DataStructures::BST< IT, Compare, IsEqual >::IsValid ( ) const
inline

Check validity of the Binary Search Tree. Recursively check if subtrees do not violate any of the rules defined by a BST.

Remarks
Using a preordering traversal, it makes sure that:
  • If the node is the left child of its parent, then it must be smaller than (or equal to) the parent and it must pass down the value from its parent to its right subtree to make sure none of the nodes in that subtree is greater than the parent.
  • If the node is the right child of its parent, then it must be larger than the parent and it must pass down the value from its parent to its left subtree to make sure none of the nodes in that subtree is lesser than the parent.
Returns
wheter or not the tree is a valid Binary Search Tree (true) or not (false).

Definition at line 185 of file binary_search_tree.hxx.

186  {
187  auto previousNode = std::unique_ptr<const BST*>(new const BST*);
188  *previousNode = nullptr;
189  return this->IsValid(previousNode);
190  }
template<typename IT , typename Compare , typename IsEqual >
bool SHA_DataStructures::BST< IT, Compare, IsEqual >::IsValid ( std::unique_ptr< const BST< IT, Compare, IsEqual > * > &  previousNode) const
inlineprivate

Check validity of the Binary Search Tree. Recursively check if subtrees do not violate any of the rules defined by a BST.

Parameters
previousNodeunique_ptr reference on const BST* used to keep track of the last node retrieved.
Remarks
Using a preordering traversal, it makes sure that:
  • If the node is the left child of its parent, then it must be smaller than (or equal to) the parent and it must pass down the value from its parent to its right subtree to make sure none of the nodes in that subtree is greater than the parent.
  • If the node is the right child of its parent, then it must be larger than the parent and it must pass down the value from its parent to its left subtree to make sure none of the nodes in that subtree is lesser than the parent.
Returns
wheter or not the tree is a valid Binary Search Tree (true) or not (false).

Definition at line 306 of file binary_search_tree.hxx.

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  }
std::iterator_traits< IT >::value_type data
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
std::size_t SHA_DataStructures::BST< IT, Compare, IsEqual >::MaxHeight ( ) const
inline

Returns the biggest branch height.

Complexity O(n).

Returns
biggest branch height composing the tree.

Definition at line 197 of file binary_search_tree.hxx.

198  {
199  return 1 + std::max(((this->leftChild) ? this->leftChild->MaxHeight() : 0),
200  ((this->rightChild) ? this->rightChild->MaxHeight() : 0));
201  }
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
std::size_t SHA_DataStructures::BST< IT, Compare, IsEqual >::MinHeight ( ) const
inline

Returns the smallest branch height.

Complexity O(n).

Returns
smallest branch height composing the tree.

Definition at line 208 of file binary_search_tree.hxx.

209  {
210  return 1 + std::min(((this->leftChild) ? this->leftChild->MinHeight() : 0),
211  ((this->rightChild) ? this->rightChild->MinHeight() : 0));
212  }
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
BST SHA_DataStructures::BST< IT, Compare, IsEqual >::operator= ( BST< IT, Compare, IsEqual > &  )
inlineprivate

Definition at line 290 of file binary_search_tree.hxx.

290 {} // Not Implemented
template<typename IT , typename Compare , typename IsEqual >
static const BST* SHA_DataStructures::BST< IT, Compare, IsEqual >::Remove ( std::unique_ptr< BST< IT, Compare, IsEqual > > &  bst,
const Value data 
)
inlinestatic

Removes all elements equal [IsEqual() template parameter] to the value from the BST.

Parameters
bstthe unique_ptr owning the bst on which the removal occurs.
datato be removed from the BST. All elements with a value equivalent (IsEqual template parameter) to this are removed from the container. Member type Value is the type of the elements in the BST, defined as an alias of its first template parameter Value (IT::Value).
Warning
this method is destructive and may delete the bst owned by the unique_ptr. Return value may be used for inline checking as: (!Remove(bst, data)) ? tree no longer exist : tree still contains node
Returns
the pointer handler by the bst passed as argument, nullptr if bst has been erased (empty).

Definition at line 227 of file binary_search_tree.hxx.

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  }
static const BST * Remove(std::unique_ptr< BST > &bst, const Value &data)
std::iterator_traits< IT >::value_type data
template<typename IT , typename Compare , typename IsEqual >
void SHA_DataStructures::BST< IT, Compare, IsEqual >::SetLeftChild ( std::unique_ptr< BST< IT, Compare, IsEqual > >  bst)
inlineprivate

Definition at line 363 of file binary_search_tree.hxx.

363 { this->leftChild = std::move(bst); }
std::unique_ptr< BST > leftChild
template<typename IT , typename Compare , typename IsEqual >
void SHA_DataStructures::BST< IT, Compare, IsEqual >::SetRightChild ( std::unique_ptr< BST< IT, Compare, IsEqual > >  bst)
inlineprivate

Definition at line 364 of file binary_search_tree.hxx.

364 { this->rightChild = std::move(bst); }
std::unique_ptr< BST > rightChild
template<typename IT , typename Compare , typename IsEqual >
std::size_t SHA_DataStructures::BST< IT, Compare, IsEqual >::Size ( ) const
inline

Returns the number of nodes composing the BST.

Complexity O(n).

Returns
number of nodes composing the tree.

Definition at line 277 of file binary_search_tree.hxx.

278  {
279  return 1 + ((this->leftChild) ? this->leftChild->Size() : 0)
280  + ((this->rightChild) ? this->rightChild->Size() : 0);
281  }
std::unique_ptr< BST > leftChild
std::unique_ptr< BST > rightChild

Member Data Documentation

template<typename IT , typename Compare , typename IsEqual >
std::iterator_traits<IT>::value_type SHA_DataStructures::BST< IT, Compare, IsEqual >::data
private

Definition at line 366 of file binary_search_tree.hxx.

template<typename IT , typename Compare , typename IsEqual >
std::unique_ptr<BST> SHA_DataStructures::BST< IT, Compare, IsEqual >::leftChild
private

Definition at line 367 of file binary_search_tree.hxx.

template<typename IT , typename Compare , typename IsEqual >
std::unique_ptr<BST> SHA_DataStructures::BST< IT, Compare, IsEqual >::rightChild
private

Definition at line 368 of file binary_search_tree.hxx.


The documentation for this class was generated from the following file: