rboles parcialmente ordenados
Un rbol parcialmente ordenado (montculo) es un rbol completamente lleno, con la posible excepcin del nivel ms bajo, el cul se llena de izquierda a derecha (rbol completo).
3 9 15 17 19 25 21 28 30 10 35 40 6 16 37
rboles parcialmente ordenados
La propiedad que permite efectuar rpidamente las operaciones es la propiedad de orden del APO que consiste en que cualquier nodo debe ser menor que todos sus descendientes, o sea, en un APO, para todo nodo X, la clave en el padre de X es menor o igual que la clave en X (con excepcin de la raz, que no tiene padre). Operaciones bsicas: insercin y eliminacin. Principal aplicacin: representacin de colas con prioridad.
Un rbol binario completo de altura h tiene entre 2h y 2h+1 -1 nodos. Esto implica que la altura de un rbol binario completo es log2 n, por lo que las inserciones y eliminaciones son O(log2 n).
rboles parcialmente ordenados
3
Representacin de APO
3 9 6
6 15 21 10 16
15
21
10
16 17 19 25
17
19
25
Vector de posiciones relativas Altura = 3 Nmero de nodos (n) 23 n 2 4 1
Nodos ultimo = 9
0 3 1 9 2 6 3 15 4 21 5 10 6 16 7 17 8 19 9 25 10 11 12 13 14
maxNodos = 15
/* APO.h
*/ APO CrearAPO (int maxNodos); void InsertarAPO (tElemento e, APO A); void SuprimirMinAPO (APO A); tElemento RecuperarMinAPO (APO A); void DestruirAPO (APO A); int APOVacio (APO A); #endif
typedef char tElemento; /* Por ejemplo */ #ifndef _APO_ #define _APO_ typedef int nodo; /* ndice de la matriz entre 0 y maxNodos-1 */ typedef struct tArbol { tElemento *nodos; int maxNodos; int ultimo; } tipoArbol; typedef tipoArbol *APO;
/* APO.c #include <stdlib.h> #include "error.h" #include "APO.h"
*/
Insercin en un APO
Insertar 5 3 9 6
APO CrearAPO (int maxNodos) { APO A; A = (APO) malloc(sizeof(tipoArbol)); if (A == NULL) ERROR("CrearAPO(): No hay memoria"); A->nodos=(tElemento*) calloc(maxNodos, sizeof(tElemento)); if (A->nodos == NULL) ERROR("CrearAPO(): No hay memoria"); A->maxNodos = maxNodos; A->ultimo = -1; return A; }
15
21
10
16
17
19
25
Insercin en un APO
Insertar 5 9 3 6 Insertar 5
Insercin en un APO
3 6
15
10
16
15
10
16
17
19
25
21
17
19
25
21
Insercin en un APO
Insertar 5 5 3 6
void InsertarAPO (tElemento e, APO A) { nodo p; if (A->maxNodos - 1 == A->ultimo) ERROR("InsertarAPO(): APO lleno"); A->ultimo++; p = A->ultimo; while ((p > 0) && (A->nodos[(p-1)/2]>e)) { A->nodos[p] = A->nodos[(p-1)/2]; p = (p-1)/2; } A->nodos[p] = e; }
15
10
16
17
19
25
21
Suprimir en un APO
Caso 1 3 Caso 3 UltimoElto = 9
Suprimir en un APO
3
9 9
15 Caso 2 3 9 6 6 17 UltimoElto = 6 UltimoElto = 21 19 25
10
16
21
Suprimir en un APO
Caso 3 Caso 3
Suprimir en un APO
5
15
10
16
15
10
16
17
19
25
17
19
25
UltimoElto = 21
UltimoElto = 21
Suprimir en un APO
Caso 3 5 9 6 Caso 3
Suprimir en un APO
5 9 6
15
10
16
15
21
10
16
17
19
25
17
19
25
UltimoElto = 21
UltimoElto = 21
void SuprimirMinAPO (APO A) { nodo p, pMin; int fin; tElemento ultimoElto; if (A->ultimo == -1) ERROR("SuprimirAPO(): APO vaco"); ultimoElto = A->nodos[A->ultimo]; A->ultimo--; if (A->ultimo >= 0) { /* primer if*/ p = 0; if (A->ultimo > 0) { /*segundo if */ fin = 0;
}
while (p <= (A->ultimo-1)/2 && !fin) { if (2*p+1 == A->ultimo) pMin = 2*p+1; else if (A->nodos[2*p+1]<A->nodos[2*p+2]) pMin = 2*p+1; else pMin = 2*p+2; if (A->nodos[pMin] < ultimoElto) { A->nodos[p] = A->nodos[pMin]; p = pMin; } else fin = 1; } /* while */ } /* segundo if */ A->nodos[p] = ultimoElto; /* primer if */
tElemento RecuperarMinAPO (APO A) { return A->nodos[0]; } void DestruirAPO (APO A) { free(A->nodos); free(A); } int APOVacio (APO A) { return (A->ultimo == -1); }
