-
Notifications
You must be signed in to change notification settings - Fork 0
/
BSTuptr.hpp
408 lines (368 loc) · 12.2 KB
/
BSTuptr.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
#pragma once
/**
* @brief Binary Search Tree (BST) using std::unique_ptr.
* Any comparable data is allowed within this tree.
* Supported operations include adding, removing, height, and containment checks.
* Multiple tree traversal orders are provided including non-recursive traversal via iterator:
* 1) Inorder
* 2) Preorder
* 3) Postorder
* 4) Levelorder
*/
#include "BSTuptrNode.hpp"
#include "BSTuptrIterator.hpp"
#include <algorithm> // std::max
#include <cstddef> // std::size_t
#include <cstdint> // std::uint8_t
#include <initializer_list>
#include <iostream>
#include <memory> // std::unique_ptr
#include <sstream>
#include <stdexcept> // std::invalid_argument
#include <utility> // std::move
namespace wndx {
namespace ds {
template<typename T>
class BSTuptr
{
public:
using enum TreeTravOrder;
// alias to the node pointer
using node_ptr = std::unique_ptr<Node<T>>;
using const_iterator = BSTuptrIterator<T>;
protected:
enum TreeTravOrder trav_order{ TreeTravOrder::IN_ORDER };
// tracks the number of nodes in this BST
std::size_t m_nodeCount {0};
// this BST is a rooted tree so we maintain a handle on the root node
node_ptr m_root;
public:
/**
* @brief use specific tree traversal order.
*/
BSTuptr(const TreeTravOrder order)
: trav_order{ order }
{
}
/**
* @brief support list initialization, optionally use specified tree traversal order.
*/
BSTuptr(const std::initializer_list<T> il, const TreeTravOrder order=IN_ORDER)
: trav_order{ order }
{
for (const T n : il) add(n);
}
BSTuptr() = default;
BSTuptr(BSTuptr &&) = default;
BSTuptr(const BSTuptr &) = default;
BSTuptr &operator=(BSTuptr &&) = default;
BSTuptr &operator=(const BSTuptr &) = default;
virtual ~BSTuptr() = default;
public:
const_iterator cbegin() const noexcept { return const_iterator(m_root.get(), trav_order); }
const_iterator cend() const noexcept { return const_iterator(nullptr); }
const_iterator begin() const noexcept { return const_iterator(m_root.get(), trav_order); }
const_iterator end() const noexcept { return const_iterator(nullptr); }
/**
* @brief the number of nodes in binary tree
*/
std::size_t size() const
{
return m_nodeCount;
}
/**
* @brief check if binary tree is empty
*/
constexpr bool empty() const
{
return size() == 0;
}
public:
/**
* @brief add an element to this binary tree.
*
* @param data The data/value to add.
* @return true If the insertion operation was successful.
*/
bool add(const T& data)
{
// if already exists in the binary tree => ignore adding it
if (contains(data)) return false;
m_root = add(m_root, data);
m_nodeCount++;
return true;
}
private:
/**
* @brief private method to recursively add a value in the binary tree.
*
* @param node The node to search from.
* @param data The data/value to add.
*/
node_ptr add(node_ptr& node, const T& data)
{
// base case: found a leaf node
if (!node) return std::make_unique<Node<T>>(data);
// pick a subtree to insert element
if (data < node->m_data) {
node->l = add(node->l, data);
} else {
node->r = add(node->r, data);
}
return std::move(node);
}
public:
/**
* @brief Remove a value from binary tree if it exists, O(n).
*
* @param rm_data The data/value to remove.
*/
bool remove(const T& rm_data)
{
// check that node is actually exist
if (contains(rm_data)) {
if (true) { // to use a different removal algorithm.
m_root = std::move(remove(m_root, rm_data));
} else {
if (!remove(m_root, m_root, rm_data)) return false;
}
m_nodeCount--;
return true;
}
return false;
}
private:
/**
* @brief private recursive method to find & remove an element from the tree, O(n).
*
* @param node The node to search from.
* @param rm_data The data/value to remove.
* @return reference of the node pointer to update the tree.
* usage: m_root = std::move(remove(m_root, rm_data));
*/
node_ptr& remove(node_ptr& node, const T& rm_data)
{
if (!node) return node; // nullptr node_ptr
if (rm_data < node->m_data) {
// dig into the left subtree
node->l = std::move(remove(node->l, rm_data));
} else if (rm_data > node->m_data) {
// dig into the right subtree
node->r = std::move(remove(node->r, rm_data));
} else { // found the node we want to remove
// This is the case with only a right subtree or no subtree at all.
// swap the node we want to remove with its right child.
if (!node->l) return node->r;
// This is the case with only a left subtree or no subtree at all.
// swap the node we want to remove with its left child.
if (!node->r) return node->l;
/* When removing a node from a binary tree with two links the
* successor of the node being removed can either be the largest
* value in the left subtree or the smallest value in the right
* subtree. In this implementation I have decided to find the
* smallest value in the right subtree which can be found by
* traversing as far left as possible in the right subtree. */
// find the leftmost node in the right subtree
node_ptr& successor{ findMin(node->r) };
T sndata{ successor->m_data }; // successor node data
// swap / set successor node data
node->m_data = sndata;
/* go into the right subtree and remove the leftmost node we
* found and swapped data with. This prevents us from having
* two nodes in our tree with the same value. */
node->r = std::move(remove(node->r, sndata));
}
return node;
}
/**
* @brief private recursive method to find & remove an element from the tree, O(n).
*
* @param parent The parent node of node.
* @param node The node to search from.
* @param rm_data The data/value to remove.
* @return true If the removal operation was successful.
* usage: remove(m_root, m_root, data);
* (another version of removing algorithm).
*/
bool remove(node_ptr& parent, node_ptr& node, const T& rm_data)
{
// base cases
if (!node) return false;
if (rm_data < node->m_data) return remove(node, node->l, rm_data);
if (rm_data > node->m_data) return remove(node, node->r, rm_data);
if (rm_data != node->m_data) return false;
// found the node we want to remove (rm_data == node->m_data)
if (node->l && node->r) {
node_ptr& successor{ findMin(node->r) };
T sndata{ successor->m_data }; // successor node data
remove(m_root, m_root, sndata);
node->m_data = sndata;
} else if (node->l || node->r) {
node_ptr& non_null = (node->l ? node->l : node->r);
if (m_root == node)
m_root = std::move(non_null);
else if (rm_data < parent->m_data)
parent->l = std::move(non_null);
else
parent->r = std::move(non_null);
} else {
if (node == m_root)
m_root.reset(nullptr);
else if (rm_data < parent->m_data)
parent->l.reset(nullptr);
else
parent->r.reset(nullptr);
}
return true;
}
/**
* @brief Helper method to find the leftmost node (which has the smallest value).
* usage: node_ptr& successor{ findMin(node->r) };
*/
node_ptr& findMin(node_ptr& node)
{
while (node->l) return findMin(node->l);
return node;
}
/**
* @brief Helper method to find the rightmost node (which has the largest value).
* usage: node_ptr& successor{ findMax(node->l) };
*/
node_ptr& findMax(node_ptr& node)
{
while (node->r) return findMax(node->r);
return node;
}
public:
/**
* @brief returns true if the element exists in the tree.
*/
bool contains(const T& data)
{
return contains(m_root, data);
}
private:
/**
* @brief private recursive method to find an element in the tree.
*/
bool contains(node_ptr& node, const T& data)
{
// base case: reached bottom, value not found
if (!node) return false;
// dig into the left subtree
if (data < node->m_data)
return contains(node->l, data);
// dig into the right subtree
if (data > node->m_data)
return contains(node->r, data);
// found the value we were looking for
return true;
}
public:
/**
* @brief compute the height of the tree, O(n).
*/
std::size_t height()
{
return height(m_root);
}
private:
/**
* @brief recursive helper method to compute the height of the tree.
*/
std::size_t height(const node_ptr& node)
{
if (!node) return 0;
return std::max(height(node->l), height(node->r)) + 1;
}
protected:
/**
* @brief helper method to pretty print tree.
*/
void cout_tree_info(std::ostringstream& oss, const std::string& prefix)
{
std::string str { oss.str() };
// erase extra ", " string (after last node data)
if (str.length() > 1) str.erase(str.end() - 2, str.end());
std::cout << prefix << "h:(" << height() << ")\t[" << str << "]\n";
}
/**
* @brief recursive method to print tree in inorder.
*/
void print_inorder(const node_ptr& node, std::ostream& oss = std::cout) const
{
if (!node) return;
print_inorder(node->l, oss);
oss << node->m_data << ", ";
print_inorder(node->r, oss);
}
/**
* @brief recursive method to print tree in preorder.
*/
void print_preorder(const node_ptr& node, std::ostream& oss = std::cout) const
{
if (!node) return;
oss << node->m_data << ", ";
print_preorder(node->l, oss);
print_preorder(node->r, oss);
}
/**
* @brief recursive method to print tree in postorder.
*/
void print_postorder(const node_ptr& node, std::ostream& oss = std::cout) const
{
if (!node) return;
print_postorder(node->l, oss);
print_postorder(node->r, oss);
oss << node->m_data << ", ";
}
/**
* @brief recursive method to print tree in levelorder.
*/
void print_levelorder(const node_ptr& node, std::ostream& oss = std::cout)
{
for (std::size_t i = 0; i <= height(); i++) {
lorder_cur_lvl(node, i, oss);
}
}
private:
void lorder_cur_lvl(const node_ptr& node, const std::size_t& lvl, std::ostream& oss = std::cout) const
{
if (!node) return;
if (lvl == 1) {
oss << node->m_data << ", ";
} else if (lvl > 1) {
lorder_cur_lvl(node->l, lvl - 1, oss);
lorder_cur_lvl(node->r, lvl - 1, oss);
}
}
public:
/**
* @brief pass enum to print tree in specific order i.e. tree.IN_ORDER
*/
void print(const TreeTravOrder order, const std::string& prefix="")
{
std::ostringstream oss;
switch (order) {
case IN_ORDER:
print_inorder(m_root, oss);
break;
case PRE_ORDER:
print_preorder(m_root, oss);
break;
case POST_ORDER:
print_postorder(m_root, oss);
break;
case LEVEL_ORDER:
print_levelorder(m_root, oss);
break;
// LCOV_EXCL_START - is it even possible to properly cover this case?
default:
throw std::invalid_argument("No Such Tree Traversal Order.");
// LCOV_EXCL_STOP
}
cout_tree_info(oss, prefix);
}
};
} // namespace ds
} // namespace wndx