AlgoPlus v0.1.0
Loading...
Searching...
No Matches
red_black_tree.h
1#ifndef RED_BLACK_TREE_H
2#define RED_BLACK_TREE_H
3
4#ifdef ENABLE_TREE_VISUALIZATION
5#include "../../visualization/tree_visual/tree_visualization.h"
6#endif
7
8#ifdef __cplusplus
9#include <bitset>
10#include <functional>
11#include <memory>
12#include <queue>
13#include <vector>
14#endif
15
19template <typename T> class red_black_tree {
20 private:
29 typedef struct node {
30 T info;
31 std::bitset<1> is_red;
32 std::shared_ptr<node> parent;
33 std::shared_ptr<node> right;
34 std::shared_ptr<node> left;
35 node(T key, std::shared_ptr<node> p)
36 : info(key), is_red(1), parent(p), right(nullptr), left(nullptr) {}
37 } node;
38
39 std::shared_ptr<node> root;
40 size_t _size{};
41
42 void _left_rotate(std::shared_ptr<node> t_node) {
43 std::shared_ptr<node> x = t_node->right;
44 x->parent = t_node->parent;
45 if (t_node->parent == nullptr)
46 this->root = x;
47 else if (t_node->parent->left == t_node)
48 t_node->parent->left = x;
49 else
50 t_node->parent->right = x;
51
52 t_node->right = x->left;
53 if (t_node->right)
54 t_node->right->parent = t_node;
55 x->left = t_node;
56 t_node->parent = x;
57 }
58
59 void _right_rotate(std::shared_ptr<node> t_node) {
60 std::shared_ptr<node> x = t_node->left;
61 x->parent = t_node->parent;
62 if (t_node->parent == nullptr)
63 this->root = x;
64 else if (t_node->parent->left == t_node)
65 t_node->parent->left = x;
66 else
67 t_node->parent->right = x;
68
69 t_node->left = x->right;
70 if (t_node->left)
71 t_node->left->parent = t_node;
72 x->right = t_node;
73 t_node->parent = x;
74 }
75
76 void _insert(std::shared_ptr<node> t_node) {
77 while (t_node->parent && t_node->parent->is_red == 1) {
78 std::shared_ptr<node> grand_parent = t_node->parent->parent;
79 if (t_node->parent == grand_parent->left) {
80 std::shared_ptr<node> uncle = grand_parent->right;
81 if (uncle && uncle->is_red == 1) {
82 grand_parent->is_red = 1;
83 uncle->is_red = 0;
84 t_node->parent->is_red = 0;
85 t_node = grand_parent;
86 } else {
87 if (t_node == t_node->parent->right) {
88 t_node = t_node->parent;
89 _left_rotate(t_node);
90 }
91 grand_parent = t_node->parent->parent;
92 if (grand_parent)
93 grand_parent->is_red = 1;
94 t_node->parent->is_red = 0;
95 _right_rotate(grand_parent);
96 }
97 } else {
98 std::shared_ptr<node> uncle = grand_parent->left;
99 if (uncle && uncle->is_red == 1) {
100 grand_parent->is_red = 1;
101 uncle->is_red = 0;
102 t_node->parent->is_red = 0;
103 t_node = grand_parent;
104 } else {
105 if (t_node == t_node->parent->left) {
106 t_node = t_node->parent;
107 _right_rotate(t_node);
108 }
109 grand_parent = t_node->parent->parent;
110 if (grand_parent)
111 grand_parent->is_red = 1;
112 t_node->parent->is_red = 0;
113 _left_rotate(grand_parent);
114 }
115 }
116 }
117 this->root->is_red = 0;
118 }
119
120 void _remove_helper(std::shared_ptr<node> t_node) {
121 if (t_node == this->root)
122 return;
123 std::shared_ptr<node> sibling;
124 if (t_node->parent->left == t_node)
125 sibling = t_node->parent->right;
126 else
127 sibling = t_node->parent->left;
128 if (sibling == nullptr)
129 _remove_helper(t_node->parent);
130 else {
131 if (sibling->is_red == 1) {
132 t_node->parent->is_red = 1;
133 sibling->is_red = 0;
134 if (t_node->parent->left == sibling)
135 _right_rotate(t_node->parent);
136 else
137 _left_rotate(t_node->parent);
138 _remove_helper(t_node);
139 } else {
140 if (sibling->left && sibling->left->is_red == 1) {
141 if (t_node->parent->left == sibling) {
142 sibling->left->is_red = sibling->is_red;
143 sibling->is_red = t_node->parent->is_red;
144 _right_rotate(t_node->parent);
145 } else {
146 sibling->left->is_red = t_node->parent->is_red;
147 _right_rotate(sibling);
148 _left_rotate(t_node->parent);
149 }
150 t_node->parent->is_red = 0;
151 } else if (sibling->right && sibling->right->is_red == 1) {
152 if (t_node->parent->left == sibling) {
153 sibling->right->is_red = t_node->parent->is_red;
154 _left_rotate(sibling);
155 _right_rotate(t_node->parent);
156 } else {
157 sibling->right->is_red = sibling->is_red;
158 sibling->is_red = t_node->parent->is_red;
159 _left_rotate(t_node->parent);
160 }
161 t_node->parent->is_red = 0;
162 } else {
163 sibling->is_red = 1;
164 if (t_node->parent->is_red == 0)
165 _remove_helper(t_node->parent);
166 else
167 t_node->parent->is_red = 0;
168 }
169 }
170 }
171 }
172
173 void _remove(std::shared_ptr<node> t_node) {
174 if (t_node == nullptr)
175 return;
176 std::shared_ptr<node> replace = nullptr;
177 if (t_node->left && t_node->right) {
178 std::shared_ptr<node> tmp = t_node->right;
179 while (tmp->left)
180 tmp = tmp->left;
181 replace = tmp;
182 } else if (t_node->left)
183 replace = t_node->left;
184 else if (t_node->right)
185 replace = t_node->right;
186 if (replace == nullptr) {
187 if (t_node == this->root)
188 this->root = nullptr;
189 else {
190 if (t_node->is_red == 0)
191 _remove_helper(t_node);
192 else {
193 std::shared_ptr<node> sibling = nullptr;
194 if (t_node->parent->left == t_node)
195 sibling = t_node->parent->right;
196 else
197 sibling = t_node->parent->left;
198 if (sibling)
199 sibling->is_red = 1;
200 }
201 if (t_node->parent->left == t_node)
202 t_node->parent->left = nullptr;
203 else
204 t_node->parent->right = nullptr;
205 }
206 return;
207 }
208 if (t_node->left == nullptr || t_node->right == nullptr) {
209 if (t_node == this->root) {
210 t_node->info = replace->info;
211 t_node->left = nullptr;
212 t_node->right = nullptr;
213 t_node->is_red = 0;
214 } else {
215 if (t_node->parent->left == t_node)
216 t_node->parent->left = replace;
217 else
218 t_node->parent->right = replace;
219 replace->parent = t_node->parent;
220 if (replace->is_red == 0 && t_node->is_red == 0)
221 _remove_helper(replace);
222 else
223 replace->is_red = 0;
224 }
225 return;
226 }
227 t_node->info = replace->info;
228 _remove(replace);
229 }
230
231 bool _search(T& key) {
232 std::shared_ptr<node> t_node = this->root;
233 while (t_node) {
234 if (key < t_node->info)
235 t_node = t_node->left;
236 else if (key == t_node->info)
237 return true;
238 else
239 t_node = t_node->right;
240 }
241 return false;
242 }
243
244 void _inorder(std::function<void(T)> callback, std::shared_ptr<node> t_node) const {
245 if (t_node) {
246 _inorder(callback, t_node->left);
247 callback(t_node->info);
248 _inorder(callback, t_node->right);
249 }
250 }
251
252 void _postorder(std::function<void(T)> callback, std::shared_ptr<node> t_node) const {
253 if (t_node) {
254 _postorder(callback, t_node->left);
255 _postorder(callback, t_node->right);
256 callback(t_node->info);
257 }
258 }
259
260 void _preorder(std::function<void(T)> callback, std::shared_ptr<node> t_node) const {
261 if (t_node) {
262 callback(t_node->info);
263 _preorder(callback, t_node->left);
264 _preorder(callback, t_node->right);
265 }
266 }
267
268 std::string _vis_gen(std::shared_ptr<node> t_node, T parent_info) {
269 std::string _s = "";
270 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>) {
271 _s += t_node->info + " [shape=circle fontcolor=black color=";
272 if (t_node->is_red == 1)
273 _s += "red";
274 else
275 _s += "black";
276 _s += "]\n";
277 _s += parent_info + "->" + t_node->info + '\n';
278 } else {
279 _s += std::to_string(t_node->info) + " [shape=circle fontcolor=black color=";
280 if (t_node->is_red == 1)
281 _s += "red";
282 else
283 _s += "black";
284 _s += "]\n";
285 _s += std::to_string(parent_info) + "->" + std::to_string(t_node->info) + '\n';
286 }
287 if (t_node->left)
288 _s += _vis_gen(t_node->left, t_node->info);
289 if (t_node->right)
290 _s += _vis_gen(t_node->right, t_node->info);
291 return _s;
292 }
293
294 public:
300 inline explicit red_black_tree(std::vector<T> _elements = {}) noexcept : root(nullptr) {
301 for (T& x : _elements) {
302 this->insert(x);
303 }
304 }
305
310 inline explicit red_black_tree(const red_black_tree& rb) : root(rb.root), _size(rb._size) {}
311
315 inline ~red_black_tree() noexcept { root = nullptr; }
316
322 inline red_black_tree<T>& operator=(const red_black_tree<T>& rb) {
323 root = rb.root;
324 _size = rb._size;
325 return *this;
326 }
327
333 inline bool operator==(const red_black_tree<T>& rb) const { return this->root == rb.root; }
334
340 inline bool search(T key) { return _search(key); }
341
346 inline void insert(T key) {
347 std::shared_ptr<node> p = nullptr;
348 std::shared_ptr<node> x = this->root;
349 while (x) {
350 p = x;
351 if (key < x->info)
352 x = x->left;
353 else
354 x = x->right;
355 }
356 std::shared_ptr<node> t_node = std::make_shared<node>(key, p);
357 if (p == nullptr)
358 this->root = t_node;
359 else {
360 if (key < p->info)
361 p->left = t_node;
362 else
363 p->right = t_node;
364 }
365 _insert(t_node);
366 _size += 1;
367 }
368
373 inline void remove(T key) {
374 std::shared_ptr<node> t_node = root;
375 while (t_node && t_node->info != key) {
376 if (key < t_node->info)
377 t_node = t_node->left;
378 else
379 t_node = t_node->right;
380 }
381 _remove(t_node);
382 _size -= 1;
383 }
384
390 inline size_t size() const { return _size; }
391
395 inline void clear() {
396 root = nullptr;
397 _size = 0;
398 }
399
404 inline std::vector<T> inorder() const {
405 std::vector<T> path;
406 _inorder([&](T callbacked) { path.push_back(callbacked); }, root);
407 return path;
408 }
409
414 inline std::vector<T> postorder() const {
415 std::vector<T> path;
416 _postorder([&](T callbacked) { path.push_back(callbacked); }, root);
417 return path;
418 }
419
424 inline std::vector<T> preorder() const {
425 std::vector<T> path;
426 _preorder([&](T callbacked) { path.push_back(callbacked); }, root);
427 return path;
428 }
429
434 inline std::vector<std::vector<T>> level_order() const {
435 std::vector<std::vector<T>> path;
436 std::queue<std::shared_ptr<node>> q;
437 q.push(root);
438 while (!q.empty()) {
439 size_t size = q.size();
440 std::vector<T> level;
441 for (size_t i = 0; i < size; i++) {
442 std::shared_ptr<node> current = q.front();
443 q.pop();
444 level.push_back(current->info);
445 if (current->left) {
446 q.push(current->left);
447 }
448 if (current->right) {
449 q.push(current->right);
450 }
451 }
452 path.push_back(level);
453 }
454 return path;
455 }
456
460 inline friend std::ostream& operator<<(std::ostream& out, red_black_tree<T>& rb) {
461 std::vector<T> order = rb.inorder();
462 for (int i = 0; i < order.size(); i++) {
463 if (i == order.size() - 1)
464 out << order[i] << '\n';
465 else
466 out << order[i] << ", ";
467 }
468 return out;
469 }
470
471 class Iterator;
472
477 inline Iterator begin() {
478 std::vector<T> ino = this->inorder();
479 return Iterator(0, ino);
480 }
481
486 inline Iterator end() {
487 std::vector<T> ino = this->inorder();
488 return Iterator(ino.size(), ino);
489 }
490
495#ifdef TREE_VISUALIZATION_H
496 inline void visualize() {
497 std::string _generated;
498 if (this->root) {
499 if (std::is_same_v<T, char> || std::is_same_v<T, std::string>)
500 _generated += root->info;
501 else
502 _generated += std::to_string(root->info);
503 _generated += " [shape=circle fontcolor=black color=";
504 if (root->is_red == 1)
505 _generated += "red]\n";
506 else
507 _generated += "black]\n";
508 if (this->root->left)
509 _generated += this->_vis_gen(this->root->left, root->info);
510 if (this->root->right)
511 _generated += this->_vis_gen(this->root->right, root->info);
512 }
513 tree_visualization::visualize(_generated);
514 }
515#endif
516};
517
521template <typename T> class red_black_tree<T>::Iterator {
522 private:
523 std::vector<T> elements;
524 int64_t index;
525
526 public:
532 explicit Iterator(const int64_t& index, std::vector<T>& els) noexcept
533 : index(index), elements(els) {}
534
541 Iterator& operator=(int64_t index) {
542 this->index = index;
543 return *(this);
544 }
545
551 Iterator& operator++() {
552 if (this->index < elements.size()) {
553 this->index++;
554 }
555 return *(this);
556 }
557
563 Iterator operator++(int) {
564 Iterator it = *this;
565 ++*(this);
566 return it;
567 }
568
574 Iterator& operator--() {
575 if (this->index > 0) {
576 this->index--;
577 }
578 return *(this);
579 }
580
586 Iterator operator--(int) {
587 Iterator it = *this;
588 --*(this);
589 return it;
590 }
591
599 bool operator!=(const Iterator& it) { return index != it.index; }
600
606 T operator*() { return elements[index]; }
607};
608
609#endif
red_black_tree::Iterator
Iterator class.
Definition red_black_tree.h:521
red_black_tree::Iterator::operator!=
bool operator!=(const Iterator &it)
operator != for type Iterator
Definition red_black_tree.h:599
red_black_tree::Iterator::operator=
Iterator & operator=(int64_t index)
= operator for Iterator type
Definition red_black_tree.h:541
red_black_tree::Iterator::operator--
Iterator & operator--()
operator – for type Iterator
Definition red_black_tree.h:574
red_black_tree::Iterator::operator*
T operator*()
operator * for type Iterator
Definition red_black_tree.h:606
red_black_tree::Iterator::Iterator
Iterator(const int64_t &index, std::vector< T > &els) noexcept
Construct a new Iterator object.
Definition red_black_tree.h:532
red_black_tree::Iterator::operator++
Iterator operator++(int)
operator ++ for type Iterator
Definition red_black_tree.h:563
red_black_tree::Iterator::operator--
Iterator operator--(int)
operator – for type Iterator
Definition red_black_tree.h:586
red_black_tree::Iterator::operator++
Iterator & operator++()
operator ++ for type Iterator
Definition red_black_tree.h:551
red_black_tree::inorder
std::vector< T > inorder() const
inorder function.
Definition red_black_tree.h:404
red_black_tree::begin
Iterator begin()
pointer that points to begin
Definition red_black_tree.h:477
red_black_tree::operator=
red_black_tree< T > & operator=(const red_black_tree< T > &rb)
operator = for red black tree class
Definition red_black_tree.h:322
red_black_tree::level_order
std::vector< std::vector< T > > level_order() const
level order function
Definition red_black_tree.h:434
red_black_tree::~red_black_tree
~red_black_tree() noexcept
Destructor for red black tree class.
Definition red_black_tree.h:315
red_black_tree::red_black_tree
red_black_tree(std::vector< T > _elements={}) noexcept
Contructor for red black tree class.
Definition red_black_tree.h:300
red_black_tree::operator<<
friend std::ostream & operator<<(std::ostream &out, red_black_tree< T > &rb)
operator << for red black tree class
Definition red_black_tree.h:460
red_black_tree::postorder
std::vector< T > postorder() const
postorder function.
Definition red_black_tree.h:414
red_black_tree::preorder
std::vector< T > preorder() const
preorder function.
Definition red_black_tree.h:424
red_black_tree::operator==
bool operator==(const red_black_tree< T > &rb) const
operator == for red black tree class
Definition red_black_tree.h:333
red_black_tree::clear
void clear()
clear function
Definition red_black_tree.h:395
red_black_tree::red_black_tree
red_black_tree(const red_black_tree &rb)
Copy constructor for red black tree class.
Definition red_black_tree.h:310
red_black_tree::size
size_t size() const
size function
Definition red_black_tree.h:390
red_black_tree::search
bool search(T key)
search function.
Definition red_black_tree.h:340
red_black_tree::insert
void insert(T key)
insert function.
Definition red_black_tree.h:346
red_black_tree::end
Iterator end()
pointer that points to end
Definition red_black_tree.h:486
red_black_tree::remove
void remove(T key)
remove function.
Definition red_black_tree.h:373
Generated by doxygen 1.13.2