1//! @file tree.cpp
2//! @author ryftchen
3//! @brief The definitions (tree) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "tree.hpp"
8
9namespace data_structure::tree
10{
11//! @brief Function version number.
12//! @return version number (major.minor.patch)
13const char* version() noexcept
14{
15 static const char* const ver = "0.1.0";
16 return ver;
17}
18
19// NOLINTBEGIN(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
20namespace bs
21{
22//! @brief Get the node where the minimum key is located in the BS subtree.
23//! @param root - root of the subtree
24//! @return node where the minimum key is located
25static Node* getMinimum(Node* const root)
26{
27 if (!root)
28 {
29 return nullptr;
30 }
31
32 Node* curr = root;
33 while (curr->left)
34 {
35 curr = curr->left;
36 }
37 return curr;
38}
39
40//! @brief Get the node where the maximum key is located in the BS subtree.
41//! @param root - root of the subtree
42//! @return node where the maximum key is located
43static Node* getMaximum(Node* const root)
44{
45 if (!root)
46 {
47 return nullptr;
48 }
49
50 Node* curr = root;
51 while (curr->right)
52 {
53 curr = curr->right;
54 }
55 return curr;
56}
57
58//! @brief Create the node of the BS subtree.
59//! @param key - key of the node to be created
60//! @param parent - parent node of the node to be created
61//! @param left - left child node of the node to be created
62//! @param right - right child node of the node to be created
63//! @return new node after creating
64static Node* createNode(const void* const key, Node* const parent, Node* const left, Node* const right)
65{
66 Node* const newNode = ::new (std::nothrow) Node;
67 if (!newNode)
68 {
69 return nullptr;
70 }
71
72 newNode->left = left;
73 newNode->right = right;
74 newNode->parent = parent;
75 newNode->key = const_cast<void*>(key);
76 return newNode;
77}
78
79//! @brief Insert the node into the BS subtree. Allow inserting node with the same key.
80//! @param root - root of the subtree
81//! @param node - target node
82//! @param cmp - compare function to compare keys
83//! @return root node after inserting
84static Node* insertNode(Node* root, Node* node, const Compare cmp)
85{
86 if (!node || !cmp)
87 {
88 ::delete node;
89 node = nullptr;
90 return root;
91 }
92
93 Node* x = root;
94 Node* y = nullptr;
95 while (x)
96 {
97 y = x;
98 x = (cmp(node->key, x->key) < 0) ? x->left : x->right;
99 }
100
101 node->parent = y;
102 if (!y)
103 {
104 root = node;
105 }
106 else if (cmp(node->key, y->key) < 0)
107 {
108 y->left = node;
109 }
110 else
111 {
112 y->right = node;
113 }
114 return root;
115}
116
117//! @brief Remove the node from the BS subtree.
118//! @param root - root of the subtree
119//! @param node - target node
120//! @return root node after removing
121static Node* removeNode(Node* root, Node* const node)
122{
123 if (!node)
124 {
125 return root;
126 }
127
128 Node* y = (!node->left || !node->right) ? node : getSuccessor(x: node);
129 if (!y)
130 {
131 return root;
132 }
133 Node* const x = y->left ? y->left : y->right;
134 if (x)
135 {
136 x->parent = y->parent;
137 }
138
139 if (!y->parent)
140 {
141 root = x;
142 }
143 else if (y->parent->left == y)
144 {
145 y->parent->left = x;
146 }
147 else
148 {
149 y->parent->right = x;
150 }
151
152 if (y != node)
153 {
154 node->key = y->key;
155 }
156
157 const bool yIsRoot = (root == y);
158 ::delete y;
159 y = nullptr;
160 return !yIsRoot ? root : nullptr;
161}
162
163//! @brief Destroy the BS subtree.
164//! @param root - root of the subtree
165static void destroy(const Node* root)
166{
167 if (!root)
168 {
169 return;
170 }
171
172 if (root->left)
173 {
174 destroy(root: root->left);
175 }
176 if (root->right)
177 {
178 destroy(root: root->right);
179 }
180
181 ::delete root;
182 root = nullptr;
183}
184
185//! @brief Search the node of BS subtree by key.
186//! @param root - root of the subtree
187//! @param key - key of the node
188//! @param cmp - compare function to compare keys
189//! @return node where the key is located
190static Node* search(Node* const root, const void* const key, const Compare cmp)
191{
192 if (!root || !key || !cmp)
193 {
194 return nullptr;
195 }
196 return (cmp(root->key, key) == 0) ? root : search(root: (cmp(key, root->key) < 0) ? root->left : root->right, key, cmp);
197}
198
199//! @brief Get the node where the minimum key is located in the BS tree.
200//! @param tree - BS tree
201//! @return node where the minimum key is located
202Node* getMinimum(const BSTree* const tree)
203{
204 return tree ? getMinimum(root: tree->root) : nullptr;
205}
206
207//! @brief Get the node where the maximum key is located in the BS tree.
208//! @param tree - BS tree
209//! @return node where the maximum key is located
210Node* getMaximum(const BSTree* const tree)
211{
212 return tree ? getMaximum(root: tree->root) : nullptr;
213}
214
215//! @brief Get the predecessor node of the current node.
216//! The precursor of a node is the node that has the maximum key in that node's left subtree.
217//! @param x - current node
218//! @return predecessor node
219Node* getPredecessor(const Node* x)
220{
221 if (!x)
222 {
223 return nullptr;
224 }
225
226 if (x->left)
227 {
228 return getMaximum(root: x->left);
229 }
230
231 Node* y = x->parent;
232 while (y && (y->left == x))
233 {
234 x = y;
235 y = y->parent;
236 }
237 return y;
238}
239
240//! @brief Get the successor node of the current node.
241//! The precursor of a node is the node that has the minimum key in that node's right subtree.
242//! @param x - current node
243//! @return successor node
244Node* getSuccessor(const Node* x)
245{
246 if (!x)
247 {
248 return nullptr;
249 }
250
251 if (x->right)
252 {
253 return getMinimum(root: x->right);
254 }
255
256 Node* y = x->parent;
257 while (y && (y->right == x))
258 {
259 x = y;
260 y = y->parent;
261 }
262 return y;
263}
264
265//! @brief Create the BS tree.
266//! @param cmp - compare function to compare keys
267//! @return new BS tree
268BSTree* create(const Compare cmp)
269{
270 if (!cmp)
271 {
272 return nullptr;
273 }
274
275 auto* const tree = ::new (std::nothrow) BSTree;
276 if (!tree)
277 {
278 return nullptr;
279 }
280
281 tree->root = nullptr;
282 tree->compare = cmp;
283 return tree;
284}
285
286//! @brief Destroy the BS tree.
287//! @param tree - BS tree
288void destroy(const BSTree* tree)
289{
290 if (!tree)
291 {
292 return;
293 }
294
295 destroy(root: tree->root);
296 ::delete tree;
297 tree = nullptr;
298}
299
300//! @brief Search the node of BS tree by key.
301//! @param tree - BS tree
302//! @param key - key of the node
303//! @return node where the key is located
304Node* search(const BSTree* const tree, const void* const key)
305{
306 return tree ? search(root: tree->root, key, cmp: tree->compare) : nullptr;
307}
308
309//! @brief Insert the node into the BS tree. Allow inserting node with the same key.
310//! @param tree - BS tree
311//! @param key - key of the target node
312void insert(BSTree* const tree, const void* const key)
313{
314 if (!tree)
315 {
316 return;
317 }
318
319 if (Node* const z = createNode(key, parent: nullptr, left: nullptr, right: nullptr))
320 {
321 tree->root = insertNode(root: tree->root, node: z, cmp: tree->compare);
322 }
323}
324
325//! @brief Remove the node from the BS tree.
326//! @param tree - BS tree
327//! @param key - key of the target node
328void remove(BSTree* const tree, const void* const key)
329{
330 if (!tree)
331 {
332 return;
333 }
334
335 if (Node* const z = search(tree, key))
336 {
337 tree->root = removeNode(root: tree->root, node: z);
338 }
339}
340} // namespace bs
341
342namespace avl
343{
344//! @brief Get the height of the AVL subtree.
345//! @param root - root of the subtree
346//! @return height of the AVL subtree
347static int getHeight(const Node* const root)
348{
349 return root ? root->height : 0;
350}
351
352//! @brief Get the node where the minimum key is located in the AVL subtree.
353//! @param root - root of the subtree
354//! @return node where the minimum key is located
355static Node* getMinimum(Node* const root)
356{
357 if (!root)
358 {
359 return nullptr;
360 }
361
362 Node* curr = root;
363 while (curr->left)
364 {
365 curr = curr->left;
366 }
367 return curr;
368}
369
370//! @brief Get the node where the maximum key is located in the AVL subtree.
371//! @param root - root of the subtree
372//! @return node where the maximum key is located
373static Node* getMaximum(Node* const root)
374{
375 if (!root)
376 {
377 return nullptr;
378 }
379
380 Node* curr = root;
381 while (curr->right)
382 {
383 curr = curr->right;
384 }
385 return curr;
386}
387
388//! @brief LL rotation. A single left rotation.
389//! @param k2 - root node of the unbalanced AVL tree
390//! @return root node after rotation
391static Node* leftLeftRotation(Node* const k2)
392{
393 if (!k2 || !k2->left)
394 {
395 return nullptr;
396 }
397
398 Node* const k1 = k2->left;
399 k2->left = k1->right;
400 k1->right = k2;
401
402 k2->height = std::max(a: getHeight(root: k2->left), b: getHeight(root: k2->right)) + 1;
403 k1->height = std::max(a: getHeight(root: k1->left), b: k2->height) + 1;
404 return k1;
405}
406
407//! @brief RR rotation. A single right rotation.
408//! @param k1 - root node of the unbalanced AVL tree
409//! @return root node after rotation
410static Node* rightRightRotation(Node* const k1)
411{
412 if (!k1 || !k1->right)
413 {
414 return nullptr;
415 }
416
417 Node* const k2 = k1->right;
418 k1->right = k2->left;
419 k2->left = k1;
420
421 k1->height = std::max(a: getHeight(root: k1->left), b: getHeight(root: k1->right)) + 1;
422 k2->height = std::max(a: getHeight(root: k2->right), b: k1->height) + 1;
423 return k2;
424}
425
426//! @brief LR rotation. A double left rotation.
427//! @param k3 - root node of the unbalanced AVL tree
428//! @return root node after rotation
429static Node* leftRightRotation(Node* const k3)
430{
431 if (!k3)
432 {
433 return nullptr;
434 }
435
436 k3->left = rightRightRotation(k1: k3->left);
437 return leftLeftRotation(k2: k3);
438}
439
440//! @brief RL rotation. A double right rotation.
441//! @param k1 - root node of the unbalanced AVL tree
442//! @return root node after rotation
443static Node* rightLeftRotation(Node* const k1)
444{
445 if (!k1)
446 {
447 return nullptr;
448 }
449
450 k1->right = leftLeftRotation(k2: k1->right);
451 return rightRightRotation(k1);
452}
453
454//! @brief Create the node of the AVL subtree.
455//! @param key - key of the node to be created
456//! @param left - left child node of the node to be created
457//! @param right - right child node of the node to be created
458//! @return new node after creating
459static Node* createNode(const void* const key, Node* const left, Node* const right)
460{
461 Node* const newNode = ::new (std::nothrow) Node;
462 if (!newNode)
463 {
464 return nullptr;
465 }
466
467 newNode->left = left;
468 newNode->right = right;
469 newNode->key = const_cast<void*>(key);
470 newNode->height = 0;
471 return newNode;
472}
473
474//! @brief Remove the node from the AVL subtree.
475//! @param root - root of the subtree
476//! @param node - target node
477//! @param cmp - compare function to compare keys
478//! @return root node after removing
479static Node* removeNode(Node* root, const Node* const node, const Compare cmp)
480{
481 if (!root || !node || !cmp)
482 {
483 return root;
484 }
485
486 if (cmp(node->key, root->key) < 0)
487 {
488 root->left = removeNode(root: root->left, node, cmp);
489 }
490 else if (cmp(node->key, root->key) > 0)
491 {
492 root->right = removeNode(root: root->right, node, cmp);
493 }
494 else if (root->left && root->right)
495 {
496 if (getHeight(root: root->left) > getHeight(root: root->right))
497 {
498 const Node* const max = getMaximum(root: root->left);
499 root->key = max->key;
500 root->left = removeNode(root: root->left, node: max, cmp);
501 }
502 else
503 {
504 const Node* const min = getMinimum(root: root->right);
505 root->key = min->key;
506 root->right = removeNode(root: root->right, node: min, cmp);
507 }
508 }
509 else
510 {
511 const Node* temp = root;
512 root = root->left ? root->left : root->right;
513 ::delete temp;
514 temp = nullptr;
515 }
516
517 if (!root)
518 {
519 return nullptr;
520 }
521 root->height = std::max(a: getHeight(root: root->left), b: getHeight(root: root->right)) + 1;
522
523 const int balance = getHeight(root: root->left) - getHeight(root: root->right);
524 if (balance > 1)
525 {
526 const Node* const l = root->left;
527 root = (getHeight(root: l->right) > getHeight(root: l->left)) ? leftRightRotation(k3: root) : leftLeftRotation(k2: root);
528 }
529 else if (balance < -1)
530 {
531 const Node* const r = root->right;
532 root = (getHeight(root: r->left) > getHeight(root: r->right)) ? rightLeftRotation(k1: root) : rightRightRotation(k1: root);
533 }
534 return root;
535}
536
537//! @brief Destroy the AVL subtree.
538//! @param root - root of the subtree
539static void destroy(const Node* root)
540{
541 if (!root)
542 {
543 return;
544 }
545
546 if (root->left)
547 {
548 destroy(root: root->left);
549 }
550 if (root->right)
551 {
552 destroy(root: root->right);
553 }
554
555 ::delete root;
556 root = nullptr;
557}
558
559//! @brief Search the node of AVL subtree by key.
560//! @param root - root of the subtree
561//! @param key - key of the node
562//! @param cmp - compare function to compare keys
563//! @return node where the key is located
564static Node* search(Node* const root, const void* const key, const Compare cmp)
565{
566 if (!root || !key || !cmp)
567 {
568 return nullptr;
569 }
570 return (cmp(root->key, key) == 0) ? root : search(root: (cmp(key, root->key) < 0) ? root->left : root->right, key, cmp);
571}
572
573//! @brief Insert the node into the AVL subtree. Not allow inserting node with the same key.
574//! @param root - root of the subtree
575//! @param key - key of the target node
576//! @param cmp - compare function to compare keys
577//! @return root node after inserting
578static Node* insert(Node* root, const void* const key, const Compare cmp)
579{
580 if (!key || !cmp)
581 {
582 return root;
583 }
584
585 if (!root)
586 {
587 root = createNode(key, left: nullptr, right: nullptr);
588 if (!root)
589 {
590 return nullptr;
591 }
592 }
593 else if (cmp(key, root->key) < 0)
594 {
595 root->left = insert(root: root->left, key, cmp);
596 if ((getHeight(root: root->left) - getHeight(root: root->right)) > 1)
597 {
598 root = (cmp(key, root->left->key) < 0) ? leftLeftRotation(k2: root) : leftRightRotation(k3: root);
599 }
600 }
601 else if (cmp(key, root->key) > 0)
602 {
603 root->right = insert(root: root->right, key, cmp);
604 if ((getHeight(root: root->left) - getHeight(root: root->right)) < -1)
605 {
606 root = (cmp(key, root->right->key) > 0) ? rightRightRotation(k1: root) : rightLeftRotation(k1: root);
607 }
608 }
609
610 root->height = std::max(a: getHeight(root: root->left), b: getHeight(root: root->right)) + 1;
611 return root;
612}
613
614//! @brief Remove the node from the AVL subtree.
615//! @param root - root of the subtree
616//! @param key - key of the target node
617//! @param cmp - compare function to compare keys
618//! @return root node after removing
619static Node* remove(Node* root, const void* const key, const Compare cmp)
620{
621 if (const Node* const z = search(root, key, cmp))
622 {
623 root = removeNode(root, node: z, cmp);
624 }
625 return root;
626}
627
628//! @brief Get the height of the AVL tree.
629//! @param tree - AVL tree
630//! @return height of the AVL tree
631int getHeight(const AVLTree* const tree)
632{
633 return (tree && tree->root) ? tree->root->height : 0;
634}
635
636//! @brief Get the node where the minimum key is located in the AVL tree.
637//! @param tree - AVL tree
638//! @return node where the minimum key is located
639Node* getMinimum(const AVLTree* const tree)
640{
641 return tree ? getMinimum(root: tree->root) : nullptr;
642}
643
644//! @brief Get the node where the maximum key is located in the AVL tree.
645//! @param tree - AVL tree
646//! @return node where the maximum key is located
647Node* getMaximum(const AVLTree* const tree)
648{
649 return tree ? getMaximum(root: tree->root) : nullptr;
650}
651
652//! @brief Create the AVL tree.
653//! @param cmp - compare function to compare keys
654//! @return new AVL tree
655AVLTree* create(const Compare cmp)
656{
657 if (!cmp)
658 {
659 return nullptr;
660 }
661
662 auto* const tree = ::new (std::nothrow) AVLTree;
663 if (!tree)
664 {
665 return nullptr;
666 }
667
668 tree->root = nullptr;
669 tree->compare = cmp;
670 return tree;
671}
672
673//! @brief Destroy the AVL tree.
674//! @param tree - AVL tree
675void destroy(const AVLTree* tree)
676{
677 if (!tree)
678 {
679 return;
680 }
681
682 destroy(root: tree->root);
683 ::delete tree;
684 tree = nullptr;
685}
686
687//! @brief Search the node of AVL tree by key.
688//! @param tree - AVL tree
689//! @param key - key of the node
690//! @return node where the key is located
691Node* search(const AVLTree* const tree, const void* const key)
692{
693 return tree ? search(root: tree->root, key, cmp: tree->compare) : nullptr;
694}
695
696//! @brief Insert the node into the AVL tree. Not allow inserting node with the same key.
697//! @param tree - AVL tree
698//! @param key - key of the target node
699void insert(AVLTree* const tree, const void* const key)
700{
701 if (!tree)
702 {
703 return;
704 }
705
706 tree->root = insert(root: tree->root, key, cmp: tree->compare);
707}
708
709//! @brief Remove the node from the AVL tree.
710//! @param tree - AVL tree
711//! @param key - key of the target node
712void remove(AVLTree* const tree, const void* const key)
713{
714 if (!tree)
715 {
716 return;
717 }
718
719 tree->root = remove(root: tree->root, key, cmp: tree->compare);
720}
721} // namespace avl
722
723namespace splay
724{
725//! @brief Get the node where the minimum key is located in the splay subtree.
726//! @param root - root of the subtree
727//! @return node where the minimum key is located
728static Node* getMinimum(Node* const root)
729{
730 if (!root)
731 {
732 return nullptr;
733 }
734
735 Node* curr = root;
736 while (curr->left)
737 {
738 curr = curr->left;
739 }
740 return curr;
741}
742
743//! @brief Get the node where the maximum key is located in the splay subtree.
744//! @param root - root of the subtree
745//! @return node where the maximum key is located
746static Node* getMaximum(Node* const root)
747{
748 if (!root)
749 {
750 return nullptr;
751 }
752
753 Node* curr = root;
754 while (curr->right)
755 {
756 curr = curr->right;
757 }
758 return curr;
759}
760
761//! @brief Create the node of the splay subtree.
762//! @param key - key of the node to be created
763//! @param left - left child node of the node to be created
764//! @param right - right child node of the node to be created
765//! @return new node after creating
766static Node* createNode(const void* const key, Node* const left, Node* const right)
767{
768 Node* const newNode = ::new (std::nothrow) Node;
769 if (!newNode)
770 {
771 return nullptr;
772 }
773
774 newNode->left = left;
775 newNode->right = right;
776 newNode->key = const_cast<void*>(key);
777 return newNode;
778}
779
780//! @brief Insert the node into the splay subtree. Not splay. Not allow inserting node with the same key.
781//! @param root - root of the subtree
782//! @param node - target node
783//! @param cmp - compare function to compare keys
784//! @return root node after inserting
785static Node* insertNode(Node* root, Node* node, const Compare cmp)
786{
787 if (!node || !cmp)
788 {
789 ::delete node;
790 node = nullptr;
791 return root;
792 }
793
794 Node* x = root;
795 Node* y = nullptr;
796 while (x)
797 {
798 y = x;
799 if (cmp(node->key, x->key) < 0)
800 {
801 x = x->left;
802 }
803 else if (cmp(node->key, x->key) > 0)
804 {
805 x = x->right;
806 }
807 else
808 {
809 ::delete node;
810 node = nullptr;
811 return root;
812 }
813 }
814
815 if (!y)
816 {
817 root = node;
818 }
819 else if (cmp(node->key, y->key) < 0)
820 {
821 y->left = node;
822 }
823 else
824 {
825 y->right = node;
826 }
827 return root;
828}
829
830//! @brief Destroy the splay subtree.
831//! @param root - root of the subtree
832static void destroy(const Node* root)
833{
834 if (!root)
835 {
836 return;
837 }
838
839 if (root->left)
840 {
841 destroy(root: root->left);
842 }
843 if (root->right)
844 {
845 destroy(root: root->right);
846 }
847
848 ::delete root;
849 root = nullptr;
850}
851
852//! @brief Search the node of splay subtree by key.
853//! @param root - root of the subtree
854//! @param key - key of the node
855//! @param cmp - compare function to compare keys
856//! @return node where the key is located
857static Node* search(Node* const root, const void* const key, const Compare cmp)
858{
859 if (!root || !key || !cmp)
860 {
861 return nullptr;
862 }
863 return (cmp(root->key, key) == 0) ? root : search(root: (cmp(key, root->key) < 0) ? root->left : root->right, key, cmp);
864}
865
866//! @brief Splay the node in the splay subtree. Make to be the root node.
867//! @param root - root of the subtree
868//! @param key - key of the target node
869//! @param cmp - compare function to compare keys
870//! @return root node after splaying
871static Node* splay(Node* root, const void* const key, const Compare cmp)
872{
873 if (!root || !key || !cmp)
874 {
875 return root;
876 }
877
878 Node n{};
879 Node* l = nullptr;
880 Node* r = nullptr;
881 n.left = n.right = nullptr;
882 l = r = &n;
883 while (cmp(key, root->key) != 0)
884 {
885 if (cmp(key, root->key) < 0)
886 {
887 if (root->left && (cmp(key, root->left->key) < 0))
888 {
889 Node* c = root->left;
890 root->left = c->right;
891 c->right = root;
892 root = c;
893 }
894
895 if (!root->left)
896 {
897 break;
898 }
899 r->left = root;
900 r = root;
901 root = root->left;
902 }
903 else if (cmp(key, root->key) > 0)
904 {
905 if (root->right && (cmp(key, root->right->key) > 0))
906 {
907 Node* c = root->right;
908 root->right = c->left;
909 c->left = root;
910 root = c;
911 }
912
913 if (!root->right)
914 {
915 break;
916 }
917 l->right = root;
918 l = root;
919 root = root->right;
920 }
921 }
922
923 l->right = root->left;
924 r->left = root->right;
925 root->left = n.right;
926 root->right = n.left;
927 return root;
928}
929
930//! @brief Insert the node into the splay subtree. Not allow inserting node with the same key.
931//! @param root - root of the subtree
932//! @param key - key of the target node
933//! @param cmp - compare function to compare keys
934//! @return root node after inserting
935static Node* insert(Node* root, const void* const key, const Compare cmp)
936{
937 Node* const z = createNode(key, left: nullptr, right: nullptr);
938 if (!z)
939 {
940 return root;
941 }
942
943 root = insertNode(root, node: z, cmp);
944 root = splay(root, key, cmp);
945 return root;
946}
947
948//! @brief Remove the node from the splay subtree.
949//! @param root - root of the subtree
950//! @param key - key of the target node
951//! @param cmp - compare function to compare keys
952//! @return root node after removing
953static Node* remove(Node* root, const void* const key, const Compare cmp)
954{
955 if (!root || !search(root, key, cmp))
956 {
957 return root;
958 }
959
960 Node* x = nullptr;
961 root = splay(root, key, cmp);
962 if (root->left)
963 {
964 x = splay(root: root->left, key, cmp);
965 x->right = root->right;
966 }
967 else
968 {
969 x = root->right;
970 }
971
972 ::delete root;
973 root = nullptr;
974 return x;
975}
976
977//! @brief Get the node where the minimum key is located in the splay tree.
978//! @param tree - splay tree
979//! @return node where the minimum key is located
980Node* getMinimum(const SplayTree* const tree)
981{
982 return tree ? getMinimum(root: tree->root) : nullptr;
983}
984
985//! @brief Get the node where the maximum key is located in the splay tree.
986//! @param tree - splay tree
987//! @return node where the maximum key is located
988Node* getMaximum(const SplayTree* const tree)
989{
990 return tree ? getMaximum(root: tree->root) : nullptr;
991}
992
993//! @brief Create the splay tree.
994//! @param cmp - compare function to compare keys
995//! @return new splay tree
996SplayTree* create(const Compare cmp)
997{
998 if (!cmp)
999 {
1000 return nullptr;
1001 }
1002
1003 auto* const tree = ::new (std::nothrow) SplayTree;
1004 if (!tree)
1005 {
1006 return nullptr;
1007 }
1008
1009 tree->root = nullptr;
1010 tree->compare = cmp;
1011 return tree;
1012}
1013
1014//! @brief Destroy the splay tree.
1015//! @param tree - splay tree
1016void destroy(const SplayTree* tree)
1017{
1018 if (!tree)
1019 {
1020 return;
1021 }
1022
1023 destroy(root: tree->root);
1024 ::delete tree;
1025 tree = nullptr;
1026}
1027
1028//! @brief Search the node of splay tree by key.
1029//! @param tree - splay tree
1030//! @param key - key of the node
1031//! @return node where the key is located
1032Node* search(const SplayTree* const tree, const void* const key)
1033{
1034 return tree ? search(root: tree->root, key, cmp: tree->compare) : nullptr;
1035}
1036
1037//! @brief Insert the node into the splay tree. Not allow inserting node with the same key.
1038//! @param tree - splay tree
1039//! @param key - key of the target node
1040void insert(SplayTree* const tree, const void* const key)
1041{
1042 if (!tree)
1043 {
1044 return;
1045 }
1046
1047 tree->root = insert(root: tree->root, key, cmp: tree->compare);
1048}
1049
1050//! @brief Remove the node from the splay tree.
1051//! @param tree - splay tree
1052//! @param key - key of the target node
1053void remove(SplayTree* const tree, const void* const key)
1054{
1055 if (!tree)
1056 {
1057 return;
1058 }
1059
1060 tree->root = remove(root: tree->root, key, cmp: tree->compare);
1061}
1062
1063//! @brief Splay the node in the splay tree. Make to be the root node.
1064//! @param tree - splay tree
1065//! @param key - key of the target node
1066void splay(SplayTree* const tree, const void* const key)
1067{
1068 if (!tree)
1069 {
1070 return;
1071 }
1072
1073 tree->root = splay(root: tree->root, key, cmp: tree->compare);
1074}
1075} // namespace splay
1076// NOLINTEND(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
1077} // namespace data_structure::tree
1078