Advanced Programming - Binary Search Tree
A simple Binary Search Tree implementation for the Advanced Programming 2019-2020 course @ SISSA.
|
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... | |
bst & | operator= (const bst &t) |
Copy assignment for bst. More... | |
bst & | operator= (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_type & | operator[] (const key_type &x) |
Subscripting operator performing a copy. More... | |
mapped_type & | operator[] (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... | |
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.
|
inlinenoexcept |
Empty constructor.
It creates an empty tree with no Nodes and with the default "less than" operation.
|
inlineexplicitnoexcept |
Empty constructor with an explicit comparison ("less than") operation.
x | The comparison ("less than") operator. |
It creates an empty tree with no Nodes and with the specified "less than" operation.
|
inlineexplicit |
Copy constructor.
t | The tree to be copied. |
It creates a new tree by performing a deep copy of the tree t.
|
defaultnoexcept |
Move constructor.
t | The tree to be moved. |
It creates a new tree by moving the tree t.
|
inlineprivate |
Internal helper function for balance().
v | A vector that contains all the tree pairs. |
a | The index of the first vector element to insert in the tree. |
b | The 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.
|
inlineprivate |
|
inlineprivate |
Internal helper function for the copy operations.
t | The tree to be copied. |
a | The Node to be copied. |
This function recursively copies a tree by performing a deep copy of all of its Nodes.
|
inlineprivate |
|
inline |
Balances the tree.
Reshuffles the nodes in the tree by trying to minimize its depth.
|
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.
|
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.
|
inlinenoexcept |
|
inlinenoexcept |
|
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.
|
inline |
Inserts a APutils::Node constructed in-place.
args | The 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.
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
Removes the element (if it exists) with Key
x.
x | The Key to be removed. |
If the Key
does not exist in the tree, this function does nothing.
|
inline |
Finds a APutils::Node and possibly change its value.
x | The Key to look for. |
Finds a given Key
. If the Key
is present, returns an APutils::__iterator to the proper APutils::Node, end() otherwise.
|
inline |
Finds if a node just exists.
x | The Key to look for. |
Finds a given Key
. If the Key
is present, returns an APutils::__iterator to the proper APutils::Node, end() otherwise.
|
inline |
Inserts a APutils::Node by copying it in the tree, if not already present.
x | The 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).
|
inline |
Inserts a APutils::Node by moving it in the tree, if not already present.
x | The 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).
|
inline |
|
defaultnoexcept |
|
inline |
Subscripting operator performing a copy.
x | The 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.
|
inline |
Subscripting operator performing a move.
x | The 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.
|
inline |
Prints the tree in an easy way.
ss | The 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 ...
|
friend |
Put-to operator that prints the tree.
os | The stream on which the print has to be made. |
x | The 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; }