TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
binary_search_tree< T > Class Template Reference

The Binary Search Tree class. More...

Collaboration diagram for binary_search_tree< T >:
[legend]

Classes

struct  bst_node
 A struct to represent a node in the Binary Search Tree. More...
 

Public Member Functions

 binary_search_tree ()
 Construct a new Binary Search Tree object.
 
bool insert (T new_value)
 Insert a new value into the BST.
 
bool remove (T rm_value)
 Remove a specified value from the BST.
 
bool contains (T value)
 Check if a value is in the BST.
 
bool find_min (T &ret_value)
 Find the smallest value in the BST.
 
bool find_max (T &ret_value)
 Find the largest value in the BST.
 
std::size_t size ()
 Get the number of values in the BST.
 
std::vector< T > get_elements_inorder ()
 Get all values of the BST in in-order order.
 
std::vector< T > get_elements_preorder ()
 Get all values of the BST in pre-order order.
 
std::vector< T > get_elements_postorder ()
 Get all values of the BST in post-order order.
 

Private Member Functions

bool find_max (std::unique_ptr< bst_node > &node, T &ret_value)
 Recursive function to find the maximum value in the BST.
 
bool find_min (std::unique_ptr< bst_node > &node, T &ret_value)
 Recursive function to find the minimum value in the BST.
 
bool insert (std::unique_ptr< bst_node > &node, T new_value)
 Recursive function to insert a value into the BST.
 
bool remove (std::unique_ptr< bst_node > &parent, std::unique_ptr< bst_node > &node, T rm_value)
 Recursive function to remove a value from the BST.
 
bool contains (std::unique_ptr< bst_node > &node, T value)
 Recursive function to check if a value is in the BST.
 
void traverse_inorder (std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
 Recursive function to traverse the tree in in-order order.
 
void traverse_preorder (std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
 Recursive function to traverse the tree in pre-order order.
 
void traverse_postorder (std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
 Recursive function to traverse the tree in post-order order.
 

Private Attributes

std::unique_ptr< bst_node > root_
 
std::size_t size_ = 0
 

Detailed Description

template<class T>
class binary_search_tree< T >

The Binary Search Tree class.

Template Parameters
TThe type of the binary search tree key.

Definition at line 20 of file binary_search_tree2.cpp.

Constructor & Destructor Documentation

◆ binary_search_tree()

template<class T >
binary_search_tree< T >::binary_search_tree ( )
inline

Construct a new Binary Search Tree object.

Definition at line 247 of file binary_search_tree2.cpp.

247 {
248 root_ = nullptr;
249 size_ = 0;
250 }
binary_search_tree::size_
std::size_t size_
Definition binary_search_tree2.cpp:43
binary_search_tree::root_
std::unique_ptr< bst_node > root_
Definition binary_search_tree2.cpp:42

Member Function Documentation

◆ contains() [1/2]

template<class T >
bool binary_search_tree< T >::contains ( std::unique_ptr< bst_node > & node,
T value )
inlineprivate

Recursive function to check if a value is in the BST.

Parameters
nodeThe node to search from.
valueThe value to find.
Returns
true If the value was found in the BST.
false Otherwise.

Definition at line 177 of file binary_search_tree2.cpp.

177 {
178 if (!node) {
179 return false;
180 }
181
182 if (value < node->value) {
183 return contains(node->left, value);
184 } else if (value > node->value) {
185 return contains(node->right, value);
186 } else {
187 return true;
188 }
189 }
binary_search_tree::contains
bool contains(std::unique_ptr< bst_node > &node, T value)
Recursive function to check if a value is in the BST.
Definition binary_search_tree2.cpp:177

◆ contains() [2/2]

template<class T >
bool binary_search_tree< T >::contains ( T value)
inline

Check if a value is in the BST.

Parameters
valueThe value to find.
Returns
true If value is in the BST.
false Otherwise.

Definition at line 289 of file binary_search_tree2.cpp.

289{ return contains(root_, value); }

◆ find_max() [1/2]

template<class T >
bool binary_search_tree< T >::find_max ( std::unique_ptr< bst_node > & node,
T & ret_value )
inlineprivate

Recursive function to find the maximum value in the BST.

Parameters
nodeThe node to search from.
ret_valueVariable to hold the maximum value.
Returns
true If the maximum value was successfully found.
false Otherwise.

Definition at line 53 of file binary_search_tree2.cpp.

53 {
54 if (!node) {
55 return false;
56 } else if (!node->right) {
57 ret_value = node->value;
58 return true;
59 }
60 return find_max(node->right, ret_value);
61 }
binary_search_tree::find_max
bool find_max(std::unique_ptr< bst_node > &node, T &ret_value)
Recursive function to find the maximum value in the BST.
Definition binary_search_tree2.cpp:53

◆ find_max() [2/2]

template<class T >
bool binary_search_tree< T >::find_max ( T & ret_value)
inline

Find the largest value in the BST.

Parameters
ret_valueVariable to hold the maximum value.
Returns
true If maximum value was successfully found.
false Otherwise.

Definition at line 307 of file binary_search_tree2.cpp.

307{ return find_max(root_, ret_value); }

◆ find_min() [1/2]

template<class T >
bool binary_search_tree< T >::find_min ( std::unique_ptr< bst_node > & node,
T & ret_value )
inlineprivate

Recursive function to find the minimum value in the BST.

Parameters
nodeThe node to search from.
ret_valueVariable to hold the minimum value.
Returns
true If the minimum value was successfully found.
false Otherwise.

Definition at line 71 of file binary_search_tree2.cpp.

71 {
72 if (!node) {
73 return false;
74 } else if (!node->left) {
75 ret_value = node->value;
76 return true;
77 }
78
79 return find_min(node->left, ret_value);
80 }
binary_search_tree::find_min
bool find_min(std::unique_ptr< bst_node > &node, T &ret_value)
Recursive function to find the minimum value in the BST.
Definition binary_search_tree2.cpp:71

◆ find_min() [2/2]

template<class T >
bool binary_search_tree< T >::find_min ( T & ret_value)
inline

Find the smallest value in the BST.

Parameters
ret_valueVariable to hold the minimum value.
Returns
true If minimum value was successfully found.
false Otherwise.

Definition at line 298 of file binary_search_tree2.cpp.

298{ return find_min(root_, ret_value); }

◆ get_elements_inorder()

template<class T >
std::vector< T > binary_search_tree< T >::get_elements_inorder ( )
inline

Get all values of the BST in in-order order.

Returns
std::vector<T> List of values, sorted in in-order order.

Definition at line 321 of file binary_search_tree2.cpp.

321 {
322 std::vector<T> result;
323 traverse_inorder([&](T node_value) { result.push_back(node_value); },
324 root_);
325 return result;
326 }
binary_search_tree::traverse_inorder
void traverse_inorder(std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
Recursive function to traverse the tree in in-order order.
Definition binary_search_tree2.cpp:197
math::fibonacci_sum::result
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:77

◆ get_elements_postorder()

template<class T >
std::vector< T > binary_search_tree< T >::get_elements_postorder ( )
inline

Get all values of the BST in post-order order.

Returns
std::vector<T> List of values, sorted in post-order order.

Definition at line 345 of file binary_search_tree2.cpp.

345 {
346 std::vector<T> result;
347 traverse_postorder([&](T node_value) { result.push_back(node_value); },
348 root_);
349 return result;
350 }
binary_search_tree::traverse_postorder
void traverse_postorder(std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
Recursive function to traverse the tree in post-order order.
Definition binary_search_tree2.cpp:231

◆ get_elements_preorder()

template<class T >
std::vector< T > binary_search_tree< T >::get_elements_preorder ( )
inline

Get all values of the BST in pre-order order.

Returns
std::vector<T> List of values, sorted in pre-order order.

Definition at line 333 of file binary_search_tree2.cpp.

333 {
334 std::vector<T> result;
335 traverse_preorder([&](T node_value) { result.push_back(node_value); },
336 root_);
337 return result;
338 }
binary_search_tree::traverse_preorder
void traverse_preorder(std::function< void(T)> callback, std::unique_ptr< bst_node > &node)
Recursive function to traverse the tree in pre-order order.
Definition binary_search_tree2.cpp:214

◆ insert() [1/2]

template<class T >
bool binary_search_tree< T >::insert ( std::unique_ptr< bst_node > & node,
T new_value )
inlineprivate

Recursive function to insert a value into the BST.

Parameters
nodeThe node to search from.
new_valueThe value to insert.
Returns
true If the insert operation was successful.
false Otherwise.

Definition at line 90 of file binary_search_tree2.cpp.

90 {
91 if (root_ == node && !root_) {
92 root_ = std::unique_ptr<bst_node>(new bst_node(new_value));
93 return true;
94 }
95
96 if (new_value < node->value) {
97 if (!node->left) {
98 node->left = std::unique_ptr<bst_node>(new bst_node(new_value));
99 return true;
100 } else {
101 return insert(node->left, new_value);
102 }
103 } else if (new_value > node->value) {
104 if (!node->right) {
105 node->right =
106 std::unique_ptr<bst_node>(new bst_node(new_value));
107 return true;
108 } else {
109 return insert(node->right, new_value);
110 }
111 } else {
112 return false;
113 }
114 }
binary_search_tree::insert
bool insert(std::unique_ptr< bst_node > &node, T new_value)
Recursive function to insert a value into the BST.
Definition binary_search_tree2.cpp:90

◆ insert() [2/2]

template<class T >
bool binary_search_tree< T >::insert ( T new_value)
inline

Insert a new value into the BST.

Parameters
new_valueThe value to insert into the BST.
Returns
true If the insertion was successful.
false Otherwise.

Definition at line 259 of file binary_search_tree2.cpp.

259 {
260 bool result = insert(root_, new_value);
261 if (result) {
262 size_++;
263 }
264 return result;
265 }

◆ remove() [1/2]

template<class T >
bool binary_search_tree< T >::remove ( std::unique_ptr< bst_node > & parent,
std::unique_ptr< bst_node > & node,
T rm_value )
inlineprivate

Recursive function to remove a value from the BST.

Parameters
parentThe parent node of node.
nodeThe node to search from.
rm_valueThe value to remove.
Returns
true If the removal operation was successful.
false Otherwise.

Definition at line 125 of file binary_search_tree2.cpp.

126 {
127 if (!node) {
128 return false;
129 }
130
131 if (node->value == rm_value) {
132 if (node->left && node->right) {
133 T successor_node_value{};
134 find_max(node->left, successor_node_value);
135 remove(root_, root_, successor_node_value);
136 node->value = successor_node_value;
137 return true;
138 } else if (node->left || node->right) {
139 std::unique_ptr<bst_node>& non_null =
140 (node->left ? node->left : node->right);
141
142 if (node == root_) {
143 root_ = std::move(non_null);
144 } else if (rm_value < parent->value) {
145 parent->left = std::move(non_null);
146 } else {
147 parent->right = std::move(non_null);
148 }
149
150 return true;
151 } else {
152 if (node == root_) {
153 root_.reset(nullptr);
154 } else if (rm_value < parent->value) {
155 parent->left.reset(nullptr);
156 } else {
157 parent->right.reset(nullptr);
158 }
159
160 return true;
161 }
162 } else if (rm_value < node->value) {
163 return remove(node, node->left, rm_value);
164 } else {
165 return remove(node, node->right, rm_value);
166 }
167 }
binary_search_tree::remove
bool remove(std::unique_ptr< bst_node > &parent, std::unique_ptr< bst_node > &node, T rm_value)
Recursive function to remove a value from the BST.
Definition binary_search_tree2.cpp:125

◆ remove() [2/2]

template<class T >
bool binary_search_tree< T >::remove ( T rm_value)
inline

Remove a specified value from the BST.

Parameters
rm_valueThe value to remove.
Returns
true If the removal was successful.
false Otherwise.

Definition at line 274 of file binary_search_tree2.cpp.

274 {
275 bool result = remove(root_, root_, rm_value);
276 if (result) {
277 size_--;
278 }
279 return result;
280 }

◆ size()

template<class T >
std::size_t binary_search_tree< T >::size ( )
inline

Get the number of values in the BST.

Returns
std::size_t Number of values in the BST.

Definition at line 314 of file binary_search_tree2.cpp.

314{ return size_; }

◆ traverse_inorder()

template<class T >
void binary_search_tree< T >::traverse_inorder ( std::function< void(T)> callback,
std::unique_ptr< bst_node > & node )
inlineprivate

Recursive function to traverse the tree in in-order order.

Parameters
callbackFunction that is called when a value needs to processed.
nodeThe node to traverse from.

Definition at line 197 of file binary_search_tree2.cpp.

198 {
199 if (!node) {
200 return;
201 }
202
203 traverse_inorder(callback, node->left);
204 callback(node->value);
205 traverse_inorder(callback, node->right);
206 }

◆ traverse_postorder()

template<class T >
void binary_search_tree< T >::traverse_postorder ( std::function< void(T)> callback,
std::unique_ptr< bst_node > & node )
inlineprivate

Recursive function to traverse the tree in post-order order.

Parameters
callbackFunction that is called when a value needs to processed.
nodeThe node to traverse from.

Definition at line 231 of file binary_search_tree2.cpp.

232 {
233 if (!node) {
234 return;
235 }
236
237 traverse_postorder(callback, node->left);
238 traverse_postorder(callback, node->right);
239 callback(node->value);
240 }

◆ traverse_preorder()

template<class T >
void binary_search_tree< T >::traverse_preorder ( std::function< void(T)> callback,
std::unique_ptr< bst_node > & node )
inlineprivate

Recursive function to traverse the tree in pre-order order.

Parameters
callbackFunction that is called when a value needs to processed.
nodeThe node to traverse from.

Definition at line 214 of file binary_search_tree2.cpp.

215 {
216 if (!node) {
217 return;
218 }
219
220 callback(node->value);
221 traverse_preorder(callback, node->left);
222 traverse_preorder(callback, node->right);
223 }

Member Data Documentation

◆ root_

template<class T >
std::unique_ptr<bst_node> binary_search_tree< T >::root_
private

Pointer to the root of the BST.

Definition at line 42 of file binary_search_tree2.cpp.

◆ size_

template<class T >
std::size_t binary_search_tree< T >::size_ = 0
private

Number of elements/nodes in the BST.

Definition at line 43 of file binary_search_tree2.cpp.

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