TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
Public Member Functions | Private Attributes | List of all members
RBtree Class Reference
Collaboration diagram for RBtree:
[legend]

Public Member Functions

void insert ()
 
void insertfix (node *)
 
void leftrotate (node *)
 
void rightrotate (node *)
 
void del ()
 
node * successor (node *)
 
void delfix (node *)
 
void disp ()
 
void display (node *)
 
void search ()
 

Private Attributes

node * root
 
node * q
 

Detailed Description

Definition at line 13 of file rb_tree.cpp.

Constructor & Destructor Documentation

◆ RBtree()

RBtree::RBtree ( )
inline

Definition at line 18 of file rb_tree.cpp.

19 {
20 q = NULL;
21 root = NULL;
22 }

Member Function Documentation

◆ del()

void RBtree::del ( )

Definition at line 135 of file rb_tree.cpp.

136{
137 if (root == NULL)
138 {
139 cout << "\nEmpty Tree.";
140 return;
141 }
142 int x;
143 cout << "\nEnter the key of the node to be deleted: ";
144 cin >> x;
145 node *p;
146 p = root;
147 node *y = NULL;
148 node *q = NULL;
149 int found = 0;
150 while (p != NULL && found == 0)
151 {
152 if (p->key == x)
153 found = 1;
154 if (found == 0)
155 {
156 if (p->key < x)
157 p = p->right;
158 else
159 p = p->left;
160 }
161 }
162 if (found == 0)
163 {
164 cout << "\nElement Not Found.";
165 return;
166 }
167 else
168 {
169 cout << "\nDeleted Element: " << p->key;
170 cout << "\nColour: ";
171 if (p->color == 'b')
172 cout << "Black\n";
173 else
174 cout << "Red\n";
175
176 if (p->parent != NULL)
177 cout << "\nParent: " << p->parent->key;
178 else
179 cout << "\nThere is no parent of the node. ";
180 if (p->right != NULL)
181 cout << "\nRight Child: " << p->right->key;
182 else
183 cout << "\nThere is no right child of the node. ";
184 if (p->left != NULL)
185 cout << "\nLeft Child: " << p->left->key;
186 else
187 cout << "\nThere is no left child of the node. ";
188 cout << "\nNode Deleted.";
189 if (p->left == NULL || p->right == NULL)
190 y = p;
191 else
192 y = successor(p);
193 if (y->left != NULL)
194 q = y->left;
195 else
196 {
197 if (y->right != NULL)
198 q = y->right;
199 else
200 q = NULL;
201 }
202 if (q != NULL)
203 q->parent = y->parent;
204 if (y->parent == NULL)
205 root = q;
206 else
207 {
208 if (y == y->parent->left)
209 y->parent->left = q;
210 else
211 y->parent->right = q;
212 }
213 if (y != p)
214 {
215 p->color = y->color;
216 p->key = y->key;
217 }
218 if (y->color == 'b')
219 delfix(q);
220 }
221}

◆ delfix()

void RBtree::delfix ( node * p)

Definition at line 223 of file rb_tree.cpp.

224{
225 node *s;
226 while (p != root && p->color == 'b')
227 {
228 if (p->parent->left == p)
229 {
230 s = p->parent->right;
231 if (s->color == 'r')
232 {
233 s->color = 'b';
234 p->parent->color = 'r';
235 leftrotate(p->parent);
236 s = p->parent->right;
237 }
238 if (s->right->color == 'b'&&s->left->color == 'b')
239 {
240 s->color = 'r';
241 p = p->parent;
242 }
243 else
244 {
245 if (s->right->color == 'b')
246 {
247 s->left->color = 'b';
248 s->color = 'r';
249 rightrotate(s);
250 s = p->parent->right;
251 }
252 s->color = p->parent->color;
253 p->parent->color = 'b';
254 s->right->color = 'b';
255 leftrotate(p->parent);
256 p = root;
257 }
258 }
259 else
260 {
261 s = p->parent->left;
262 if (s->color == 'r')
263 {
264 s->color = 'b';
265 p->parent->color = 'r';
266 rightrotate(p->parent);
267 s = p->parent->left;
268 }
269 if (s->left->color == 'b'&&s->right->color == 'b')
270 {
271 s->color = 'r';
272 p = p->parent;
273 }
274 else
275 {
276 if (s->left->color == 'b')
277 {
278 s->right->color = 'b';
279 s->color = 'r';
280 leftrotate(s);
281 s = p->parent->left;
282 }
283 s->color = p->parent->color;
284 p->parent->color = 'b';
285 s->left->color = 'b';
286 rightrotate(p->parent);
287 p = root;
288 }
289 }
290 p->color = 'b';
291 root->color = 'b';
292 }
293}

◆ disp()

void RBtree::disp ( )

Definition at line 372 of file rb_tree.cpp.

373{
374 display(root);
375}

◆ display()

void RBtree::display ( node * p)

Definition at line 376 of file rb_tree.cpp.

377{
378 if (root == NULL)
379 {
380 cout << "\nEmpty Tree.";
381 return;
382 }
383 if (p != NULL)
384 {
385 cout << "\n\t NODE: ";
386 cout << "\n Key: " << p->key;
387 cout << "\n Colour: ";
388 if (p->color == 'b')
389 cout << "Black";
390 else
391 cout << "Red";
392 if (p->parent != NULL)
393 cout << "\n Parent: " << p->parent->key;
394 else
395 cout << "\n There is no parent of the node. ";
396 if (p->right != NULL)
397 cout << "\n Right Child: " << p->right->key;
398 else
399 cout << "\n There is no right child of the node. ";
400 if (p->left != NULL)
401 cout << "\n Left Child: " << p->left->key;
402 else
403 cout << "\n There is no left child of the node. ";
404 cout << endl;
405 if (p->left)
406 {
407 cout << "\n\nLeft:\n";
408 display(p->left);
409 }
410 /*else
411 cout<<"\nNo Left Child.\n";*/
412 if (p->right)
413 {
414 cout << "\n\nRight:\n";
415 display(p->right);
416 }
417 /*else
418 cout<<"\nNo Right Child.\n"*/
419 }
420}
endl
#define endl
Definition matrix_exponentiation.cpp:36

◆ insert()

void RBtree::insert ( )

Definition at line 34 of file rb_tree.cpp.

35{
36 int z, i = 0;
37 cout << "\nEnter key of the node to be inserted: ";
38 cin >> z;
39 node *p, *q;
40 node *t = new node;
41 t->key = z;
42 t->left = NULL;
43 t->right = NULL;
44 t->color = 'r';
45 p = root;
46 q = NULL;
47 if (root == NULL)
48 {
49 root = t;
50 t->parent = NULL;
51 }
52 else
53 {
54 while (p != NULL)
55 {
56 q = p;
57 if (p->key < t->key)
58 p = p->right;
59 else
60 p = p->left;
61 }
62 t->parent = q;
63 if (q->key < t->key)
64 q->right = t;
65 else
66 q->left = t;
67 }
68 insertfix(t);
69}
node
struct node { int data; int height; struct node *left; struct node *right;} node
for std::queue
Definition avltree.cpp:13

◆ insertfix()

void RBtree::insertfix ( node * t)

Definition at line 70 of file rb_tree.cpp.

71{
72 node *u;
73 if (root == t)
74 {
75 t->color = 'b';
76 return;
77 }
78 while (t->parent != NULL && t->parent->color == 'r')
79 {
80 node *g = t->parent->parent;
81 if (g->left == t->parent)
82 {
83 if (g->right != NULL)
84 {
85 u = g->right;
86 if (u->color == 'r')
87 {
88 t->parent->color = 'b';
89 u->color = 'b';
90 g->color = 'r';
91 t = g;
92 }
93 }
94 else
95 {
96 if (t->parent->right == t)
97 {
98 t = t->parent;
99 leftrotate(t);
100 }
101 t->parent->color = 'b';
102 g->color = 'r';
103 rightrotate(g);
104 }
105 }
106 else
107 {
108 if (g->left != NULL)
109 {
110 u = g->left;
111 if (u->color == 'r')
112 {
113 t->parent->color = 'b';
114 u->color = 'b';
115 g->color = 'r';
116 t = g;
117 }
118 }
119 else
120 {
121 if (t->parent->left == t)
122 {
123 t = t->parent;
124 rightrotate(t);
125 }
126 t->parent->color = 'b';
127 g->color = 'r';
128 leftrotate(g);
129 }
130 }
131 root->color = 'b';
132 }
133}
numerical_methods::simpson_method::g
double g(double x)
Another test function.
Definition composite_simpson_rule.cpp:115

◆ leftrotate()

void RBtree::leftrotate ( node * p)

Definition at line 295 of file rb_tree.cpp.

296{
297 if (p->right == NULL)
298 return;
299 else
300 {
301 node *y = p->right;
302 if (y->left != NULL)
303 {
304 p->right = y->left;
305 y->left->parent = p;
306 }
307 else
308 p->right = NULL;
309 if (p->parent != NULL)
310 y->parent = p->parent;
311 if (p->parent == NULL)
312 root = y;
313 else
314 {
315 if (p == p->parent->left)
316 p->parent->left = y;
317 else
318 p->parent->right = y;
319 }
320 y->left = p;
321 p->parent = y;
322 }
323}

◆ rightrotate()

void RBtree::rightrotate ( node * p)

Definition at line 324 of file rb_tree.cpp.

325{
326 if (p->left == NULL)
327 return;
328 else
329 {
330 node *y = p->left;
331 if (y->right != NULL)
332 {
333 p->left = y->right;
334 y->right->parent = p;
335 }
336 else
337 p->left = NULL;
338 if (p->parent != NULL)
339 y->parent = p->parent;
340 if (p->parent == NULL)
341 root = y;
342 else
343 {
344 if (p == p->parent->left)
345 p->parent->left = y;
346 else
347 p->parent->right = y;
348 }
349 y->right = p;
350 p->parent = y;
351 }
352}

◆ search()

void RBtree::search ( )

Definition at line 421 of file rb_tree.cpp.

422{
423 if (root == NULL)
424 {
425 cout << "\nEmpty Tree\n";
426 return;
427 }
428 int x;
429 cout << "\n Enter key of the node to be searched: ";
430 cin >> x;
431 node *p = root;
432 int found = 0;
433 while (p != NULL && found == 0)
434 {
435 if (p->key == x)
436 found = 1;
437 if (found == 0)
438 {
439 if (p->key < x)
440 p = p->right;
441 else
442 p = p->left;
443 }
444 }
445 if (found == 0)
446 cout << "\nElement Not Found.";
447 else
448 {
449 cout << "\n\t FOUND NODE: ";
450 cout << "\n Key: " << p->key;
451 cout << "\n Colour: ";
452 if (p->color == 'b')
453 cout << "Black";
454 else
455 cout << "Red";
456 if (p->parent != NULL)
457 cout << "\n Parent: " << p->parent->key;
458 else
459 cout << "\n There is no parent of the node. ";
460 if (p->right != NULL)
461 cout << "\n Right Child: " << p->right->key;
462 else
463 cout << "\n There is no right child of the node. ";
464 if (p->left != NULL)
465 cout << "\n Left Child: " << p->left->key;
466 else
467 cout << "\n There is no left child of the node. ";
468 cout << endl;
469
470 }
471}

◆ successor()

node * RBtree::successor ( node * p)

Definition at line 354 of file rb_tree.cpp.

355{
356 node *y = NULL;
357 if (p->left != NULL)
358 {
359 y = p->left;
360 while (y->right != NULL)
361 y = y->right;
362 }
363 else
364 {
365 y = p->right;
366 while (y->left != NULL)
367 y = y->left;
368 }
369 return y;
370}

Member Data Documentation

◆ q

node* RBtree::q
private

Definition at line 16 of file rb_tree.cpp.

◆ root

node* RBtree::root
private

Definition at line 15 of file rb_tree.cpp.

The documentation for this class was generated from the following file: