-
Notifications
You must be signed in to change notification settings - Fork 1
/
ArbolBinarioCod.h
477 lines (402 loc) · 13.7 KB
/
ArbolBinarioCod.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
#ifndef CODINGPROYECT_ARBOLBINARIO_H
#define CODINGPROYECT_ARBOLBINARIO_H
#include "NodoArbol.h"
#include <iostream>
using namespace std;
class ArbolBinarioCod {
protected:
enum {IZQUIERDO, DERECHO};
NodoArbol<string, string> *raiz;
NodoArbol<string, string> *actual;
int contador;
int altura;
public:
ArbolBinarioCod();
~ArbolBinarioCod();
void Insertar(string c, string d);
string BuscarK(string c);
bool Vacio(NodoArbol<string, string> *r) { return r==NULL; }
void Borrar(string c);
bool EsHoja(NodoArbol<string, string> *r) { return !r->der && !r->izq; }
void InOrden(void (*func)(string&, int) , NodoArbol<string, string> *nodo=NULL, bool r=true);
void PreOrden(void (*func)(string&, int) , NodoArbol<string, string> *nodo=NULL, bool r=true);
void PostOrden(void (*func)(string&, int) , NodoArbol<string, string> *nodo=NULL, bool r=true);
private:
// Funciones de equilibrado:
void Equilibrar(NodoArbol<string, string> *nodo, int, bool);
void RSI(NodoArbol<string, string>* nodo);
void RSD(NodoArbol<string, string>* nodo);
void RDI(NodoArbol<string, string>* nodo);
void RDD(NodoArbol<string, string>* nodo);
// Funciones auxiliares
void Podar(NodoArbol<string, string>* &);
void auxContador(NodoArbol<string, string>*);
void auxAltura(NodoArbol<string, string>*, int);
};
/**
* Constructor del Arbol
* @tparam K Clave por la cual va a ordenar el árbol
* @tparam T Valor guardado por el árbol
*/
ArbolBinarioCod::ArbolBinarioCod() {
raiz = nullptr;
actual = nullptr;
}
/**Llama la función podar para eliminar el árbol
* Destructor del Arbol
*/
ArbolBinarioCod::~ArbolBinarioCod() {
Podar(raiz);
}
/**Borra todos los nodos a partir de un nodo, incluido. Usa
recorrido postorden
* @tparam nodo a podar
*/
void ArbolBinarioCod::Podar(NodoArbol<string, string>* &nodo)
{
if(nodo) {
Podar(nodo->izq); // Podar izquierdo
Podar(nodo->der); // Podar derecho
delete nodo;
nodo = NULL;
}
}
/**
* Agrega un dato al árbol
* @param clave Clave para agregar el dato
* @param dato c Dato codificado a agregar
* @param dato d Dato decodificado a agregar
*/
void ArbolBinarioCod::Insertar( string c, string d) {
NodoArbol<string, string> *padre = NULL;
actual = raiz;
// Buscar el dato en el árbol, manteniendo un puntero al nodo padre
while(!Vacio(actual) && d != actual->desc) {
padre = actual;
if(d > actual->desc) actual = actual->der;
else if(d < actual->desc) actual = actual->izq;
}
// Si se ha encontrado el elemento, regresar sin insertar
if(!Vacio(actual)) return;
// Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será
// el nodo raiz
if(Vacio(padre)) raiz = new NodoArbol<string, string>(c, d);
// Si el dato es menor que el que contiene el nodo padre, lo insertamos
// en la rama izquierda
else if(d < padre->desc) {
padre->izq = new NodoArbol<string, string>(c, d ,padre);
Equilibrar(padre, IZQUIERDO, true);
}
// Si el dato es mayor que el que contiene el nodo padre, lo insertamos
// en la rama derecha
else if(d > padre->desc) {
padre->der = new NodoArbol<string, string>(c, d,padre);
Equilibrar(padre, DERECHO, true);
}
}
/**
* Equilibra árbol AVL partiendo de un nuevo nodo
* @param *nodo Nodo a equilibrar
* @param nuevo Nos indica que se agrega un nodo nuevo
* @param rama El valor de equilibrio de la rama (1, 0 o -1)
*/
void ArbolBinarioCod::Equilibrar(NodoArbol<string, string> *nodo, int rama, bool nuevo)
{
bool salir = false;
// Recorrer camino inverso actualizando valores de FE:
while(nodo && !salir) {
if(nuevo)
if(rama == IZQUIERDO) nodo->fe--; // Depende de si añadimos ...
else nodo->fe++;
else
if(rama == IZQUIERDO) nodo->fe++; // ... o borramos
else nodo->fe--;
if(nodo->fe == 0) salir = true; // La altura de las rama que
// empieza en nodo no ha variado,
// salir de Equilibrar
else if(nodo->fe == -2) { // Rotar a derechas y salir:
if(nodo->izq->fe == 1) RDD(nodo); // Rotación doble
else RSD(nodo); // Rotación simple
salir = true;
}
else if(nodo->fe == 2) { // Rotar a izquierdas y salir:
if(nodo->der->fe == -1) RDI(nodo); // Rotación doble
else RSI(nodo); // Rotación simple
salir = true;
}
if(nodo->padre)
if(nodo->padre->der == nodo) rama = DERECHO; else rama = IZQUIERDO;
nodo = nodo->padre; // Calcular FE, siguiente nodo del camino.
}
}
/**
* Rotación doble a derecha
* @param nodo Nodo a rotar
*/
void ArbolBinarioCod::RDD(NodoArbol<string, string>* nodo) {
//cout << "RDD" << endl;
NodoArbol<string, string> *Padre = nodo->padre;
NodoArbol<string, string>*P = nodo;
NodoArbol<string, string> *Q = P->izq;
NodoArbol<string, string> *R = Q->der;
NodoArbol<string, string> *B = R->izq;
NodoArbol<string, string> *C = R->der;
if(Padre)
if(Padre->der == nodo) Padre->der = R;
else Padre->izq = R;
else raiz = R;
// Reconstruir árbol:
Q->der = B;
P->izq = C;
R->izq = Q;
R->der = P;
// Reasignar padres:
R->padre = Padre;
P->padre = Q->padre = R;
if(B) B->padre = Q;
if(C) C->padre = P;
// Ajustar valores de FE:
switch(R->fe) {
case -1: Q->fe = 0; P->fe = 1; break;
case 0: Q->fe = 0; P->fe = 0; break;
case 1: Q->fe = -1; P->fe = 0; break;
}
R->fe = 0;
}
/**
* Rotación doble a izquierda
* @param nodo Nodo a rotar
*/
void ArbolBinarioCod::RDI(NodoArbol<string, string>* nodo) {
//cout << "RDI" << endl;
NodoArbol<string, string> *Padre = nodo->padre;
NodoArbol<string, string> *P = nodo;
NodoArbol<string, string> *Q = P->der;
NodoArbol<string, string> *R = Q->izq;
NodoArbol<string, string> *B = R->izq;
NodoArbol<string, string> *C = R->der;
if(Padre)
if(Padre->der == nodo) Padre->der = R;
else Padre->izq = R;
else raiz = R;
// Reconstruir árbol:
P->der = B;
Q->izq = C;
R->izq = P;
R->der = Q;
// Reasignar padres:
R->padre = Padre;
P->padre = Q->padre = R;
if(B) B->padre = P;
if(C) C->padre = Q;
// Ajustar valores de FE:
switch(R->fe) {
case -1: P->fe = 0; Q->fe = 1; break;
case 0: P->fe = 0; Q->fe = 0; break;
case 1: P->fe = -1; Q->fe = 0; break;
}
R->fe = 0;
}
/**
* Rotación simple a derecha
* @param nodo Nodo a rotar
*/
void ArbolBinarioCod::RSD(NodoArbol<string, string>* nodo)
{
//cout << "RSD" << endl;
NodoArbol<string, string> *Padre = nodo->padre;
NodoArbol<string, string> *P = nodo;
NodoArbol<string, string> *Q = P->izq;
NodoArbol<string, string> *B = Q->der;
if(Padre)
if(Padre->der == P) Padre->der = Q;
else Padre->izq = Q;
else raiz = Q;
// Reconstruir árbol:
P->izq = B;
Q->der = P;
// Reasignar padres:
P->padre = Q;
if(B) B->padre = P;
Q->padre = Padre;
// Ajustar valores de FE:
P->fe = 0;
Q->fe = 0;
}
/**
* Rotación simple a izquierda
* @param nodo Nodo a rotar
*/
void ArbolBinarioCod::RSI(NodoArbol<string, string>* nodo)
{
//cout << "RSI" << endl;
NodoArbol<string, string> *Padre = nodo->padre;
NodoArbol<string, string> *P = nodo;
NodoArbol<string, string> *Q = P->der;
NodoArbol<string, string> *B = Q->izq;
if(Padre)
if(Padre->der == P) Padre->der = Q;
else Padre->izq = Q;
else raiz = Q;
// Reconstruir árbol:
P->der = B;
Q->izq = P;
// Reasignar padres:
P->padre = Q;
if(B) B->padre = P;
Q->padre = Padre;
// Ajustar valores de FE:
P->fe = 0;
Q->fe = 0;
}
/**
* Elimina un dato del árbol
* @param d Dato a borrar
*/
void ArbolBinarioCod::Borrar( string d)
{
NodoArbol<string, string> *padre = NULL;
NodoArbol<string, string> *nodo;
string aux;
actual = raiz;
// Mientras sea posible que el valor esté en el árbol
while(!Vacio(actual)) {
if(d == actual->desc) { // Si el valor está en el nodo actual
if(EsHoja(actual)) { // Y si además es un nodo hoja: lo borramos
if(padre) // Si tiene padre (no es el nodo raiz)
// Anulamos el puntero que le hace referencia
if(padre->der == actual) padre->der = NULL;
else if(padre->izq == actual) padre->izq = NULL;
delete actual; // Borrar el nodo
actual = NULL;
// El nodo padre del actual puede ser ahora un nodo hoja, por lo tanto su
// FE es cero, pero debemos seguir el camino a partir de su padre, si existe.
if((padre->der == actual && padre->fe == 1) ||
(padre->izq == actual && padre->fe == -1)) {
padre->fe = 0;
actual = padre;
padre = actual->padre;
}
if(padre)
if(padre->der == actual) Equilibrar(padre, DERECHO, false);
else Equilibrar(padre, IZQUIERDO, false);
return;
}
else { // Si el valor está en el nodo actual, pero no es hoja
// Buscar nodo
padre = actual;
// Buscar nodo más izquierdo de rama derecha
if(actual->der) {
nodo = actual->der;
while(nodo->izq) {
padre = nodo;
nodo = nodo->izq;
}
}
// O buscar nodo más derecho de rama izquierda
else {
nodo = actual->izq;
while(nodo->der) {
padre = nodo;
nodo = nodo->der;
}
}
// Intercambiar valores de no a borrar u nodo encontrado
// y continuar, cerrando el bucle. El nodo encontrado no tiene
// por qué ser un nodo hoja, cerrando el bucle nos aseguramos
// de que sólo se eliminan nodos hoja.
aux = actual->cod;
actual->cod = nodo->cod;
nodo->cod = aux;
actual = nodo;
}
}
else { // Todavía no hemos encontrado el valor, seguir buscándolo
padre = actual;
if(d > actual->desc) actual = actual->der;
else if(d < actual->desc) actual = actual->izq;
}
}
}
/**
* Recorrido de árbol en inorden, aplicamos la función func, que tiene el prototipo:
* template<class DATO> void func(DATO&);
* @param nodo Nodo a recorrer en orden
* @param r Indica que hay raíz
*/
void ArbolBinarioCod::InOrden(void (*func)(string&, int) , NodoArbol<string, string> *nodo, bool r)
{
if(r) nodo = raiz;
if(nodo->izq) InOrden(func, nodo->izq, false);
func(nodo->cod, nodo->fe);
if(nodo->der) InOrden(func, nodo->der, false);
}
/**
* Recorrido de árbol en preorden, aplicamos la función func, que tiene
* el prototipo: template<class DATO> void func(DATO&);
* @param nodo Nodo a recorrer en preorden
*/
void ArbolBinarioCod::PreOrden(void (*func)(string&, int), NodoArbol<string, string> *nodo, bool r)
{
if(r) nodo = raiz;
func(nodo->cod, nodo->fe);
if(nodo->izq) PreOrden(func, nodo->izq, false);
if(nodo->der) PreOrden(func, nodo->der, false);
}
/**
* Recorrido de árbol en postorden, aplicamos la función func, que tiene
* el prototipo:template<class DATO> void func(DATO&);
* @param clave Clave para identificar el nodo a borrar
*/
void ArbolBinarioCod::PostOrden(void (*func)(string&, int), NodoArbol<string, string> *nodo, bool r)
{
if(r) nodo = raiz;
if(nodo->izq) PostOrden(func, nodo->izq, false);
if(nodo->der) PostOrden(func, nodo->der, false);
func(nodo->cod, nodo->fe);
}
/**
* Busca un dato en el árbol. Si no esta el dato en el árbol
* tira una excepción
* @param d Valor a buscar
* @return el valor buscado
*/
string ArbolBinarioCod::BuscarK(string d) {
actual = raiz;
// Todavía puede aparecer, ya que quedan nodos por mirar
while(!Vacio(actual)) {
if(d == actual->desc) return actual->cod; // dato encontrado
else if(d > actual->desc) actual = actual->der; // Seguir
else if(d < actual->desc) actual = actual->izq;
}
throw 1; // No está en árbol
}
/**
* Función auxiliar para contar nodos. Función recursiva de recorrido en
* preorden, el proceso es aumentar el contador
* @param nodo Nodo usado para contar los elementos del árbol
*/
void ArbolBinarioCod::auxContador(NodoArbol<string, string> *nodo)
{
contador++; // Otro nodo
// Continuar recorrido
if(nodo->izq) auxContador(nodo->izq);
if(nodo->der) auxContador(nodo->der);
}
/**
* Función auxiliar para calcular altura. Función recursiva de recorrido en
* postorden, el proceso es actualizar la altura sólo en nodos hojas de mayor
* altura de la máxima actual
* @param nodo Nodo utilizado para realizar la función
* @param a Altura del árbol
*/
void ArbolBinarioCod::auxAltura(NodoArbol<string, string> *nodo, int a)
{
// Recorrido postorden
if(nodo->izq) auxAltura(nodo->izq, a+1);
if(nodo->der) auxAltura(nodo->der, a+1);
// Proceso, si es un nodo hoja, y su altura es mayor que la actual del
// árbol, actualizamos la altura actual del árbol
if(EsHoja(nodo) && a > altura) altura = a;
}
#endif //CODINGPROYECT_ARBOLBINARIO_H