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

#include <binary_search_tree.hxx>

Public Member Functions
const BST *	Find (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 BST *	GetLeftChild () const
const BST *	GetRightChild () const

Static Public Member Functions
static std::unique_ptr< BST >	Build (const IT &begin, const IT &end)
static std::unique_ptr< BST >	BuildFromSorted (const IT &begin, const IT &end)
static const BST *	Remove (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< BST >	leftChild
std::unique_ptr< BST >	rightChild

Detailed Description

template<typename IT, typename Compare, typename IsEqual>
class huc::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 huc::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 >

huc::BST< IT, Compare, IsEqual >::BST ( const Value &  data )

inlineprivate

Definition at line 288 of file binary_search_tree.hxx.

: data(data) {}

template<typename IT , typename Compare , typename IsEqual >

huc::BST< IT, Compare, IsEqual >::BST ( BST< IT, Compare, IsEqual > &  )

inlineprivate

Definition at line 289 of file binary_search_tree.hxx.

{}           // Not Implemented

Member Function Documentation

template<typename IT , typename Compare , typename IsEqual >

static std::unique_ptr<BST> huc::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.

      {
        if (begin >= end)
          return  nullptr;

        // Create root node
        auto root = std::unique_ptr<BST>(new BST(*begin));

        // Insert all remaining elements within the tree
        for (auto it = begin + 1; it != end; ++it)
          root->Insert(*it);

        return root;
      }

template<typename IT , typename Compare , typename IsEqual >

static std::unique_ptr<BST> huc::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.

      {
        if (begin >= end)
          return nullptr;

        const auto middle = begin + (std::distance(begin,end) / 2);
        auto root = std::unique_ptr<BST>(new BST(*middle));

        // Recursively insert both children
        root->SetLeftChild(std::move(BuildFromSorted(begin, middle)));
        root->SetRightChild(std::move(BuildFromSorted(middle + 1, end)));

        return root;
      }

template<typename IT , typename Compare , typename IsEqual >

const BST* huc::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,data

value 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.

      {
        // Key found returns node
        if (IsEqual()(this->data, data))
          return this;

        // Key is less than current node - search in left subtree
        if (Compare()(data, this->data))
          return this->leftChild ? this->leftChild->Find(data) : nullptr;

        // Search in right subtree
        return this->rightChild ? this->rightChild->Find(data) : nullptr;
      }

template<typename IT , typename Compare , typename IsEqual >

Value huc::BST< IT, Compare, IsEqual >::GetData ( ) const

inline

Definition at line 283 of file binary_search_tree.hxx.

{ return this->data; }

template<typename IT , typename Compare , typename IsEqual >

const BST* huc::BST< IT, Compare, IsEqual >::GetLeftChild ( ) const

inline

Definition at line 284 of file binary_search_tree.hxx.

{ return this->leftChild.get(); }

template<typename IT , typename Compare , typename IsEqual >

std::unique_ptr<BST>& huc::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.

      {
        // Cannot get predecessor if no left child exists
        assert(("GetPredecessor should not be called if no left child exists.", this->leftChild));

        // Left child is the predecessor
        if (!this->leftChild->rightChild)
          return this->leftChild;

        // Return Right Most Child
        return this->leftChild->GetRightMostChild();
      }

template<typename IT , typename Compare , typename IsEqual >

const BST* huc::BST< IT, Compare, IsEqual >::GetRightChild ( ) const

inline

Definition at line 285 of file binary_search_tree.hxx.

{ return this->rightChild.get(); }

template<typename IT , typename Compare , typename IsEqual >

std::unique_ptr<BST>& huc::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.

      {
        // Cannot get predecessor if no left child exists
        assert(("GetRightMostChild should not be called if no right child exists.", this->rightChild));

        if (this->rightChild && !this->rightChild->rightChild)
          return this->rightChild;

        return this->rightChild->GetRightMostChild();
      }

template<typename IT , typename Compare , typename IsEqual >

void huc::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

data	data 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.

      {
        // Key is lower or equal than current root - Insert on the left side
        if (Compare()(data, this->data))
        {
          if (!this->leftChild)
            this->SetLeftChild(std::move(std::unique_ptr<BST>(new BST(data))));
          else
            this->leftChild->Insert(data);
        }
        // Key is greater than current root - Insert on the right side
        else
        {
          if (!this->rightChild)
            this->SetRightChild(std::move(std::unique_ptr<BST>(new BST(data))));
          else
            this->rightChild->Insert(data);
        }
      }

template<typename IT , typename Compare , typename IsEqual >

bool huc::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.

{ return this->MaxHeight() - this->MinHeight() <= 1; }

template<typename IT , typename Compare , typename IsEqual >

bool huc::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.

      {
        auto previousNode = std::unique_ptr<const BST*>(new const BST*);
        *previousNode = nullptr;
        return this->IsValid(previousNode);
      }

template<typename IT , typename Compare , typename IsEqual >

bool huc::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

previousNode

unique_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.

      {
        // Recurse on left child without breaking if not failing
        if (this->leftChild &&!this->leftChild->IsValid(previousNode))
          return false;

        // First node retrieve - assign
        if (!*previousNode)
          *previousNode = this;
        // Previous data does not compare well to the current one - BST not valid
        else if (!Compare()((*previousNode)->data, this->data))
          return false;

        // Set current node
        *previousNode = this;

        // Recurse on right child
        if (this->rightChild && !this->rightChild->IsValid(previousNode))
          return false;

        return true;
      }

template<typename IT , typename Compare , typename IsEqual >

std::size_t huc::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.

      {
        return 1 + std::max(((this->leftChild) ? this->leftChild->MaxHeight() : 0),
                            ((this->rightChild) ? this->rightChild->MaxHeight() : 0));
      }

template<typename IT , typename Compare , typename IsEqual >

std::size_t huc::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.

      {
        return 1 + std::min(((this->leftChild) ? this->leftChild->MinHeight() : 0),
                            ((this->rightChild) ? this->rightChild->MinHeight() : 0));
      }

template<typename IT , typename Compare , typename IsEqual >

BST huc::BST< IT, Compare, IsEqual >::operator= ( BST< IT, Compare, IsEqual > &  )

inlineprivate

Definition at line 290 of file binary_search_tree.hxx.

{} // Not Implemented

template<typename IT , typename Compare , typename IsEqual >

static const BST* huc::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

bst	the unique_ptr owning the bst on which the removal occurs.
data	to 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.

      {
        // Break on empty unique_ptr
        if (!bst)
          return nullptr;

        // Reach node matching the value
        if (!IsEqual()(bst->data, data))
        {
          if (Compare()(data, bst->data))
            Remove(bst->leftChild, data);
          else
            Remove(bst->rightChild, data);
        }
        // Proceed removal
        else
        {
          // Recursively delete all subnodes containing the same value
          if (bst->leftChild && IsEqual()(bst->data, bst->leftChild->data))
            Remove(bst->leftChild, data);

          // No child - Simply remove node
          if (!bst->leftChild && !bst->rightChild)
            bst.reset();
          // Both children:
          // - Swap node value with its predecessor
          // - Remove predecessor node and replace it with its child
          else if (bst->leftChild && bst->rightChild)
          {
            auto& predecessor = bst->GetPredecessor();
            std::swap(bst->data, predecessor->data);
            predecessor.reset(predecessor->leftChild.release());
          }
          // Left node is unique child - remove node and replace it with its child.
          else if (bst->leftChild)
            bst.reset(bst->leftChild.release());
          // Right node is unique child - remove node and replace it with its child.
          else if (bst->rightChild)
            bst.reset(bst->rightChild.release());
        }

        // Return pointer handled by bst.
        return bst.get();
      }

template<typename IT , typename Compare , typename IsEqual >

void huc::BST< IT, Compare, IsEqual >::SetLeftChild ( std::unique_ptr< BST< IT, Compare, IsEqual > >  bst )

inlineprivate

Definition at line 363 of file binary_search_tree.hxx.

{ this->leftChild = std::move(bst); }

template<typename IT , typename Compare , typename IsEqual >

void huc::BST< IT, Compare, IsEqual >::SetRightChild ( std::unique_ptr< BST< IT, Compare, IsEqual > >  bst )

inlineprivate

Definition at line 364 of file binary_search_tree.hxx.

{ this->rightChild = std::move(bst); }

template<typename IT , typename Compare , typename IsEqual >

std::size_t huc::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.

      {
        return 1 + ((this->leftChild) ? this->leftChild->Size() : 0)
                 + ((this->rightChild) ? this->rightChild->Size() : 0);
      }

Member Data Documentation

template<typename IT , typename Compare , typename IsEqual >

std::iterator_traits<IT>::value_type huc::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> huc::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> huc::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:

• binary_search_tree.hxx