A generic binary search tree.
More...
#include <agrum/tools/core/binSearchTree.h>
template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
class gum::BinSearchTree< Val, Cmp, Node >
A generic binary search tree.
- Template Parameters
-
| Val | The values type to store in the binary search tree. |
| Cmp | The comparator for sorting the binary search tree. |
| Node | The nodes type used to store values in the binary search tree. |
Definition at line 64 of file binSearchTree.h.
◆ const_iterator
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ iterator
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ BinSearchTree() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Basic constructor: returns an empty binary search tree.
- Parameters
-
| uniqueness_policy | Allows (false) or disables (true) the binary tree uniqueness. |
It is possible for the binary tree to have multiple instances of the same value within the tree.
◆ BinSearchTree() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Copy constructor.
- Parameters
-
◆ ~BinSearchTree()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ _eraseWithTwoChildren_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ _updateEraseIterators_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Update all iterators when a given node is deleted.
- Parameters
-
| node | The node that is erased. |
◆ begin() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ begin() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ clear()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ contains()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ copy_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
A method for recursively copying the contents of a BinSearchTree.
- Warning
- This function produces a tree with precisely the same structure as that passed in argument (node). Hence, this should be used only when copying binary search trees storing data w.r.t. the same weak order Cmp.
- Parameters
-
| root_from | The root of the tree to be copied. |
| parent | The node that should be the parent of the copy. |
| dir | The direction of the edge parent->copy. |
◆ deleteSubTree_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
A method for recursively deleting a subtree of the gum::BinSearchTree.
Note that this method does not update the iterators pointing to nodes of the subtree. These should be cleared before deleteSubTree_ is called.
- Parameters
-
| node | The root of the subtree to delete. |
◆ empty()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ end() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ end() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ erase() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Erase the leftmost node with the given (key,val) pair.
- Parameters
-
- Exceptions
-
| NotFound | Raised if we could not find the node. |
◆ erase() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Erase the node pointed to by the iterator.
If we could not find the node, then nothing happens. In particular, no exception is raised.
- Parameters
-
| iter | The iterator pointing toward the value to remove. |
◆ erase_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Erase the node passed in argument.
- Parameters
-
◆ getNode_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the node containing a given value.
- Parameters
-
| val | The value of the node to return. |
- Returns
- Returns the node containing a given value (0 if the value cannot be found).
◆ insert()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Creates a copy of the value, insert it in the tree and returns the copy value.
When elements are inserted into binary search trees, this is actually copies that are inserted. Thus, the method returns the newly created copy, so that the user may reference it.
- Parameters
-
| val | The value added by copy. |
- Returns
- Returns a reference over copy added in the gum::BinSearchTree.
- Exceptions
-
| DuplicateElement | Raised if the binary tree already contains the value and the uniqueness property is set to true. |
◆ insert_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value.
When elements are inserted into gum::BinSearchTree, this is actually copies that are inserted. Thus, the method returns the node containing the newly created copy, so that the user may reference the new copy.
- Warning
- this method is actually the implementation of method insert. It is used to speed-up insertions in terminal classes such as AVL trees.
- Exceptions
-
| DuplicateElement | exception is raised if the binary tree already contains the value and the uniqueness property is set to true. |
- Parameters
-
| val | The value added by copy. |
- Returns
- Returns the node containing the newly created copy.
◆ maxNode_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the greatest node w.r.t.
order Cmp in the subtree rooted at node.
- Parameters
-
| node | The root for looking for the the greatest node. |
- Returns
- Returns the greatest node.
◆ maxValue()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the value of the rightmost node with the maximal key in the tree.
- Returns
- Returns the value of the rightmost node with the maximal key in the tree.
- Exceptions
-
◆ minNode_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the smallest node w.r.t.
order Cmp in the subtree rooted at node.
- Parameters
-
| node | The root for looking for the the smallest node. |
- Returns
- Returns the smallest node.
◆ minValue()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the value of the leftmost node with the minimal key in the tree.
- Returns
- Returns the value of the leftmost node with the minimal key in the tree.
- Exceptions
-
◆ operator=()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ prevNode_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the previous node according to weak ordering Cmp.
- Parameters
-
| node | The node for which the previous node is returned. |
- Returns
- Returns the previous node according to the weak ordering Cmp.
◆ rbegin() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Reverse iterator.
- Returns
- Returns an iterator at the beginning of the gum::BinSearchTree for reverse iteration.
◆ rbegin() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Reverse iterator.
- Returns
- Returns an iterator at the beginning of the gum::BinSearchTree for reverse iteration.
◆ rend() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Reverse end iterator.
- Returns
- Returns an iterator at the end of the gum::BinSearchTree for reverse iteration.
◆ rend() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Reverse end iterator.
- Returns
- Returns an iterator at the end of the gum::BinSearchTree for reverse iteration.
◆ root() [1/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns an iterator at the root of the tree.
- Returns
- Returns an iterator at the root of the tree.
◆ root() [2/2]
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns an iterator at the root of the tree.
- Returns
- Returns an iterator at the root of the tree.
◆ rootValue()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the value of the root of the tree.
- Returns
- Returns the value of the root of the tree.
- Exceptions
-
◆ setUniquenessPolicy()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Enables the user to change dynamically the policy for checking whether there can exist several identical elements in the binary tree.
By default, trees can store several times the same element. However, for some applications, we should ensure that all elements in the binary search tree are distinct.
- Warning
- When setting the policy to "uniqueness", the function does not check whether the tree already contains identical elements. It thus only ensures that elements inserted from now on do not already belong to the tree.
- Parameters
-
| new_policy | Set the uniqueness policy on or off. |
◆ size()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the number of elements in the binary search tree.
- Returns
- Returns the number of elements in the binary search tree.
◆ succNode_()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the next node according to the weak ordering Cmp.
- Parameters
-
| node | The node for which the sucessor is returned. |
- Returns
- Returns the next node according to the weak ordering Cmp.
◆ toString()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Displays the content of the tree, in increasing order w.r.t.
Cmp.
- Returns
- Returns the content of the tree in a string.
◆ uniquenessPolicy()
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Returns the current uniqueness policy.
- Returns
- Returns the current uniqueness policy.
◆ BinSearchTreeIterator< Val, Cmp, Node >
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ cmp_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ iter_end_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
Pseudo static iterator.
The end and rend iterators are constructed only once per binary search tree so as to optimize for(iter = begin();iter != end(); iter++) loops: this will avoid creating objects end and rend each time we pass in the loop.
Definition at line 314 of file binSearchTree.h.
◆ iterator_list_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
The list of iterators pointing to the binary search tree.
Definition at line 297 of file binSearchTree.h.
◆ nb_elements_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
The number of elements stored in the tree.
Definition at line 304 of file binSearchTree.h.
◆ root_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
◆ uniqueness_policy_
template<typename Val , class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
The uniqueness property: whether the same value can appear multiple times.
Definition at line 301 of file binSearchTree.h.
The documentation for this class was generated from the following file:
Collaboration diagram for gum::BinSearchTree< Val, Cmp, Node >: