Arboles Binarios Parcialmente Ordenados.




1. INTRODUCCIÓN.

Un árbol A se dice parcialmente ordenado (APO) si cumple la condición de que la etiqueta de cada nodo es menor (de igual forma mayor) o igual que las etiquetas de los hijos (se supone que el tipo_elemento base admite un orden) manteniéndose además tan balanceado como sea posible, en el caso óptimo equilibrado.

Las operaciones básicas en este tipo de árboles son la de inserción de un elemento y la de borrado del elemento de menor etiqueta (la raiz) ,con la consiguiente problemática que se plantea al tener que dejar el árbol tras cualquier operación tanto equilibrado como cumpliendo la condición de orden parcial. Un ejemplo de este tipo de árboles muestra en la siguiente figura:






2. BORRADO EN LOS APO.

Para ejecutar el borrado (y eventual almacenamiento del valor) de la raíz,no se puede quitar el nodo sin más ya que se desconectaria la estructura. Por otro lado si se quiere mantener la propiedad de orden parcial y el mayor balanceo posible con las hojas en el nivel más bajo alojadas de izquierda a derecha lo que podría hacerse es poner provisionalmente la hoja más a la derecha del nivel más bajo como raíz provisional. Empujaremos entonces esta raíz hacia abajo intercambiándola con el hijo de etiqueta menor hasta que no podamos hacerlo más (porque sea ya una hoja o porque la etiqueta sea ya menor que la de cualquiera de sus hijos).

El anterior proceso aplicado a un árbol con n nodos toma un tiempo O(log2 n) puesto que en el árbol ningún camino tiene más de 1+log2 n nodos y el proceso de empujar hacia abajo intercambiando con los hijos toma un tiempo constante por nodo. En la siguiente figura podemos observar este proceso sobre un ejemplo de borrado en un APO en el cual se elimina el nodo a para seguidamente subir a la raíz el nodo g que es empujado hacia abajo.









3. INSERCIÓN EN LOS APO.

Para implementar la inserción habría que hacer unas consideraciones similares a las anteriores. El nuevo elemento que se inserta, lo podriamos situar provisionalmente en el nivel más bajo tan a la izquierda como sea posible (se comienza en un nuevo nivel si el último nivel está completo). A continuación se intercambia con su padre repitiéndose este proceso hasta que se cumpla la condición de orden parcial (bien porque ya esté en la raíz o porque tenga ya una etiqueta mayor que la de su padre).

Al igual que en el borrado puede verse fácilmente que este proceso no lleva más de O(log2 n) pasos. En la siguiente figura podemos ver un ejemplo de inserción en un APO.









4. IMPLEMENTACIÓN MATRICIAL DE ARBOLES APO.

El hecho de que los árboles que hemos estado considerando sean binarios, tan balanceados como sea posible y tengan las hojas en el nivel inferior empujadas hacia la izquierda hace que podamos usar una representación muy usual para estos árboles llamada MONTON que, básicamente es un vector en el que guardamos los nodos del árbol por niveles. Si existen n nodos, se usan las n primeras posiciones de un vector M (M[0] aloja la raíz). El hijo izquierdo del nodo en M[k], si existe, está en M[2k+1], y el hijo derecho, si existe, está en M[2k+2] ,en consecuencia el padre de M[k] sea M[(k-1)/2], para i>0.




Podemos declarar un APO de elementos de algún tipo, digamos tipoelemento, que consistira en un vector de tipoelemento y un entero 'último' indicando el último elemento actual (en uso) del vector. Asi podriamos declarar:

typedef int tElemento;

typedef struct nodoAPO {
	int ultimo;
	int maximo;
	tElemento *apo;
} *APO;

Y la implementación de las operaciones sería como sigue:

  
APO CrearAPO (int max)
    
    

{
	APO A;

	if (max < 1) {
		error("El árbol debe tener al menos un nodo.");
	}
	
	A = (APO)malloc(sizeof(struct nodoAPO));
	if (A == NULL) 
		error("No hay memoria suficiente.");	
		
	A->apo = (tElemento*)malloc(max*sizeof(tElemento));
	if (A->apo == NULL) 
		error("No hay memoria suficiente.");	
	
	A->ultimo = -1;
	A->maximo = max;

	return A;
}

void DestruirAPO (APO A)
    
    

{
	free(A->apo);
	free(A);
}

void InsertaAPO (tElemento el, APO A)
    
    

{
	int pos;
	tElemento aux;
	
	if (A->ultimo == A->maximo-1) {
		error("No caben mas elementos.");	
	}
	
	A->ultimo++;
	pos=A->ultimo;
	A->apo[pos]=el;
	/* Bucle para subir el elemento hasta su posición. */
	while ((pos>0) && (A->apo[pos] < A->apo[(pos-1)/2])) {
		aux = A->apo[pos];
		A->apo[pos] = A->apo[(pos-1)/2];
		A->apo[(pos-1)/2] = aux;
		pos = (pos-1)/2;
	}
}

tElemento BorrarMinimo (APO A)
    
    

{
	int pos;
	int pos_min,acabar;
	tElemento minimo,aux;

	if (A->ultimo == -1) {
		error("No hay elementos.");	
	}
	
	minimo = A->apo[0];
	A->apo[0] =  A->apo[A->ultimo];
	A->ultimo--;
	if (A->ultimo <= 0) return minimo;
	pos = 0;
	acabar = 0;
	while (pos <= (A->ultimo-1)/2 && !acabar) {
		if (2*pos+1 == A->ultimo)
			pos_min = 2*pos+1;
		else if (A->apo[2*pos+1] < A->apo[2*pos+2])
				pos_min = 2*pos+1;
			 else pos_min = 2*pos+2;
		if (A->apo[pos] > A->apo[pos_min]) {
			aux = A->apo[pos];
			A->apo[pos] = A->apo[pos_min];
			A->apo[pos_min] = aux;
			pos = pos_min;
		}
		else acabar=1; 					
	}

	return minimo;
}




Tutor de Estructuras de Datos Interactivo
Exposito Lopez Daniel, Abraham García Soto, Martin Gomez Antonio Jose
Director de proyecto: Joaquín Fernández Valdivia
5º Licenciatura Informatica
ETSII 99/00 (Universidad de Granada).