yfast 0.6.1
Loading...
Searching...
No Matches
bst.h
1#ifndef _YFAST_IMPL_BST_H
2#define _YFAST_IMPL_BST_H
3
4#include <functional>
5
6namespace yfast::impl {
7
13template <typename Node, typename Compare = std::less<typename Node::Key>>
14class BST {
15public:
16 typedef typename Node::Key Key;
17
18 typedef struct {
19 Node* substitution;
20 Node* subtree_parent; // height changed
21 Node* subtree_child; // height unchanged
22 bool is_left_child; // NB: only matters if subtree_parent != nullptr
24
25protected:
26 Compare _cmp;
27 Node* _root;
28
29public:
30 explicit BST(Compare cmp = Compare()): BST(nullptr, cmp) {}
31
32 BST(const BST& other) = delete;
33
34 BST(BST&& other) noexcept: _cmp(other._cmp), _root(other._root) {
35 other._root = nullptr;
36 }
37
38 [[nodiscard]] unsigned int size() const { return _root != nullptr ? _root->size : 0; }
39 Node* root() const { return _root; }
40 Node* leftmost() const { return _root != nullptr ? _leftmost(_root) : nullptr; }
41 Node* rightmost() const { return _root != nullptr ? _rightmost(_root) : nullptr; }
42
43 Node* find(const Key& key) const {
44 auto probe = _root;
45 while (probe != nullptr) {
46 if (_cmp(probe->key, key)) {
47 probe = probe->right();
48 }
49 else if (_cmp(key, probe->key)) {
50 probe = probe->left();
51 }
52 else {
53 return probe;
54 }
55 }
56 return nullptr;
57 }
58
59 Node* pred(const Key& key, bool strict = false) const {
60 auto node = seek(key);
61 if (node == nullptr) {
62 return nullptr;
63 }
64 if (_cmp(key, node->key)) {
65 return pred(node);
66 }
67 if (_cmp(node->key, key)) {
68 return node;
69 }
70 return strict ? pred(node) : node;
71 }
72
73 Node* succ(const Key& key, bool strict = false) const {
74 auto node = seek(key);
75 if (node == nullptr) {
76 return nullptr;
77 }
78 if (_cmp(key, node->key)) {
79 return node;
80 }
81 if (_cmp(node->key, key)) {
82 return succ(node);
83 }
84 return strict ? succ(node) : node;
85 }
86
92 Node* insert(Node* node) {
93 Node* parent = nullptr;
94 auto probe = _root;
95 bool left_path;
96
97 while (probe != nullptr) {
98 if (_cmp(node->key, probe->key)) {
99 left_path = true;
100 parent = probe;
101 probe = parent->left();
102 }
103 else if (_cmp(probe->key, node->key)) {
104 left_path = false;
105 parent = probe;
106 probe = parent->right();
107 }
108 else { // replace
109 node->parent = parent;
110 if (parent != nullptr) {
111 if (left_path) { // NB: assigned if 'parent' non-null
112 parent->set_left(node);
113 }
114 else {
115 parent->set_right(node);
116 }
117 }
118 else {
119 _root = node;
120 }
121 link_left(node, probe->left());
122 link_right(node, probe->right());
123 node->size = probe->size;
124 return probe;
125 }
126 }
127
128 node->parent = parent;
129 node->set_left(nullptr);
130 node->set_right(nullptr);
131 node->size = 1;
132
133 if (parent != nullptr) {
134 if (left_path) { // NB: assigned if 'parent' non-null
135 parent->set_left(node);
136 }
137 else {
138 parent->set_right(node);
139 }
140 }
141 else {
142 _root = node;
143 }
144
145 inc_size_path(parent);
146
147 return nullptr;
148 }
149
150 RemoveReport remove(Node* node) {
151 auto parent = node->parent;
152 bool left_path;
153 if (parent != nullptr) {
154 if (node == parent->left()) {
155 left_path = true;
156 }
157 else {
158 left_path = false;
159 }
160 }
161
162 if (node->left() == nullptr && node->right() == nullptr) {
163 if (parent != nullptr) {
164 if (left_path) { // NB: assigned if 'parent' non-null
165 parent->set_left(nullptr);
166 }
167 else {
168 parent->set_right(nullptr);
169 }
170 }
171 else {
172 _root = nullptr;
173 }
174 dec_size_path(parent);
175 return { nullptr, parent, nullptr, left_path };
176 }
177
178 if (node->left() == nullptr) { // => node->right != nullptr
179 if (parent != nullptr) {
180 if (left_path) { // NB: assigned if 'parent' non-null
181 link_left(parent, node->right());
182 }
183 else {
184 link_right(parent, node->right());
185 }
186 }
187 else {
188 _root = node->right();
189 _root->parent = nullptr;
190 }
191 dec_size_path(parent);
192 return { node->right(), parent, node->right(), left_path };
193 }
194
195 if (node->right() == nullptr) { // => node->left != nullptr
196 if (parent != nullptr) {
197 if (left_path) { // NB: assigned if 'parent' non-null
198 link_left(parent, node->left());
199 }
200 else {
201 link_right(parent, node->left());
202 }
203 }
204 else {
205 _root = node->left();
206 _root->parent = nullptr;
207 }
208 dec_size_path(parent);
209 return { node->left(), parent, node->left(), left_path };
210 }
211
212 Node* subtree_parent;
213 Node* subtree_child;
214 bool is_left_child;
215 auto succ = BST::succ(node);
216 if (succ == node->right()) {
217 link_left(succ, node->left());
218 succ->size = node->size;
219 subtree_parent = succ;
220 subtree_child = succ->right();
221 is_left_child = false;
222 }
223 else {
224 subtree_parent = succ->parent;
225 subtree_child = succ->right();
226 link_left(succ->parent, succ->right());
227 link_left(succ, node->left());
228 link_right(succ, node->right());
229 succ->size = node->size;
230 is_left_child = true;
231 }
232 if (parent != nullptr) {
233 if (left_path) { // NB: assigned if 'parent' non-null
234 link_left(parent, succ);
235 }
236 else {
237 link_right(parent, succ);
238 }
239 }
240 else {
241 succ->parent = nullptr;
242 _root = succ;
243 }
244 dec_size_path(subtree_parent);
245 return { succ, subtree_parent, subtree_child, is_left_child };
246 }
247
248 static Node* pred(Node* node) {
249 if (node->left() != nullptr) {
250 return _rightmost(node->left());
251 }
252 for (auto probe = node; probe->parent != nullptr; probe = probe->parent) {
253 if (probe == probe->parent->right()) {
254 return probe->parent;
255 }
256 }
257 return nullptr;
258 }
259
260 static Node* succ(Node* node) {
261 if (node->right() != nullptr) {
262 return _leftmost(node->right());
263 }
264 for (auto probe = node; probe->parent != nullptr; probe = probe->parent) {
265 if (probe == probe->parent->left()) {
266 return probe->parent;
267 }
268 }
269 return nullptr;
270 }
271
272protected:
273 explicit BST(Node* root, Compare cmp = Compare()): _cmp(cmp), _root(root) {
274 if (_root != nullptr) {
275 _root->parent = nullptr;
276 }
277 }
278
279 Node* seek(const Key& key) const {
280 auto probe = _root;
281 Node* parent = nullptr;
282 while (probe != nullptr) {
283 if (_cmp(probe->key, key)) {
284 parent = probe;
285 probe = parent->right();
286 }
287 else if (_cmp(key, probe->key)) {
288 parent = probe;
289 probe = parent->left();
290 }
291 else {
292 return probe;
293 }
294 }
295 return parent;
296 }
297
298 static Node* _leftmost(Node* node) {
299 auto probe = node;
300 while (probe->left() != nullptr) {
301 probe = probe->left();
302 }
303 return probe;
304 }
305
306 static Node* _rightmost(Node* node) {
307 auto probe = node;
308 while (probe->right() != nullptr) {
309 probe = probe->right();
310 }
311 return probe;
312 }
313
314 static void link_left(Node* parent, Node* child) {
315 if (parent != nullptr) {
316 parent->set_left(child);
317 }
318 if (child != nullptr) {
319 child->parent = parent;
320 }
321 }
322
323 static void link_right(Node* parent, Node* child) {
324 if (parent != nullptr) {
325 parent->set_right(child);
326 }
327 if (child != nullptr) {
328 child->parent = parent;
329 }
330 }
331
332 static void update_size(Node* node) {
333 if (node != nullptr) {
334 auto left = node->left();
335 auto left_size = left != nullptr ? left->size : 0;
336 auto right = node->right();
337 auto right_size = right != nullptr ? right->size : 0;
338 node->size = 1 + left_size + right_size;
339 }
340 }
341
342 static void update_size_path(Node* node) {
343 for (auto ancestor = node; ancestor != nullptr; ancestor = ancestor->parent) {
344 update_size(ancestor);
345 }
346 }
347
348 static void inc_size_path(Node* node) {
349 for (auto ancestor = node; ancestor != nullptr; ancestor = ancestor->parent) {
350 ++(ancestor->size);
351 }
352 }
353
354 static void dec_size_path(Node* node) {
355 for (auto ancestor = node; ancestor != nullptr; ancestor = ancestor->parent) {
356 --(ancestor->size);
357 }
358 }
359};
360
361}
362
363#endif
Definition bst.h:14
Node * insert(Node *node)
Definition bst.h:92