16 typedef typename Node::Key Key;
30 explicit BST(Compare cmp = Compare()): BST(nullptr, cmp) {}
32 BST(
const BST& other) =
delete;
34 BST(
BST&& other)
noexcept: _cmp(other._cmp), _root(other._root) {
35 other._root =
nullptr;
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; }
43 Node* find(
const Key& key)
const {
45 while (probe !=
nullptr) {
46 if (_cmp(probe->key, key)) {
47 probe = probe->right();
49 else if (_cmp(key, probe->key)) {
50 probe = probe->left();
59 Node* pred(
const Key& key,
bool strict =
false)
const {
60 auto node = seek(key);
61 if (node ==
nullptr) {
64 if (_cmp(key, node->key)) {
67 if (_cmp(node->key, key)) {
70 return strict ? pred(node) : node;
73 Node* succ(
const Key& key,
bool strict =
false)
const {
74 auto node = seek(key);
75 if (node ==
nullptr) {
78 if (_cmp(key, node->key)) {
81 if (_cmp(node->key, key)) {
84 return strict ? succ(node) : node;
93 Node* parent =
nullptr;
97 while (probe !=
nullptr) {
98 if (_cmp(node->key, probe->key)) {
101 probe = parent->left();
103 else if (_cmp(probe->key, node->key)) {
106 probe = parent->right();
109 node->parent = parent;
110 if (parent !=
nullptr) {
112 parent->set_left(node);
115 parent->set_right(node);
121 link_left(node, probe->left());
122 link_right(node, probe->right());
123 node->size = probe->size;
128 node->parent = parent;
129 node->set_left(
nullptr);
130 node->set_right(
nullptr);
133 if (parent !=
nullptr) {
135 parent->set_left(node);
138 parent->set_right(node);
145 inc_size_path(parent);
150 RemoveReport remove(Node* node) {
151 auto parent = node->parent;
153 if (parent !=
nullptr) {
154 if (node == parent->left()) {
162 if (node->left() ==
nullptr && node->right() ==
nullptr) {
163 if (parent !=
nullptr) {
165 parent->set_left(
nullptr);
168 parent->set_right(
nullptr);
174 dec_size_path(parent);
175 return {
nullptr, parent,
nullptr, left_path };
178 if (node->left() ==
nullptr) {
179 if (parent !=
nullptr) {
181 link_left(parent, node->right());
184 link_right(parent, node->right());
188 _root = node->right();
189 _root->parent =
nullptr;
191 dec_size_path(parent);
192 return { node->right(), parent, node->right(), left_path };
195 if (node->right() ==
nullptr) {
196 if (parent !=
nullptr) {
198 link_left(parent, node->left());
201 link_right(parent, node->left());
205 _root = node->left();
206 _root->parent =
nullptr;
208 dec_size_path(parent);
209 return { node->left(), parent, node->left(), left_path };
212 Node* subtree_parent;
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;
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;
232 if (parent !=
nullptr) {
234 link_left(parent, succ);
237 link_right(parent, succ);
241 succ->parent =
nullptr;
244 dec_size_path(subtree_parent);
245 return { succ, subtree_parent, subtree_child, is_left_child };
248 static Node* pred(Node* node) {
249 if (node->left() !=
nullptr) {
250 return _rightmost(node->left());
252 for (
auto probe = node; probe->parent !=
nullptr; probe = probe->parent) {
253 if (probe == probe->parent->right()) {
254 return probe->parent;
260 static Node* succ(Node* node) {
261 if (node->right() !=
nullptr) {
262 return _leftmost(node->right());
264 for (
auto probe = node; probe->parent !=
nullptr; probe = probe->parent) {
265 if (probe == probe->parent->left()) {
266 return probe->parent;
273 explicit BST(Node* root, Compare cmp = Compare()): _cmp(cmp), _root(root) {
274 if (_root !=
nullptr) {
275 _root->parent =
nullptr;
279 Node* seek(
const Key& key)
const {
281 Node* parent =
nullptr;
282 while (probe !=
nullptr) {
283 if (_cmp(probe->key, key)) {
285 probe = parent->right();
287 else if (_cmp(key, probe->key)) {
289 probe = parent->left();
298 static Node* _leftmost(Node* node) {
300 while (probe->left() !=
nullptr) {
301 probe = probe->left();
306 static Node* _rightmost(Node* node) {
308 while (probe->right() !=
nullptr) {
309 probe = probe->right();
314 static void link_left(Node* parent, Node* child) {
315 if (parent !=
nullptr) {
316 parent->set_left(child);
318 if (child !=
nullptr) {
319 child->parent = parent;
323 static void link_right(Node* parent, Node* child) {
324 if (parent !=
nullptr) {
325 parent->set_right(child);
327 if (child !=
nullptr) {
328 child->parent = parent;
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;
342 static void update_size_path(Node* node) {
343 for (
auto ancestor = node; ancestor !=
nullptr; ancestor = ancestor->parent) {
344 update_size(ancestor);
348 static void inc_size_path(Node* node) {
349 for (
auto ancestor = node; ancestor !=
nullptr; ancestor = ancestor->parent) {
354 static void dec_size_path(Node* node) {
355 for (
auto ancestor = node; ancestor !=
nullptr; ancestor = ancestor->parent) {