1//! @file tree.hpp
2//! @author ryftchen
3//! @brief The declarations (tree) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <functional>
10#include <ostream>
11
12//! @brief The data structure module.
13namespace data_structure // NOLINT(modernize-concat-nested-namespaces)
14{
15//! @brief Tree-related functions in the data structure module.
16namespace tree
17{
18//! @brief Brief function description.
19//! @return function description (module_function)
20inline static const char* description() noexcept
21{
22 return "DS_TREE";
23}
24extern const char* version() noexcept;
25
26//! @brief The binary search tree.
27namespace bs
28{
29#ifdef __cplusplus
30extern "C"
31{
32#endif
33 //! @brief Alias for the compare function type.
34 typedef int (*Compare)(const void* const, const void* const);
35
36#pragma pack(push, 8)
37 //! @brief The node of the BS tree.
38 typedef struct BSTreeNode
39 {
40 //! @brief Pointer to the left child node.
41 struct BSTreeNode* left;
42 //! @brief Pointer to the right child node.
43 struct BSTreeNode* right;
44 //! @brief Pointer to the parent node.
45 struct BSTreeNode* parent;
46 //! @brief Key value.
47 void* key;
48 } Node;
49
50 //! @brief The BS tree structure.
51 struct BSTree
52 {
53 //! @brief Pointer to the root node.
54 struct BSTreeNode* root;
55 //! @brief The key's compare function.
56 Compare compare;
57 };
58#pragma pack(pop)
59#ifdef __cplusplus
60}
61#endif
62
63extern Node* getMinimum(const BSTree* const tree);
64extern Node* getMaximum(const BSTree* const tree);
65extern Node* getPredecessor(const Node* x);
66extern Node* getSuccessor(const Node* x);
67
68extern BSTree* create(const Compare cmp);
69extern void destroy(const BSTree* tree);
70extern Node* search(const BSTree* const tree, const void* const key);
71extern void insert(BSTree* const tree, const void* const key);
72extern void remove(BSTree* const tree, const void* const key);
73} // namespace bs
74
75//! @brief The Adelson-Velsky-Landis tree.
76namespace avl
77{
78#ifdef __cplusplus
79extern "C"
80{
81#endif
82 //! @brief Alias for the compare function type.
83 typedef int (*Compare)(const void* const, const void* const);
84
85#pragma pack(push, 8)
86 //! @brief The node of the AVL tree.
87 typedef struct AVLTreeNode
88 {
89 //! @brief Pointer to the left child node.
90 struct AVLTreeNode* left;
91 //! @brief Pointer to the right child node.
92 struct AVLTreeNode* right;
93 //! @brief Key value.
94 void* key;
95 //! @brief The height of an empty tree is 0, and the height of a non-empty tree is equal to its maximum level.
96 int height;
97 } Node;
98
99 //! @brief The AVL tree structure.
100 struct AVLTree
101 {
102 //! @brief Pointer to the root node.
103 struct AVLTreeNode* root;
104 //! @brief The key's compare function.
105 Compare compare;
106 };
107#pragma pack(pop)
108#ifdef __cplusplus
109}
110#endif
111
112extern int getHeight(const AVLTree* const tree);
113extern Node* getMinimum(const AVLTree* const tree);
114extern Node* getMaximum(const AVLTree* const tree);
115
116extern AVLTree* create(const Compare cmp);
117extern void destroy(const AVLTree* tree);
118extern Node* search(const AVLTree* const tree, const void* const key);
119extern void insert(AVLTree* const tree, const void* const key);
120extern void remove(AVLTree* const tree, const void* const key);
121} // namespace avl
122
123//! @brief The splay tree.
124namespace splay
125{
126#ifdef __cplusplus
127extern "C"
128{
129#endif
130 //! @brief Alias for the compare function type.
131 typedef int (*Compare)(const void* const, const void* const);
132
133#pragma pack(push, 8)
134 //! @brief The node of the splay tree.
135 typedef struct SplayTreeNode
136 {
137 //! @brief Pointer to the left child node.
138 struct SplayTreeNode* left;
139 //! @brief Pointer to the right child node.
140 struct SplayTreeNode* right;
141 //! @brief Key value.
142 void* key;
143 } Node;
144
145 //! @brief The splay tree structure.
146 struct SplayTree
147 {
148 //! @brief Pointer to the root node.
149 struct SplayTreeNode* root;
150 //! @brief The key's compare function.
151 Compare compare;
152 };
153#pragma pack(pop)
154#ifdef __cplusplus
155}
156#endif
157
158extern Node* getMinimum(const SplayTree* const tree);
159extern Node* getMaximum(const SplayTree* const tree);
160
161extern SplayTree* create(const Compare cmp);
162extern void destroy(const SplayTree* tree);
163extern Node* search(const SplayTree* const tree, const void* const key);
164extern void insert(SplayTree* const tree, const void* const key);
165extern void remove(SplayTree* const tree, const void* const key);
166extern void splay(SplayTree* const tree, const void* const key);
167} // namespace splay
168
169//! @brief Do traversing.
170//! @tparam Tree - type of tree
171//! @tparam Node - type of tree node
172template <typename Tree, typename Node>
173class Traverse
174{
175public:
176 //! @brief Construct a new Traverse object.
177 //! @param tree - tree structure to be traversed
178 explicit Traverse(const Tree* const tree) : tree{tree} {}
179
180 //! @brief Alias for the operation when traversing.
181 using Operation = std::function<void(const void* const)>;
182 //! @brief Perform a pre-order traversal of the tree.
183 //! @param op - operation on each node
184 void preOrder(const Operation& op) const;
185 //! @brief Perform a in-order traversal of the tree.
186 //! @param op - operation on each node
187 void inOrder(const Operation& op) const;
188 //! @brief Perform a post-order traversal of the tree.
189 //! @param op - operation on each node
190 void postOrder(const Operation& op) const;
191
192private:
193 //! @brief The tree structure to be traversed.
194 const Tree* const tree{nullptr};
195 //! @brief Perform a pre-order traversal of the subtree.
196 //! @param node - root of the subtree
197 //! @param op - operation on each node
198 static void preOrderTraversal(const Node* const node, const Operation& op);
199 //! @brief Perform a in-order traversal of the subtree.
200 //! @param node - root of the subtree
201 //! @param op - operation on each node
202 static void inOrderTraversal(const Node* const node, const Operation& op);
203 //! @brief Perform a post-order traversal of the subtree.
204 //! @param node - root of the subtree
205 //! @param op - operation on each node
206 static void postOrderTraversal(const Node* const node, const Operation& op);
207};
208
209template <typename Tree, typename Node>
210void Traverse<Tree, Node>::preOrder(const Operation& op) const
211{
212 if (!tree || !op)
213 {
214 return;
215 }
216
217 preOrderTraversal(node: tree->root, op);
218}
219
220template <typename Tree, typename Node>
221void Traverse<Tree, Node>::inOrder(const Operation& op) const
222{
223 if (!tree || !op)
224 {
225 return;
226 }
227
228 inOrderTraversal(node: tree->root, op);
229}
230
231template <typename Tree, typename Node>
232void Traverse<Tree, Node>::postOrder(const Operation& op) const
233{
234 if (!tree || !op)
235 {
236 return;
237 }
238
239 postOrderTraversal(node: tree->root, op);
240}
241
242template <typename Tree, typename Node>
243void Traverse<Tree, Node>::preOrderTraversal(const Node* const node, const Operation& op)
244{
245 if (!node)
246 {
247 return;
248 }
249
250 op(node->key);
251 preOrderTraversal(node: node->left, op);
252 preOrderTraversal(node: node->right, op);
253}
254
255template <typename Tree, typename Node>
256void Traverse<Tree, Node>::inOrderTraversal(const Node* const node, const Operation& op)
257{
258 if (!node)
259 {
260 return;
261 }
262
263 inOrderTraversal(node: node->left, op);
264 op(node->key);
265 inOrderTraversal(node: node->right, op);
266}
267
268template <typename Tree, typename Node>
269void Traverse<Tree, Node>::postOrderTraversal(const Node* const node, const Operation& op)
270{
271 if (!node)
272 {
273 return;
274 }
275
276 postOrderTraversal(node: node->left, op);
277 postOrderTraversal(node: node->right, op);
278 op(node->key);
279}
280
281//! @brief Print the tree structure.
282//! @tparam Node - type of tree node
283//! @tparam Key - type of node key
284template <typename Node, typename Key>
285class Printer
286{
287public:
288 //! @brief Construct a new Printer object.
289 //! @param root - root of the tree
290 explicit Printer(const Node* const root) : root{root} {}
291
292 //! @brief Print the node in the tree.
293 //! @param os - output stream object
294 //! @param node - root of the subtree
295 //! @param key - key of the node
296 //! @param direction - node type, the left is -1, the root is 0, and the right is 1
297 void printNode(std::ostream& os, const Node* const node, const void* const key, const int direction) const;
298
299private:
300 //! @brief The root of the tree.
301 const Node* const root{nullptr};
302 //! @brief Indentation size.
303 mutable int indent{0};
304
305protected:
306 template <typename TN, typename NK>
307 friend std::ostream& operator<<(std::ostream&, const Printer<TN, NK>&);
308};
309
310template <typename Node, typename Key>
311void Printer<Node, Key>::printNode(
312 std::ostream& os, const Node* const node, const void* const key, const int direction) const
313{
314 if (!node || !key)
315 {
316 return;
317 }
318
319 const int currInd = indent;
320 if (direction == 0)
321 {
322 indent = 0;
323 os << "+ " << *static_cast<const Key*>(node->key) << " -> root\n";
324 }
325 else
326 {
327 os << "+ " << std::string(currInd, ' ') << *static_cast<const Key*>(node->key) << " -> "
328 << *static_cast<const Key*>(key) << "'s " << ((direction == 1) ? "right" : "left") << " child\n";
329 }
330
331 indent += 2;
332 printNode(os, node: node->left, key: node->key, direction: -1);
333 printNode(os, node: node->right, key: node->key, direction: 1);
334 indent = currInd;
335}
336
337//! @brief The operator (<<) overloading of the Printer class.
338//! @tparam TN - type of tree node
339//! @tparam NK - type of node key
340//! @param os - output stream object
341//! @param printer - specific Printer object
342//! @return reference of the output stream object
343template <typename TN, typename NK>
344std::ostream& operator<<(std::ostream& os, const Printer<TN, NK>& printer)
345{
346 if (printer.root)
347 {
348 printer.printNode(os, printer.root, printer.root->key, 0);
349 }
350 return os;
351}
352} // namespace tree
353} // namespace data_structure
354