Advanced Programming - Binary Search Tree
A simple Binary Search Tree implementation for the Advanced Programming 2019-2020 course @ SISSA.
Public Types | Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
APbst::bst< KT, VT, cmp > Class Template Reference

Class that implements a Binary Search Tree. More...

#include <BST.hpp>

Public Types

using key_type = KT
 The Key type of the Node of the tree.
 
using mapped_type = VT
 The Value type of the Node of the tree.
 
using pair_type = typename std::pair< const KT, VT >
 The Pair type of the tree, i.e. std::pair<const Key,Value>.
 
using node_type = typename APutils::Node< pair_type >
 The Node type of the tree, i.e. Node<Pair>.
 
using iterator = typename APutils::__iterator< node_type, pair_type >
 The non-const iterator type.
 
using const_iterator = typename APutils::__iterator< node_type, const pair_type >
 The const iterator type.
 

Public Member Functions

 bst () noexcept
 Empty constructor. More...
 
 bst (cmp x) noexcept
 Empty constructor with an explicit comparison ("less than") operation. More...
 
 bst (const bst &t)
 Copy constructor. More...
 
 bst (bst &&t) noexcept=default
 Move constructor. More...
 
bstoperator= (const bst &t)
 Copy assignment for bst. More...
 
bstoperator= (bst &&t) noexcept=default
 Move assignment for bst. More...
 
std::pair< iterator, bool > insert (const pair_type &x)
 Inserts a APutils::Node by copying it in the tree, if not already present. More...
 
std::pair< iterator, bool > insert (pair_type &&x)
 Inserts a APutils::Node by moving it in the tree, if not already present. More...
 
template<class... Types>
std::pair< iterator, bool > emplace (Types &&... args)
 Inserts a APutils::Node constructed in-place. More...
 
void clear () noexcept
 Clears the content of the tree. More...
 
iterator begin () noexcept
 Returns an iterator to the left-most APutils::Node. More...
 
const_iterator begin () const noexcept
 Returns a const_iterator to the left-most APutils::Node. More...
 
const_iterator cbegin () const noexcept
 The const version of begin(), to be used when a const_iterator is needed. More...
 
iterator end () noexcept
 Returns an iterator to one-past the last element. More...
 
const_iterator end () const noexcept
 Returns a const_iterator to one-past the last element. More...
 
const_iterator cend () const noexcept
 The const version of end(), to be used when a const_iterator is needed. More...
 
iterator find (const key_type &x)
 Finds a APutils::Node and possibly change its value. More...
 
const_iterator find (const key_type &x) const
 Finds if a node just exists. More...
 
void balance ()
 Balances the tree. More...
 
mapped_typeoperator[] (const key_type &x)
 Subscripting operator performing a copy. More...
 
mapped_typeoperator[] (key_type &&x)
 Subscripting operator performing a move. More...
 
void printRawTree (std::stringstream &ss)
 Prints the tree in an easy way. More...
 
void erase (const key_type &x)
 Removes the element (if it exists) with Key x. More...
 

Private Member Functions

APutils::Node< std::pair< const KT, VT > > * __begin () const
 Internal helper function for begin(). More...
 
APutils::Node< std::pair< const KT, VT > > * __find (const KT &x) const
 Internal helper function for find(). More...
 
void __copy (const bst &t, std::unique_ptr< APutils::Node< std::pair< const KT, VT >>> &a)
 Internal helper function for the copy operations. More...
 
void __balance (std::vector< std::pair< const KT, VT >> &v, long long int a, long long int b)
 Internal helper function for balance(). More...
 

Private Attributes

cmp op
 Operator of comparison ("less than") for the Key type.
 
std::unique_ptr< APutils::Node< std::pair< const KT, VT > > > root
 The root Node of the tree.
 

Friends

std::ostream & operator<< (std::ostream &os, const bst &x)
 Put-to operator that prints the tree. More...
 

Detailed Description

template<typename KT, typename VT, typename cmp = std::less<KT>>
class APbst::bst< KT, VT, cmp >

Class that implements a Binary Search Tree.

This class takes two compulsory template parameters, KT and VT, and an optional one (cmp). The compulsory ones are, respectively, the Key type and the Value type of the Nodes of the tree, while cmp is the "less than" operator for the particular KT in use.

Example:

APbst::bst<std::string,int> personAge{};

As this is an exam project, some internal members are documented as well.

See also
op

Constructor & Destructor Documentation

◆ bst() [1/4]

template<typename KT , typename VT , typename cmp = std::less<KT>>
APbst::bst< KT, VT, cmp >::bst ( )
inlinenoexcept

Empty constructor.

It creates an empty tree with no Nodes and with the default "less than" operation.

◆ bst() [2/4]

template<typename KT , typename VT , typename cmp = std::less<KT>>
APbst::bst< KT, VT, cmp >::bst ( cmp  x)
inlineexplicitnoexcept

Empty constructor with an explicit comparison ("less than") operation.

Parameters
xThe comparison ("less than") operator.

It creates an empty tree with no Nodes and with the specified "less than" operation.

◆ bst() [3/4]

template<typename KT , typename VT , typename cmp = std::less<KT>>
APbst::bst< KT, VT, cmp >::bst ( const bst< KT, VT, cmp > &  t)
inlineexplicit

Copy constructor.

Parameters
tThe tree to be copied.

It creates a new tree by performing a deep copy of the tree t.

See also
bst::operator=

◆ bst() [4/4]

template<typename KT , typename VT , typename cmp = std::less<KT>>
APbst::bst< KT, VT, cmp >::bst ( bst< KT, VT, cmp > &&  t)
defaultnoexcept

Move constructor.

Parameters
tThe tree to be moved.

It creates a new tree by moving the tree t.

See also
bst::operator=

Member Function Documentation

◆ __balance()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::__balance ( std::vector< std::pair< const KT, VT >> &  v,
long long int  a,
long long int  b 
)
inlineprivate

Internal helper function for balance().

Parameters
vA vector that contains all the tree pairs.
aThe index of the first vector element to insert in the tree.
bThe index of the last vector element to insert in the tree.

This function emplaces all the Node pairs contained in v in a balanced fashion, by starting with the middle element and then recursively calling itself.

See also
balance()

◆ __begin()

template<typename KT , typename VT , typename cmp = std::less<KT>>
APutils::Node<std::pair<const KT, VT> >* APbst::bst< KT, VT, cmp >::__begin ( ) const
inlineprivate

Internal helper function for begin().

This function finds the leftmost Node of the tree and it returns a raw pointer to the leftmost Node itself.

See also
begin()
cbegin()

◆ __copy()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::__copy ( const bst< KT, VT, cmp > &  t,
std::unique_ptr< APutils::Node< std::pair< const KT, VT >>> &  a 
)
inlineprivate

Internal helper function for the copy operations.

Parameters
tThe tree to be copied.
aThe Node to be copied.

This function recursively copies a tree by performing a deep copy of all of its Nodes.

See also
bst()
bst::operator=

◆ __find()

template<typename KT , typename VT , typename cmp = std::less<KT>>
APutils::Node<std::pair<const KT, VT> >* APbst::bst< KT, VT, cmp >::__find ( const KT &  x) const
inlineprivate

Internal helper function for find().

This function finds the Node with key x and it returns a raw pointer to the found Node.

See also
find()

◆ balance()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::balance ( )
inline

Balances the tree.

Reshuffles the nodes in the tree by trying to minimize its depth.

◆ begin() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
iterator APbst::bst< KT, VT, cmp >::begin ( )
inlinenoexcept

Returns an iterator to the left-most APutils::Node.

This function finds the leftmost Node of the tree and it returns an iterator to the leftmost Node itself.

See also
cbegin()
end()

◆ begin() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
const_iterator APbst::bst< KT, VT, cmp >::begin ( ) const
inlinenoexcept

Returns a const_iterator to the left-most APutils::Node.

This function finds the leftmost Node of the tree and it returns a const_iterator to the leftmost Node itself.

See also
cbegin()
end()

◆ cbegin()

template<typename KT , typename VT , typename cmp = std::less<KT>>
const_iterator APbst::bst< KT, VT, cmp >::cbegin ( ) const
inlinenoexcept

The const version of begin(), to be used when a const_iterator is needed.

See also
begin()
cend()

◆ cend()

template<typename KT , typename VT , typename cmp = std::less<KT>>
const_iterator APbst::bst< KT, VT, cmp >::cend ( ) const
inlinenoexcept

The const version of end(), to be used when a const_iterator is needed.

See also
end()
cbegin()

◆ clear()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::clear ( )
inlinenoexcept

Clears the content of the tree.

Since reset() resets root to nullptr and then deletes the previously managed object, the distructor of APutils::Node is called on each APutils::Node of the tree.

◆ emplace()

template<typename KT , typename VT , typename cmp = std::less<KT>>
template<class... Types>
std::pair<iterator,bool> APbst::bst< KT, VT, cmp >::emplace ( Types &&...  args)
inline

Inserts a APutils::Node constructed in-place.

Parameters
argsThe arguments for the Pair constructor.

Inserts a new APutils::Node into the tree by constructing it in-place.

This function forwards the arguments args to the constructor of Pair, and if the tree does not contain an element with the same Key it inserts the Pair itself.

See also
insert()

◆ end() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
iterator APbst::bst< KT, VT, cmp >::end ( )
inlinenoexcept

Returns an iterator to one-past the last element.

It returns an interator to nullptr.

See also
cend()
begin()

◆ end() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
const_iterator APbst::bst< KT, VT, cmp >::end ( ) const
inlinenoexcept

Returns a const_iterator to one-past the last element.

It returns a const_interator to nullptr.

See also
cend()
begin()

◆ erase()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::erase ( const key_type x)
inline

Removes the element (if it exists) with Key x.

Parameters
xThe Key to be removed.

If the Key does not exist in the tree, this function does nothing.

◆ find() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
iterator APbst::bst< KT, VT, cmp >::find ( const key_type x)
inline

Finds a APutils::Node and possibly change its value.

Parameters
xThe Key to look for.

Finds a given Key. If the Key is present, returns an APutils::__iterator to the proper APutils::Node, end() otherwise.

◆ find() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
const_iterator APbst::bst< KT, VT, cmp >::find ( const key_type x) const
inline

Finds if a node just exists.

Parameters
xThe Key to look for.

Finds a given Key. If the Key is present, returns an APutils::__iterator to the proper APutils::Node, end() otherwise.

◆ insert() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
std::pair<iterator, bool> APbst::bst< KT, VT, cmp >::insert ( const pair_type x)
inline

Inserts a APutils::Node by copying it in the tree, if not already present.

Parameters
xThe values of the Key and the Value to be put in the APutils::Node.

This function inserts a new APutils::Node in the current tree, and it returns a pair of an __iterator (pointing to the APutils::Node) and a bool. The bool is true if a new APutils::Node has been allocated, false otherwise (i.e., the Key was already present in the tree).

See also
emplace()

◆ insert() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
std::pair<iterator, bool> APbst::bst< KT, VT, cmp >::insert ( pair_type &&  x)
inline

Inserts a APutils::Node by moving it in the tree, if not already present.

Parameters
xThe values of the Key and the Value to be put in the APutils::Node.

This function inserts a new APutils::Node in the current tree, and it returns a pair of an __iterator (pointing to the APutils::Node) and a bool. The bool is true if a new APutils::Node has been allocated, false otherwise (i.e., the Key was already present in the tree).

See also
emplace()

◆ operator=() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
bst& APbst::bst< KT, VT, cmp >::operator= ( const bst< KT, VT, cmp > &  t)
inline

Copy assignment for bst.

Parameters
tThe tree to be copied.

It creates a new tree by performing a deep copy of the tree t.

See also
bst()

◆ operator=() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
bst& APbst::bst< KT, VT, cmp >::operator= ( bst< KT, VT, cmp > &&  t)
defaultnoexcept

Move assignment for bst.

Parameters
tThe tree to be moved.

It creates a new tree by moving the tree t.

See also
bst()

◆ operator[]() [1/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
mapped_type& APbst::bst< KT, VT, cmp >::operator[] ( const key_type x)
inline

Subscripting operator performing a copy.

Parameters
xThe Key to look for.

Returns a reference to the value corresponding to the Key x, performing an insertion if such Key does not already exist.

◆ operator[]() [2/2]

template<typename KT , typename VT , typename cmp = std::less<KT>>
mapped_type& APbst::bst< KT, VT, cmp >::operator[] ( key_type &&  x)
inline

Subscripting operator performing a move.

Parameters
xThe Key to look for.

Returns a reference to the value corresponding to the Key x, performing an insertion if such Key does not already exist.

◆ printRawTree()

template<typename KT , typename VT , typename cmp = std::less<KT>>
void APbst::bst< KT, VT, cmp >::printRawTree ( std::stringstream &  ss)
inline

Prints the tree in an easy way.

Parameters
ssThe string stream.

This function is mainly used for tests only, as it prints the tree in a format that is easier to check in automatic tests.

E.g., if a tree contains Key:Value pairs 1:1, 2:2, 3:3, etc., tree.printRawTree(ss) will fill ss with a string that looks like

1 : 1
2 : 2
3 : 3
...

Friends And Related Function Documentation

◆ operator<<

template<typename KT , typename VT , typename cmp = std::less<KT>>
std::ostream& operator<< ( std::ostream &  os,
const bst< KT, VT, cmp > &  x 
)
friend

Put-to operator that prints the tree.

Parameters
osThe stream on which the print has to be made.
xThe tree to be printed.

This function assumes that the Key and the Value have a corresponding overloaded put-to operator; if this is not the case, it is a user's task to implement it before including BST.hpp.

E.g., in order to print a std::vector Value, one could write

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "[";
    auto itStop = v.cend();
    for (auto it = v.cbegin(); it != itStop; ++it) {
        os << *it;
        if (it != itStop - 1) os << ", ";
    }
    os << "]";
    return os;
}

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