Actividad de Aprendizaje 13 El Árbol AVL, implementación dinámica - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Estructura de datos I
Actividad de Aprendizaje 13. El Árbol AVL, implementación dinámica
Alumno: Sandoval Padilla Fernando Cesar
Docente: Gutiérrez Hernández Alfredo
Código: 215685409
Sección: D12
	
			
 23 de Noviembre de 2019
Resumen personal:
La realización de esta actividad fue bastante sencilla, así que solo fue necesario implementar el árbol AVL al primer árbol, lo cual no fue complejo logrando así hacer mas eficiente el programa para trabajar con un mayor número de elementos.
Código fuente:
Main.cpp
1 #include <iostream>
2 #include <chrono>
3 #include <random>
4 #include <functional>
5
6 #include "btree.h"
7
8 using namespace std;
9
10 int main() {
11 default_random_engine generator(chrono::system_clock::now().time_since_epoch().count());
12 uniform_int_distribution<int> intDistribution(0, 100000);
13 auto intDice = bind(intDistribution, generator);
14
15 BTree<int> myArbol;
16 int data, cant;
17
18 cout<<"Cuantos numeros desea en su arbol? ";
19 cin>>cant;
20
21
22 try {
23 for(int i(0); i < cant; i++) {
24 data = intDice();
25 cout << i+1 <<". Insertando: " << data << endl;
26
27 myArbol.insertData(data);
28 }
29 }
30 catch(BTree<int>::Exception ex) {
31 cout << ex.what() << endl;
32 }
33
34 cout << endl << endl;
35
36 cout << "Preorder = ";
37 myArbol.parsePreOrder();
38
39 cout << endl << endl;
40
41 cout << "Inorder = ";
42 myArbol.parseInOrder();
43
44 cout << endl << endl;
45
46 cout << "Postorder = ";
47 myArbol.parsePostOrder();
48
49 cout << endl << endl;
50
51 cout << "Altura del subarbol Izquierdo: " << myArbol.getHeightLeft() << endl;
52
53 cout << endl << endl;
54
55 cout << "Altura del subarbol Derecho: " << myArbol.getHeightRight() << endl;
56
57 cout << endl << endl;
58
59 cout << "Altura del arbol: " << myArbol.getHeight() << endl;
60
61 cout << endl << endl;
62
63 return 0;
64 }
btree.h
1 /*
2 Optimizar el arbol:
3 - atributo de saber cual es la altura de cada sub-arbol
4 - atributo de lista doblemente ligados (Cada hijo sabe cual es su padre)
5
6 Elemento faltante:
7 - Eliminar dato
8 */
9
10 #ifndef BTREE_H_INCLUDED
11 #define BTREE_H_INCLUDED
12
13 #include <exception>
14 #include <string>
15
16 template <class T>
17 class BTree {
18 public:
19 class Node {
20 private:
21 T* dataPtr;
22 Node* left;
23 Node* right;
24
25 public:
26 class Exception : public std::exception {
27 private:
28 std::string msg;
29
30 public:
31 explicit Exception(const char* message) : msg(message) { }
32
33 explicit Exception(const std::string& message) : msg(message) { }
34
35 virtual ~Exception() throw () { }
36
37 virtual const char* what() const throw () {
38 return msg.c_str();
39 }
40 };
41 Node();
42 Node(const T&);
43
44 ~Node();
45
46 T* getDataPtr();
47 T& getData();
48
49 Node*& getLeft();
50 Node*& getRight();
51
52 void setDataPTr(T*);
53 void setData(const T&);
54 void setLeft(Node*&);
55 void setRight(Node*&);
56 };
57
58 class Exception : public std::exception {
59 private:
60 std::string msg;
61
62 public:
63 explicit Exception(const char* message) : msg(message) { }
64
65 explicit Exception(const std::string& message) : msg(message) { }
66
67 virtual ~Exception() throw () { }
68
69 virtual const char* what() const throw () {
70 return msg.c_str();
71 }
72 };
73
74 private:
75 Node* root;
76
77 void copyAll(Node*&, Node*&);
78
79 void insertData(Node*&, const T&);
80
81 Node*& findData(Node*&, const T&);
82
83 void deleteAll(Node*&);
84
85 Node*& getTheLowest(Node*&);
86
87 Node*& getTheHighest(Node*&);
88
89 int getHeight(Node*&);
90
91 int getHeightRight(Node*&);
92
93 int getHeightLeft(Node*&);
94
95 void parsePreOrder(Node*&);
96
97 void parseInOrder(Node*&);
98
99 void parsePostOrder(Node*&);
100
101 int getBalanceFactor(Node*&);
102
103 void doSimpleLeftRot(Node*&);
104
105 void doSimpleRightRot(Node*&);
106
107 void doDoubleLeftRot(Node*&);
108
109 void doDoubleRightRot(Node*&);
110
111 void doBalancing(Node*&);
112
113 void swapData(T&, T&);
114
115 public:
116 BTree();
117 BTree(const BTree&);
118
119 ~BTree();
120
121 bool isEmpty() const;
122
123 void insertData(const T&);
124
125 Node*& findData(const T&);
126
127 T& retrieve(Node*&);
128
129 void parsePreOrder();
130
131 void parseInOrder();
132
133 void parsePostOrder();
134
135 void deleteData(Node*&);
136
137 bool isLeaf(Node*&) const;
138
139 int getHeight();
140
141 int getHeightRight();
142
143 int getHeightLeft();
144
145 void deleteAll();
146
147 BTree& operator = (const BTree&);
148 };
149
150 ///Nodo
151
152 template <class T>
153 BTree<T>::Node::Node() : dataPtr(nullptr), left(nullptr), right(nullptr) { }
154
155 template <class T>
156 BTree<T>::Node::Node(const T& e) : dataPtr(new T(e)), left(nullptr), right(nullptr) {
157 if(dataPtr == nullptr) {
158 throw Exception(" Memoria no disponible, creando nodo");
159 }
160 }
161
162 template <class T>
163 BTree<T>::Node::~Node() {
164 delete dataPtr;
165 }
166
167 template <class T>
168 T* BTree<T>::Node::getDataPtr() {
169 return dataPtr;
170 }
171
172 template <class T>
173 T& BTree<T>::Node::getData() {
174 return *dataPtr;
175 }
176
177 template <class T>
178 typename BTree<T>::Node*& BTree<T>::Node::getLeft() {
179 return left;
180 }
181
182 template <class T>
183 typename BTree<T>::Node*& BTree<T>::Node::getRight() {
184 return right;
185 }
186
187 template <class T>
188 void BTree<T>::Node::setDataPTr(T* p) {
189 dataPtr = p;
190 }
191
192 template <class T>
193 void BTree<T>::Node::setData(const T& e) {
194 if(dataPtr == nullptr and (dataPtr = new T(e)) == nullptr) {
195
196 throw Exception(" Memoria no disponible, Node::setData");
197 }
198 else {
199 *dataPtr = e;
200 }
201 }
202
203 template <class T>
204 void BTree<T>::Node::setLeft(BTree<T>::Node*& p) {
205 left = p;
206 }
207
208 template <class T>
209 void BTree<T>::Node::setRight(BTree<T>::Node*& p) {
210 right = p;
211 }
212
213 ///BTree
214
215 ///private
216
217 template <class T>
218 void BTree<T>::copyAll(Node*& orig, Node*& dest) {
219 if(orig == nullptr) {
220 return;
221 }
222
223 dest = new Node(orig->getData());
224
225 copyAll(orig->getLeft(), dest->getLeft());
226 copyAll(orig->getRight(), dest->getRight());
227 }
228
229 template <class T>
230 void BTree<T>::insertData(BTree<T>::Node*& r, const T& e) {
231 if(r == nullptr) { ///Inserta como hoja (balanceada) (no recursivo)
232 try {
233 if((r = new Node(e)) == nullptr) {
234 throw Exception(" Memoria no disponible, insertData.");
235 }
236 }
237 catch(typename Node::Exception ex) {
238 throw Exception(ex.what());
239 }
240
241 return;
242 }
243
244 ///Insercion recursiva
245 if(e < r->getData()) {
246 insertData(r->getLeft(), e);
247 }
248 else {
249 insertData(r->getRight(), e);
250 }
251 ///Aqui sale de la recursion
252
253 ///Revisar factor de equilibrio, aplicar rotaciones
254 doBalancing(r);
255 }
256
257 template <class T>
258 typename BTree<T>::Node*& BTree<T>::findData(BTree<T>::Node*& r, const T& e) {
259 if(r == nullptr or r->getData() == e) {
260 return r;
261 }
262
263 if(e < r->getData()) {
264 return findData(r->getLeft(), e);
265 }
266 else {
267 return findData(r->getRight(), e);
268 }
269 }
270
271 template <class T>
272 void BTree<T>::deleteAll(BTree<T>::Node*& r) {
273 if(r == nullptr) {
274 return;
275 }
276
277 deleteAll(r->getLeft());
278 deleteAll(r->getRight());
279
280 delete r;
281
282 r = nullptr;
283 }
284
285 template <class T>
286 typename BTree<T>::Node*& BTree<T>::getTheLowest(BTree<T>::Node*& r) {
287 if(r == nullptr or r->getLeft() == nullptr) {
288 return r;
289 }
290
291 return getTheLowest(r->getLeft());
292 }
293
294 template <class T>
295 typename BTree<T>::Node*& BTree<T>::getTheHighest(BTree<T>::Node*& r) {
296 if(r == nullptr or r->getRight() == nullptr) {
297 return r;
298 }
299
300 return getTheHighest(r->getRight());
301 }
302
303 template <class T>
304 int BTree<T>::getHeight(BTree<T>::Node*& r) {
305 if(r == nullptr) {
306 return 0;
307 }
308
309 int leftHeigth(getHeight(r->getLeft()));310 int rightHeigth(getHeight(r->getRight()));
311
312 return (leftHeigth > rightHeigth ? leftHeigth : rightHeigth) + 1;
313 }
314
315 template <class T>
316 int BTree<T>::getHeightRight(BTree<T>::Node*& r) {
317 if(r == nullptr) {
318 return 0;
319 }
320
321 int leftHeigth(getHeight(r->getLeft()));
322 int rightHeigth(getHeight(r->getRight()));
323
324 return (leftHeigth > rightHeigth ? leftHeigth : rightHeigth) + 1;
325 }
326
327 template <class T>
328 int BTree<T>::getHeightLeft(BTree<T>::Node*& r) {
329 if(r == nullptr) {
330 return 0;
331 }
332
333 int leftHeigth(getHeight(r->getLeft()));
334 int rightHeigth(getHeight(r->getRight()));
335
336 return (leftHeigth > rightHeigth ? leftHeigth : rightHeigth) + 1;
337 }
338
339 template <class T>
340 void BTree<T>::parsePreOrder(BTree<T>::Node*& r) {
341 if(r == nullptr) {
342 return;
343 }
344
345 std::cout << r->getData() << ", ";
346 parsePreOrder(r->getLeft());
347 parsePreOrder(r->getRight());
348 }
349
350 template <class T>
351 void BTree<T>::parseInOrder(BTree<T>::Node*& r) {
352 if(r == nullptr) {
353 return;
354 }
355
356 parseInOrder(r->getLeft());
357 std::cout << r->getData() << ", ";
358 parseInOrder(r->getRight());
359 }
360
361 template <class T>
362 void BTree<T>::parsePostOrder(BTree<T>::Node*& r) {
363 if(r == nullptr) {
364 return;
365 }
366
367 parsePostOrder(r->getLeft());
368 parsePostOrder(r->getRight());
369 std::cout << r->getData() << ", ";
370 }
371
372
373 template <class T>
374 void BTree<T>::swapData(T& a, T& b) {
375 T aux;
376
377 aux = a;
378 a = b;
379 b= aux;
380 }
381
382 ///public
383
384 template <class T>
385 BTree<T>::BTree() : root(nullptr) { }
386
387 template <class T>
388 BTree<T>::BTree(const BTree<T>& t) : root(nullptr) {
389 copyAll(t.root, root);
390 }
391
392 template <class T>
393 BTree<T>::~BTree() {
394 deleteAll();
395 }
396
397 template <class T>
398 bool BTree<T>::isEmpty() const {
399 return root == nullptr;
400 }
401
402 template <class T>
403 void BTree<T>::insertData(const T& e) {
404 insertData(root, e);
405 }
406
407 template <class T>
408 typename BTree<T>::Node*& BTree<T>::findData(const T& e) {
409 return findData(root, e);
410 }
411
412 template <class T>
413 T& BTree<T>::retrieve(BTree<T>::Node*& r) {
414 if(r == nullptr) {
415 throw Exception(" Posicion invalida, retireve.");
416 }
417
418 return r->getData();
419 }
420
421 template <class T>
422 void BTree<T>::parsePreOrder() {
423 parsePreOrder(root);
424 }
425
426 template <class T>
427 void BTree<T>::parseInOrder() {
428 parseInOrder(root);
429 }
430
431 template <class T>
432 void BTree<T>::parsePostOrder() {
433 parsePostOrder(root);
434 }
435
436 template <class T>
437 void BTree<T>::deleteData(BTree<T>::Node*& r) {
438 if(r == nullptr) {
439 throw Exception(" Posicion invalida, deleteData.");
440 }
441
442 if(isLeaf(r)) {
443 delete r;
444
445 r = nullptr;
446
447 return;
448 }
449
450 Node*& substitute(r->getLeft() != nullptr ? getTheHighest(r->getLeft()) : getTheLowest(r->getRight()));
451
452 swapData(r->getData(), substitute->getData());
453
454 deleteData(substitute);
455 }
456
457 template <class T>
458 bool BTree<T>::isLeaf(BTree<T>::Node*& r) const {
459 return r != nullptr and r->getLeft() == r->getRight();
460 }
461
462 template <class T>
463 int BTree<T>::getHeight() {
464 return getHeight(root);
465 }
466
467 template <class T>
468 int BTree<T>::getHeightRight() {
469 return getHeight(root->getRight());
470 }
471
472 template <class T>
473 int BTree<T>::getHeightLeft() {
474 return getHeight(root->getLeft());
475 }
476
477 template <class T>
478 void BTree<T>::deleteAll() {
479 deleteAll(root);
480 }
481
482 template <class T>
483 BTree<T>& BTree<T>::operator=(const BTree<T>& t) {
484 deleteAll();
485
486 copyAll(t);
487
488 return *this;
489 }
490
491 template <class T>
492 int BTree<T>::getBalanceFactor(BTree<T>::Node*& r) {
493 return getHeight(r->getRight()) - getHeight(r->getLeft());
494 }
495
496 template <class T>
497 void BTree<T>::doSimpleLeftRot(BTree<T>::Node*& r) {
498 Node* aux1(r->getRight());
499 Node* aux2(aux1->getLeft());
500
501 r->setRight(aux2);
502 aux1->setLeft(r);
503 r = aux1;
504 }
505
506 template <class T>
507 void BTree<T>::doSimpleRightRot(BTree<T>::Node*& r) {
508 Node* aux1(r->getLeft());
509 Node* aux2(aux1->getRight());
510
511 r->setLeft(aux2);
512 aux1->setRight(r);
513 r = aux1;
514 }
515
516 template <class T>
517 void BTree<T>::doDoubleLeftRot(BTree<T>::Node*& r) {
518 doSimpleRightRot(r->getRight());
519 doSimpleLeftRot(r);
520 }
521
522 template <class T>
523 void BTree<T>::doDoubleRightRot(BTree<T>::Node*& r) {
524 doSimpleLeftRot(r->getLeft());
525 doSimpleRightRot(r);
526 }
527
528 template <class T>
529 void BTree<T>::doBalancing(BTree<T>::Node*& r) {
530 switch(getBalanceFactor(r)) {
531 case 2: ///Desbalanceo a la derecha, aplicar rotacion a la izquierda.
532 if(getBalanceFactor(r->getRight()) == 1) { ///Coincide signo, simple
533 doSimpleLeftRot(r);
534 }
535 else { ///No coincide signo, doble
536 doDoubleLeftRot(r);
537 }
538
539 break;
540
541 case -2: ///Desbalanceo a la izquierda, aplicar rotacion a la derecha.
542 if(getBalanceFactor(r->getLeft()) == -1) { ///Coincide signo, simple
543 doSimpleRightRot(r);
544 }
545 else { ///No coincide signo, double
546 doDoubleRightRot(r);
547 }
548
549 break;
550 }
551 }
552
553 #endif // BTREE_H_INCLUDED
Capturas de pantalla: