14. ARBOLES 14.1 FUNDAMENTOS Y TERMINOLOGIA BASICA 79 14.2. ARBOLES BINARIOS 81 14.3. FUNDAMENTOS 82 14.4. OPERACIONES CON ARBOLES BINARIOS: RECORRIDO DE ARBOLES BINARIOS 83 14.5. OTRAS OPERACIONES CON ARBOLES BINARIOS 85 Eliminacion de nodos en un arbol binario 92 14.6. REPRESENTACION DE LOS ARBOLES BINARIOS 96 Representacion mediante arrays 96 Representacion mediante cursores 96 Representacion mediante punteros 97 14.7. ARBOLES BINARIOS ENLAZADOS ("HILVANADOS") 101 14.8. REPRESENTACION DE ARBOLES GENERALES COMO ARBOLES BINARIOS 104 14.9. ARBOLES BINARIOS DE BUSQUEDA 105 Operaciones en arboles binarios de busqueda 106 Busqueda 106 Insercion 109 Borrado 111 14.10. HEAPS (MONTICULOS) 113 Representacion de monticulos 114 Operaciones basicas sobre monticulos 115 Insercion 116 Borrar (una posicion 'pos' cualquiera) 117 Aplicacion de los monticulos 117 14.11. ORDENACION CON ARBOLES 119 14.1 Fundamentos y terminologia basica Hasta ahora hemos visto estructuras de datos lineales, es decir, los datos estaban estructurados en forma de secuencia. Sin embargo, las relaciones entre los objetos no siempre son tan simples como para ser representadas mediante secuencias (incluso, en ocasiones, es conveniente que no sea asi), sino que la complejidad de las relaciones entre los elementos puede requerir otro tipo de estructura. En esas situaciones se pasaria a tener estructuras de datos no lineales. Este es el caso de la estructura de datos conocida como arbol. Los arboles establecen una estructura jerarquica entre los objetos. Los arboles genealogicos y los organigramas son ejemplos comunes de arboles. Un arbol es una coleccion de elementos llamados nodos, uno de los cuales se distingue como raiz, junto con una relacion que impone una estructura jerarquica entre los nodos. Formalmente, un arbol se puede definir de manera recursiva como sigue: Definicion: Una estructura de arbol con tipo base Valor es: (i) Bien la estructura vacia. (ii) Un conjunto finito de uno o mas nodos, tal que existe un nodo especial, llamado nodo raiz, y donde los restantes nodos estan separados en n(0 conjuntos disjuntos, cada uno de los cuales es a su vez un arbol (llamados subarboles del nodo raiz). La definicion implica que cada nodo del arbol es raiz de algun subarbol contenido en el arbol principal. Ejemplos de estructuras arborescentes: Figura 1: Ejemplo de arbol. El indice de un libro tambien se puede representar en forma de arbol, en esta representacion se reflejan con claridad las relaciones de dependencia entre cada una de las partes del libro: Figura 2: Estructura arborescente representando la estructura de un libro. Antes de continuar avanzando en las caracteristicas y propiedades de los arboles, veamos algunos terminos importantes asociados con el concepto de arbol: - Grado de un nodo: Es el numero de subarboles que tienen como raiz ese nodo (el numero de subarboles que "cuelgan" del nodo). - Nodo terminal: Nodo con grado 0, no tiene subarboles. - Grado de un arbol: Grado maximo de los nodos de un arbol. - Hijos de un nodo: Nodos que dependen directamente de ese nodo, es decir, las raices de sus subarboles. - Padre de un nodo: Antecesor directo de un nodo, nodo del que depende directamente. - Nodos hermanos: Nodos hijos del mismo nodo padre. - Camino: Sucesion de nodos del arbol n1, n2, ..., nk, tal que ni es el padre de ni+1. - Antecesores de un nodo: Todos los nodos en el camino desde la raiz del arbol hasta ese nodo. - Nivel de un nodo: Longitud del camino desde la raiz hasta el nodo. El nodo raiz tiene nivel 1. - Altura (profundidad) de un arbol: Nivel maximo de un nodo en un arbol. - Longitud de camino de un arbol: Suma de las longitudes de los caminos a todos sus componentes. - Bosque: Conjunto de n>0 arboles disjuntos. La representacion de un arbol general dependera de su grado, es decir, del numero de relaciones maximo que puede tener un nodo del arbol. Resulta mas simple la representacion y manipulacion de una estructura arbol cuando el grado de este es fijo y no variable. Por esa razon, para introducir los aspectos mas concretos de la manipulacion de arboles, vamos a tratar con un tipo particular de arboles de grado fijo, los llamados arboles binarios. 14.2. Arboles binarios Los arboles binarios constituyen un tipo particular de arboles de gran aplicacion. Estos arboles se caracterizan porque no existen nodos con grado mayor que dos, es decir, un nodo tendra como maximo dos subarboles. Definicion: Un arbol binario es un conjunto finito de nodos que puede estar vacio o consistir en un nodo raiz y dos arboles binarios disjuntos, llamados subarbol izquierdo y subarbol derecho. En general, en un arbol no se distingue entre los subarboles de un nodo, mientras que en un arbol binario se suele utilizar la nomenclatura subarbol izquierdo y derecho para identificar los dos posibles subarboles de un nodo determinado. De forma que, por ejemplo, los dos siguientes arboles, a pesar de contener la misma informacion son distintos por la disposicion de los subarboles: Figura 3: Ejemplos de arboles. Antes de pasar a la representacion de los arboles binarios, vamos a hacer algunas observaciones relevantes acerca del numero y caracteristicas de los nodos en este tipo de arboles. Lema 1: El numero maximo de nodos en el nivel i de un arbol binario es 2i-1, i(1, y el numero maximo de nodos en un arbol binario de altura k es 2k-1, k(1. Lema 2: Para cualquier arbol binario no vacio, si n0 es el numero de nodos terminales y n2 es el numero de nodos de grado 2, entonces se cumple que n0=n2+1. 1 Igualmente, para poder entender alguna de las formas de representacion de los arboles binarios, vamos a introducir dos nuevos conceptos, lo que se entiende por arbol binario lleno y por arbol binario completo. Definicion: Se dice que un arbol binario esta lleno si es un arbol binario de profundidad k que tiene 2k-1 nodos. Un arbol binario lleno es aquel que contiene el numero maximo de posibles nodos. Como en estos casos no existen subarboles vacios excepto para los nodos terminales, es posible realizar una representacion secuencial eficiente de este tipo de arboles. Esta representacion suele implicar la numeracion de los nodos. La numeracion se realiza por niveles y de izquierda a derecha. Este proceso de numeracion (etiquetado) de los nodos permite una identificacion elegante de las relaciones de parentesco entre los nodos del arbol y se vera mas adelante (en C/C++ suele empezar la numeracion en '0' y terminar en 'n-1'. En otros lenguajes, como Pascal, la numeracion suele empezar en '1' y terminar en 'n'. Nosotros nos ceñiremos a la numeracion en C/C++.) Definicion: Un arbol binario con n nodos y profundidad k se dice que es completo si y solo si sus nodos se corresponden con los nodos numerados de 0 a n-1 en el arbol binario lleno de profundidad k. Cuando un arbol no es lleno pero es completo, tambien es posible la representacion secuencial eficiente de la estructura de nodos que lo componen. 14.3. Fundamentos Al igual que hemos visto en el resto de temas, empezaremos por introducir el tipo abstracto de datos 'Arbol Binario'. Como en las otras estructuras de datos vistas, empezaremos viendo las operaciones que consideraremos basicas para la manipulacion de los arboles. Y al igual que hicimos en los otros TAD tendremos diferentes tipos de operaciones: * De consulta sobre la informacion del TAD: En este caso, se debera poder consultar tanto la informacion guardada en el nodo raiz como los hijos del nodo raiz (Informacion, HijoIzdo, HijoDcho.) * De consulta sobre la propia estructura: Si la estructura contiene informacion, o por el contrario, esta vacia (ArbolVacio.) El hecho de añadir y eliminar una cierta informacion del arbol, es un problema ciertamente complejo, que depende de diferentes criterios y que es dificil de abordar desde el punto de vista general. El problema de la eliminacion de informacion lo veremos de forma mas concreta mas adelante. La adicion de informacion, la veremos desde un punto de vista concreto en este momento, aunque se puede ver de diferentes maneras (veremos otros puntos de vista mas adelante, en arboles binarios de busqueda y en monticulos.) * Para añadir informacion: En este caso, la manera en que consideraremos que se puede añadir informacion sera creando un nuevo arbol a partir de dos arboles ya existentes y con la informacion que desamos añadir en el nodo raiz, cada subarbol sera un hijo del nuevo arbol (HacerArbol.) Resumiendo, estas operaciones quedarian de la siguiente forma: IniciarArbol ( ) ® ArbolBinario ArbolVacio ( ArbolBinario ) ® Boolean HacerArbol ( ArbolBinario, Valor, ArbolBinario ) ® ArbolBinario HijoIzquierdo ( ArbolBinario ) ® ArbolBinario HijoDerecho ( ArbolBinario ) ® ArbolBinario Informacion ( ArbolBinario ) ® Valor SalPag Y cumplen los siguientes axiomas: ( p, r ( ArbolBinario ( d ( Valor ( ArbolVacio ( IniciarArbol ( ) ) ® TRUE ArbolVacio ( HacerArbol ( p, d, r ) ) ® FALSE HijoIzquierdo ( HacerArbol ( p, d, r ) ) ® p HijoIzquierdo ( IniciarArbol ( ) ) ® ERROR HijoDerecho ( HacerArbol ( p, d, r ) ) ® r HijoDerecho ( IniciarArbol ( ) ) ® ERROR Informacion ( HacerArbol ( p, d, r ) ) ® d Informacion ( IniciarArbol ( ) ) ® ERROR A partir de esta informacion, ya somos capaces de codificar en C++ la interfaz de la clase arbol: class Arbol { public: Arbol (void); /* IniciarArbol -> Constructor */ void HacerArbol (Arbol &, Valor, Arbol &); bool ArbolVacio (void); bool Informacion (Valor &); Arbol &HijoIzdo (void); Arbol &HijoDcho (void); Arbol (const Arbol &); /* Constructor de copia */ ~Arbol (void); /* Destructor */ private: ... }; Vista la parte publica de la clase, ya podemos hacer uso de la misma. 14.4. Operaciones con arboles binarios: Recorrido de arboles binarios Si se desea manipular la informacion contenida en un arbol, lo primero que hay que saber es como se puede recorrer ese arbol, de manera que se acceda a todos los nodos del arbol solamente una vez. El recorrido completo de un arbol produce un orden lineal en la informacion del arbol. Este orden puede ser util en determinadas ocasiones. Cuando se recorre un arbol se desea tratar cada nodo y cada subarbol de la misma manera. Existen entonces seis posibles formas de recorrer un arbol binario: (1) nodo - subarbol izquierdo - subarbol derecho (2) subarbol izquierdo - nodo - subarbol derecho (3) subarbol izquierdo - subarbol derecho - nodo (4) nodo - subarbol derecho - subarbol izquierdo (5) subarbol derecho - nodo - subarbol izquierdo (6) subarbol derecho - subarbol izquierdo - nodo Si se adopta el convenio de que, por razones de simetria, siempre se recorrera antes el subarbol izquierdo que el derecho, entonces tenemos solamente tres tipos de recorrido de un arbol (los tres primeros en la lista anterior). Estos recorridos, atendiendo a la posicion en que se procesa la informacion del nodo, reciben, respectivamente, el nombre de recorrido prefijo, infijo y posfijo. Los tres tipos de recorrido tienen una definicion muy simple si se hace uso de una expresion recursiva de los mismos. SalPag Algoritmo Prefijo Entrada Arbol arb Inicio si ( arb no es Vacio ) entonces Procesar ( Informacion de arb ) Prefijo ( Hijo izquierdo de arb ) Prefijo ( Hijo derecho de arb ) fin_si fin Algoritmo Infijo Entrada Arbol arb Inicio Si ( arb no es Vacio ) entonces Infijo ( Hijo izquierdo de arb ) Procesar ( Informacion de arb ) Infijo ( Hijo derecho de arb ) Fin_si Fin Algoritmo Posfijo Entrada Arbol arb Inicio Si ( arb no es Vacio ) entonces Posfijo ( Hijo izquierdo de arb ) Posfijo ( Hijo derecho de arb ) Procesar ( Informacion de arb ) Fin_si Fin Ejemplo de recorrido de un arbol binario: Recorrido Prefijo: A B C D E F G Recorrido Infijo: C B D E A G F Recorrido Posfijo: C E D B G F A Figura 5 ( En C++, la implementacion de los recorridos es muy simple. Por ejemplo el recorrido Prefijo quedaria como sigue: ( Prefijo (cons Arbol & arb) { Valor inf; if (arb.ArbolVacio () == false) { arb.Informacion (inf); Procesar (inf); Prefijo (arb.HijoIzdo() ); Prefijo (arb.HijoDcho() ); } } ( SalPag El paso del parametro lo hacemos por referencia, pero constante, para no tener que realizar la copia de la informacion y hacer un metodo mas eficiente. 14.5. Otras operaciones con arboles binarios La primera operacion compleja a considerar sobre arboles binarios sera su generacion. En este caso, no vamos a entrar a considerar todos los casos que pueden aparecer al insertar un nuevo nodo en un arbol, la problematica puede ser amplia y el proceso de generacion de un arbol dependera de las reglas impuestas por una aplicacion particular. Vamos a ver, sin embargo, algun ejemplo concreto que permita ilustrar esta operacion. Al manipular la estructura arbol, la situacion mas habitual es que el problema imponga una serie de reglas para la construccion del arbol en funcion de los datos de entrada. Estos datos, en principio, seran desconocidos antes de la ejecucion del programa. El procedimiento de generacion del arbol debera, por tanto, reproducir de la manera mas eficiente posible esas reglas de generacion. Ejemplo 1: Generacion de un arbol a partir de su recorrido prefijo. Supongamos que se desea generar en memoria una estructura de arbol binario con unos datos cuyas relaciones se conocen previamente. Es decir, el usuario va a trasladar al ordenador una estructura de arbol conocida. Para hacer esto, se establece una notacion secuencial que permita la interpretacion simple de las relaciones. Esta notacion es similar a la representacion secuencial que se comento para arboles binarios completos, y que se extendio a cualquier arbol arbitrario. La notacion consiste en una secuencia de caracteres que indica la informacion de cada nodo en el arbol completo asociado, de manera que se indica tambien si algun subarbol esta vacio y se supone que la informacion del subarbol izquierdo va siempre antes que la del subarbol derecho. En realidad se trata de una representacion secuencial del recorrido prefijo del arbol. Se considerara, para simplificar, que la informacion asociada con cada nodo es simplemente un caracter y que los subarboles vacios se representan con un '.'. Entonces la entrada al algoritmo de generacion puede ser simplemente una cadena de caracteres, donde cada uno de ellos se interpreta como un nodo del arbol. Figura 6 Representacion secuencial del arbol: A B C . . D . E . . F G . . . ( En este caso, las reglas de generacion del arbol binario a partir de su representacion secuencial serian: (1) Leer caracter a caracter la secuencia de entrada. (a) Si el caracter que se lee es '.' no hay que crear ningun nodo, el subarbol esta vacio. (b) Si se lee un caracter distinto de '.' entonces se crea un nuevo nodo con la informacion leida y se pasa a generar los subarboles izquierdo y derecho de ese nodo, segun los mismos criterios y en ese mismo orden. Un algoritmo que implemente estas reglas de generacion podria ser: Algoritmo Generar_Arbol Salida ArbolBinario arb Inicio Leer ( caracter ) Si caracter ( '.' entonces Informacion de arb ( caracter Generar_Arbol ( Hijo izquierdo de arb ) Generar_Arbol ( Hijo derecho de arb ) Sino arb es vacio Fin_si Fin SalPag Utilizando exclusivamente las operaciones basicas definidas previamente, el algoritmo de generacion quedaria como sigue: Algoritmo Generar_Arbol Salida ArbolBinario arb Auxiliar ArbolBinario izq, der Inicio Leer ( caracter ) Si(1) caracter ( '.' entonces izq ( Generar_Arbol der ( Generar_Arbol arb ( HacerArbol (izq, caracter, der) Sino(1) arb ( IniciarArbol ( ) Fin_si(1) Fin Se puede observar como la recursividad permite definir de una manera simple y elegante el proceso de generacion. Esta funcion escrita en C++ quedaria como sigue: ( void GenerarArbol (Arbol & arb) { Arbol izq, der; cin >> x if (x != '.') { GenerarArbol (izq); GenerarArbol (der); arb.HacerArbol (izq, x, der); } } ( Resaltar, que en ningun momento se llama a ninguna funcion para iniciar el arbol, ya que por el hecho de declararlo el arbol es creado vacio (se llama al constructor por defecto de la clase.) Ejemplo 2: Arbol binario para la representacion de una expresion algebraica. Generar el arbol binario de representacion de una expresion algebraica. Para ello se realizan las siguientes consideraciones: (1) La entrada del programa debera ser una expresion escrita en notacion infija. (2) En las expresiones solo se tendran en cuenta los cuatro operadores binarios basicos: +, -, *, /. No se consideraran parentesis. (3) Los operandos seran exclusivamente caracteres (1 caracter, 1 operando). La generacion del arbol se facilita considerablemente si se traduce la expresion a notacion posfija y se almacenan los elementos de la expresion en una pila (Pila2), segun el siguiente algoritmo. Algoritmo Infija_Posfija (sin parentesis) Entrada cadena expresion Variables x,y: elemento de cadena pila_aux, pila_expr: Pila final: (cierto,falso) Inicio Iniciar_Pila ( pila1 ) Repetir x ( sig_elemento ( expresion ) Si(1) x es operando entonces Apilar ( x, pila_expr ) Sino(1) {x es operador, entonces se apila pero...} final ( FALSO {...antes de apilar, analizar prioridades de operadores} Mientras(1) ( no Vacia_Pila ( pila_aux ) ) y ( no terminar ) hacer Si(2) ( prioridad ( x ) ( prioridad ( Cima_Pila ( pila_aux ) ) entonces y ( Desapilar ( pila_aux ) Apilar ( pila_expr, y ) Sino(2) terminar ( CIERTO Fin_si(2) Fin_mientras(1) Apilar ( x, pila_aux ) Fin_si(1) Hasta final ( expresion ) {se ha terminado la expresion, vaciar la pila} Mientras(2) no Vacia_Pila ( pila_aux ) hacer y ( Desapilar ( pila_aux ) Apilar ( y, pila_expr ) Fin_mientras(2) Fin Una vez colocada la expresion en notacion postfijo en la pila, la generacion del arbol del arbol de la expresion quedaria: Algoritmo Crear_Arbol Entradas pila_expr: Pila arb: Arbol Salidas arb: Arbol Inicio Si(1) ( no Vacia_Pila ( pila_expr ) ) entonces arb ( crear_espacio arb^.info ( Desapilar ( pila_expr ) Si(2) ( arb^.info es operador ) entonces {* como se lee la expresion al reves, el primer operando que se lee *} {* es en realidad el ultimo, por eso se genera antes el arbol derecho *} Crear_Arbol ( arb^.der ) Crear_Arbol ( arb^.izq ) Sino(2) arb^.der ( NULO arb^.izq ( NULO Fin_si(2) Fin_si(1) Fin Al igual que en el ejemplo anterior, si nos ceñimos a las operaciones basicas el algoritmo quedaria de la siguiente manera: Algoritmo Crear_Arbol Entradas pila_expr: Pila arb: Arbol Salidas arb: ArbolBinario Variables der, izq: ArbolBinario Inicio Si(1) ( no Vacia_Pila ( pila_expr ) ) entonces y ( Desapilar ( pila_expr ) Si(2) ( y es operador ) entonces {* como se lee la expresion al reves, el primer operando que se lee *} {* es en realidad el ultimo, por eso se genera antes el arbol derecho *} Crear_Arbol ( der ) Crear_Arbol ( izq ) Sino(2) der ( IniciarArbol ( ) izq ( IniciarArbol ( ) Fin_si(2) arb ( HacerArbol ( izq, y, der ) Fin_si(1) Fin Ejemplo 3: Copia de un arbol binario en otro. Como un ejemplo mas de manipulacion de un arbol, veamos un algoritmo que nos permita realizar un duplicado de un arbol ya existente (sin utilizar el constructor de copia). Al copiar el arbol se debe copiar toda la informacion contenida en el mismo, con la misma estructura de relaciones que existe en el arbol original. El proceso de copia implica el recorrido sistematico del arbol original, al mismo tiempo que se genera un nuevo arbol con la misma informacion. Algoritmo Copiar Entrada org: ArbolBinario Salida dest: ArbolBinario Variable aux: ArbolBinario Inicio Si ( org = NULO ) entonces dest ( NULO Sino aux ( Crear_Espacio aux^.info ( org^.info aux^.izq ( Copiar(org^.izq) aux^.der ( Copiar(org^.der) dest ( aux Fin_si Fin Este algoritmo quedaria, utilizando las operaciones basicas: Algoritmo Copiar Entrada org: ArbolBinario Salida dest: ArbolBinario Inicio Si ( VacioArbol ( org ) ) entonces dest ( IniciarArbol ( ) Sino dest ( HacerArbol ( Copiar( HijoIzquierdo ( org ) ), Informacion ( org ), Copiar( HijoIzquierdo ( org ) ) ) Fin_si Fin SalPag Esta funcion escrita en C++ quedaria como sigue: ( void CopiarArbol (Arbol & des, Arbol ori) { Arbol izq, der; Valor x; bool b_aux; if (!ori.ArbolVacio () ) { CopiarArbol (izq, ori.HijoIzdo () ); CopiarArbol (der, ori.HijoDcho () ); b_aux = ori.Informacion (x); des.HacerArbol (izq, x, der); } } ( Ejemplo 4: Equivalencia entre arboles binarios. Otro problema que se puede solucionar facilmente utilizando la recursion es el de determinar la equivalencia entre dos arboles binarios. Se dice que dos arboles binarios son equivalentes si presentan la misma topologia (la misma estructura de relaciones entre nodos) y la informacion en los nodos correspondientes es la misma. Algoritmo Equivalente Entradas ArbolBinario arbol1, arbol2 Salida Boolean (CIERTO, FALSO) Variable Boolean equiv: (CIERTO, FALSO) Inicio equiv ( FALSO Si(1) ( (arb1 esta vacio) y (arb2 esta vacio) ) entonces equiv ( CIERTO Sino(1) Si(2) ( (arb1 no esta vacio) y (arb2 no esta vacio) ) entonces Si(3) (Informacion de arb1 = Informacion de arb2) entonces Si(4) (Equivalente (Hijo izquierdo arb1, Hijo izquierdo arb2) ) entonces equiv ( Equivalente (Hijo derecho arb1, Hijo derecho arb2) Fin_si(4) Fin_si(3) Fin_si(2) Fin_si(1) Devolver equiv Fin Restringiendonos nuevamente a las operaciones basicas, el algoritmo de comprobacion seria el siguiente: Algoritmo Equivalente Entradas ArbolBinario arb1, arb2 Salida Boolean (CIERTO, FALSO) Variable Boolean equiv : (CIERTO, FALSO) Inicio equiv ( FALSO Si(1) ( ArbolVacio ( arb1 ) y ArbolVacio ( arb2 ) ) entonces equiv ( CIERTO Sino(1) Si(2) ( ( no ArbolVacio ( arb1 ) y no ArbolVacio ( arb2 ) ) entonces Si(3) ( Informacion ( arb1 ) = Informacion ( arb2 ) ) entonces Si(4) (Equivalente (HijoIzquierdo (arb1), HijoIzquierdo (arb2) ) ) entonces equiv ( Equivalente (HijoDerecho (arb1), HijoDerecho (arb2) ) Fin_si(4) Fin_si(3) Fin_si(2) Fin_si(1) Devolver equiv Fin ( La funcion, escrita en C++, siguiendo la interfaz de la clase propuesta quedaria como sigue: ( bool Equivalente (Arbol arb1, Arbol arb2) { bool b_aux, equiv = false; if (arb1.ArbolVacio () && arb2.ArbolVacio () ) equiv = true; else { if (!arb1.ArbolVacio () && !arb2.ArbolVacio () ) { b_aux = arb1.Informacion (x); b_aux = arb2.Informacion (y); if (x == y) if (Equivalente (arb1.HijoIzdo (), arb2.HijoIzdo() ) equiv = Equivalente (arb1.HijoDcho (), arb2.HijoDcho() ); } } return equiv; } ( Eliminacion de nodos en un arbol binario La eliminacion de nodos es otra operacion habitual de manipulacion de arboles binarios. Hay que tener en cuenta que esta operacion debe mantener la estructura del arbol y, por tanto, dependera del orden que se haya establecido dentro del arbol (si lo hay). Esto hace que la eliminacion de nodos se pueda convertir en una operacion mas compleja y que no se pueda hablar de un algoritmo para borrar en general, mas bien se podra hablar de algoritmos para borrar nodos para un determinado orden dentro del arbol. Si por ejemplo, un arbol ha sido generado teniendo en cuenta que sus nodos esta correctamente ordenados si se recorre el arbol en orden infijo, se debe considerar un algoritmo de borrado que no altere este orden. La secuencia de orden a que da lugar el recorrido infijo se debe mantener al borrar cualquier nodo del arbol. Existen dos casos a considerar cuando se borra un nodo del arbol. El primer caso, el mas simple, implica borrar un nodo que tenga al menos un subarbol vacio. El segundo caso, mas complejo, aparece cuando se desea borrar un nodo cuyos dos subarboles son no vacios. En este ultimo caso, hay que tener que el nodo borrado debe ser sustituido por otro nodo, de manera que se mantenga la estructura inicial del arbol. Cuando el nodo a borrar posee dos subarboles no vacios, el proceso de reestructuracion de las relaciones dentro del arbol resulta mas complejo, ya que cuando el nodo es terminal, eliminar ese nodo es tan simple como eliminar el enlace que le mantiene unido al arbol desde su nodo padre, y si el nodo posee un unico subarbol no vacio, el nodo debe ser sustituido por su nodo hijo. Estas dos ultimas situaciones no implican una reestructuracion importante del arbol. Suponiendo que el arbol debe mantener el orden establecido entre los nodos por un recorrido particular del mismo, el problema es determinar que nodo debe sustituir al nodo que se va a borrar. Si volvemos al ejemplo anterior, el orden establecido por el recorrido infijo del arbol seria: Recorrido infijo: C B D E A G F Si se desea borrar el nodo B, que tiene dos nodos hijos, el nodo que deberia sustituirle seria el nodo D, ya que es su sucesor en el orden establecido por el recorrido infijo (criterio escogido en este ejemplo particular). En general, sea cual sea el orden establecido entre los nodos, el sustituto de un nodo que se va a borrar debera ser su sucesor en dicho orden. De esta manera se mantiene la estructura global del arbol. Los diferentes criterios de ordenacion de los nodos van a dar lugar a distintos algoritmos para determinar el sucesor de un nodo, segun el orden establecido, y para modificar los enlaces entre nodos. Ejemplo Veamos el ejemplo concreto de un algoritmo que permita borrar un nodo en el caso en que se supone como valido el orden establecido entre los nodos por un recorrido infijo del arbol: SalPag Algoritmo BorrarNodo Entrada ArbolBinario arb { Raiz del arbol de donde se pretende borrar } ArbolBinario donde { Arbol a borrar } Variables ArbolBinario pad, suc Inicio Si(1) (donde no es vacio) entonces { Subarbol izquierdo vacio (o nodo terminal) } Si(2) (Hijo izquierdo de donde es vacio) entonces Si(3) (donde = arb) entonces arb ( Hijo derecho de donde Sino(3) pad ( Padre (donde, arb) Si(4) ( Hijo izquierdo de pad = donde ) entonces Hijo izquierdo de pad ( Hijo derecho de donde Sino(4) Hijo derecho de pad ( Hijo derecho de donde Fin_si(4) Fin_si(3) Liberar_Espacio (donde) Sino(2) {Subarbol derecho vacio} Si(5) (Hijo derecho de donde es vacio) entonces Si(6) ( donde = arb ) entonces arb ( Hijo izquierdo de donde Sino(6) pad ( padre (donde, arb) Si(7) (Hijo izquierdo de pad = donde ) entonces Hijo izquierdo de pad ( Hijo izquierdo de donde Sino(7) Hijo derecho de pad ( hijo izquierdo de donde Fin_si(7) Fin_si(6) Liberar_Espacio ( donde ) Sino(5) { Subarboles NO vacios } { El nodo raiz no es un caso especial } suc ( Sucesor_Infijo (donde) Informacion de donde ( Informacion de suc { Se puede utilizar la recursion : } { BorrarNodo ( arb, suc ) } { O borrarlo directamente: } pad ( padre (suc, arb) Si(8) (donde = pad) entonces Hijo derecho de pad ( Hijo derecho de suc Sino(8) Hijo izquierdo de pad ( Hijo derecho de suc Fin_si(8) Liberar_Espacio (suc) Fin_si(5) Fin_si(2) Fin_si(1) Fin Hace falta especificar los algoritmos que permitiran encontrar el padre (Padre) y el sucesor infijo de un nodo del arbol (Sucesor_Infijo). SalPag Algoritmo Padre Entradas ArbolBinario donde, arb { Se pretende buscar el subarbol 'donde' en el subarbol 'arb'} Salida ArbolBinario Variable ArbolBinario aux Inicio Si(1) (arb no es vacio) entonces Si(2) (Hijo izquierdo de arb = donde ) o (Hijo derecho de arb = donde) entonces Devolver (arb) Sino(2) aux ( Padre (donde, Hijo izquierdo de arb) Si(3) (aux es vacio) entonces aux ( Padre (donde, Hijo derecho de arb) Fin_si(3) Devolver ( aux ) Fin_si(2) Sino(1) Devolver (Arbol vacio) Fin_si(1) Fin El algoritmo que busca el padre de un nodo es en realidad un algoritmo general de busqueda, que permite recorrer todo el arbol hasta encontrar un nodo que cumpla la condicion establecida, independientemente del orden que pudiera existir en el arbol. Por lo tanto, puede ser facilmente modificado para poder localizar un nodo a partir de la informacion que contiene. En este caso, el algoritmo general de busqueda de un nodo por su informacion seria: Algoritmo Buscar Entradas Valor x ArbolBinario arb Salida ArbolBinario Variable aux: ArbolBinario Inicio Si(1) (arb no es vacio) entonces Si(2) (Informacion de arb = x ) entonces Devolver (arb) Sino(2) aux ( Buscar (x, Hijo izquierdo de arb) Si(3) (aux es vacio) entonces aux ( Buscar (x, Hijo derecho de arb) Fin_si(3) Devolver (aux) Fin_si(2) Sino(1) Devolver (Arbol vacio) Fin_si(1) Fin Volviendo al algoritmo de borrado, hemos visto que es necesario localizar el sucesor infijo de un nodo. En este caso el algoritmo es muy simple. Se trataria de recorrer el subarbol derecho del nodo, siempre a traves de los enlaces izquierdos, hasta encontrar un nodo que tenga el subarbol izquierdo vacio. Este algoritmo se puede representar facilmente tanto utilizando un esquema recursivo como iterativo. A continuacion se muestran los dos algoritmos. SalPag Algoritmo Sucesor_Infijo_Recursivo Entrada ArbolBinario arb { En este caso el primer valor de entrada del algoritmo debe ser el subarbol derecho } { del nodo del cual se desea encontrar el sucesor. La llamada deberia hacerse como: } { Sucesor_Infijo_Recursivo (Hijo derecho de arb ) } Salida ArbolBinario Inicio Si (Hijo izquierdo de arb no es un arbol vacio) entonces Devolver (Sucesor (hijo izquierdo de arb) ) Sino Devolver (arb) Fin_si Fin Algoritmo Sucesor_Infijo_Iterativo Entrada ArbolBinario arb Salida PunteroArbol Inicio arb ( Hijo derecho de arb Mientras (Hijo izquierdo de arb no sea vacio) hacer arb ( arb^.izq Fin_mientras Devolver ( arb ) Fin ( 14.6. Representacion de los arboles binarios Representacion mediante arrays Como hemos visto, si el arbol binario que se desea representar cumple las condiciones de arbol lleno o arbol completo, es posible encontrar una buena representacion secuencial del mismo. En esos casos, los nodos pueden ser almacenados en un array unidimensional, A, de manera que el nodo numerado como i se almacena en A[i]. Esto permite localizar facilmente las posiciones de los nodos padre, hijo izquierdo e hijo derecho de cualquier nodo i en un arbol binario arbitrario que cumpla tales condiciones. Lema 3: Si un arbol binario completo con n nodos se representa secuencialmente, se cumple que para cualquier nodo con indice i, 0(i((n-1), se tiene que: (1) El padre del nodo i estara localizado en la posicion (i-1)/2 si i>0. Si i=0, se trata del nodo raiz y no tiene padre. (2) El hijo izquierdo del nodo i estara localizado en la posicion (2*(i+1))-1 si 2*(i+1)-1EsVacio; if (arb.EsVacio == false) { Info = arb.Info; CopiarArbol (arb.Izdo, Izdo); CopiarArbol (arb.Dcho, Dcho); } } SalPag void Arbol::CopiarArbol ( const Arbol * const ori, PunteroArbol const & dest) { dest->EsVacio = ori->EsVacio; if (ori->EsVacio == false) { dest->Info = ori->Info; dest->Izdo = new Arbol; CopiarArbol (ori->Izdo, dest->Izdo); dest->Dcho = new Arbol; CopiarArbol (ori->Dcho, dest->Dcho); } } ( Otra manera, seria utilizando la idea de que la llamada al new en una clase se hace la llamada al constructor de la clase. Cuando invocamos al new, se reserva espacio para el nuevo elemento del tipo del operando con que se invoca al new. Si este es una clase, se llama de forma automatica al constructor adecuado, en principio si hacemos new Arbol se llamara al constructor por defecto (el que no tiene parametros.) Sin embargo si hacemos llamada con la clase con parametros, se buscara entre los constructores aquel que tenga el parametro adecuado. Si hacemos la llamada con new Arbol (arb), el constructor que acepta como parametro un arbol es el constructor de copia, de manera que se reservara espacio para el nuevo elemento y se llamara al constructor de copia con el parametro 'arb'. Con esto ya conseguimos hacer la reserva recursiva de todos los nodos del arbol ( Arbol::Arbol (const Arbol & arb) { if (arb.esvacio == true) esvacio = true; else { esvacio = false; info = arb.info; izdo = new Arbol(*arb.izdo); dcho = new Arbol(*arb.dcho); } } ( La funcion HacerArbol, al igual que el constructor de copia, puede basarse en el metodo de copia de arboles, o basarse en la utilizacion del new, que llamara al constructor de copia y que basicamente copia arboles: ( void Arbol::HacerArbol (Arbol & izq, Valor inf, Arbol & der) { EsVacio = false; Info = inf; Izdo = new Arbol; CopiarArbol (&izq, Izdo); Dcho = new Arbol; CopiarArbol (&der, Dcho); } ( O en la otra version: ( void Arbol::HacerArbol (Arbol & izq, Valor inf, Arbol & der) { esvacio = false; info = inf; izdo = new Arbol (izq); dcho = new Arbol (der); } ( Las funciones de consulta, tanto sobre el propio arbol, como sobre el contenido del arbol, seran relativamente sencillas: ( bool Arbol::ArbolVacio (void) { return EsVacio; } bool Arbol::Informacion (Valor & inf) { bool b_aux; if (EsVacio == true) b_aux = false; else { b_aux = true; inf = Info; } return b_aux; } Arbol & Arbol::HijoIzdo (void) { return *Izdo; } Arbol & Arbol::HijoDcho (void) { return *Dcho; } Para el destructor, podemos tambien utilizar una funcion recurrente que borre todos los nodos del arbol: Arbol::~Arbol (void) { if (!EsVacio) { BorrarArbol (Izdo); BorrarArbol (Dcho); EsVacio = true; } } SalPag void Arbol::BorrarArbol (PunteroArbol & arb) { if (!arb->EsVacio) { BorrarArbol (arb->Izdo); BorrarArbol (arb->Dcho); arb->EsVacio = true; } delete (arb); } El delete tiene un comportamiento similar en cierta manera al new. Cuando llamamos a delete si el operando es un objeto de una clase, se llama de forma automatica al destructor de la clase, y una vez finalizada la ejecucion del metodo, se libera la memoria asociada al objeto. Con esto el destructor quedarian como sigue: Arbol::~Arbol (void) { if (!EsVacio) { delete (Izdo); delete (Dcho); } } 14.7. Arboles binarios enlazados ("hilvanados") Al estudiar la representacion enlazada de un arbol binario es facil observar que existen muchos enlaces nulos. De hecho, existen mas enlaces nulos que punteros con valores reales. En concreto, para un arbol con n nodos, existen n+1 enlaces nulos de los 2*n enlaces existentes en la representacion (mas de la mitad). Como el espacio de memoria ocupado por los enlaces nulos es el mismo que el ocupado por los no nulos, podria resultar conveniente utilizar estos enlaces nulos para almacenar alguna informacion de interes para la manipulacion del arbol binario. Una forma de utilizar estos enlaces es sustituirlos por punteros a otros nodos del arbol (este tipo especial de punteros se conocen en la literatura anglosajona con el nombre de threads, que se podria traducir por hilos). En particular, los enlaces nulos situados en el subarbol derecho de un nodo se suelen reutilizar para apuntar al sucesor de ese nodo en un determinado recorrido del arbol, por ejemplo infijo, mientras que los enlaces nulos en subarboles izquierdos se utilizan para apuntar al predecesor del nodo en el mismo tipo de recorrido. Si para algun nodo no existe predecesor (porque es el primero en el recorrido establecido) o sucesor (porque es el ultimo), se mantiene con valor nulo el enlace correspondiente. Figura 7. Arbol binario hilvanado La ventaja de este tipo de representacion no es solo el mejor aprovechamiento de la memoria disponible, sino por la posibilidad de un acceso rapido al sucesor (o al predecesor) de un nodo, que como hemos visto anteriormente, puede ser una operacion frecuentemente necesaria. En general, los algoritmos que impliquen recorrer el arbol se podran diseñar de una manera mas eficiente. Para poder manejar correctamente toda la informacion de la que se dispone en la representacion hilvanada (con hilos) del arbol binario, es necesario poder distinguir entre lo que son punteros normales, que representan las relaciones reales entre los nodos, y lo que son hilos. Esto se puede hacer añadiendo dos campos booleanos a la representacion de los nodos del arbol. Estos nuevos campos indicaran si los enlaces izquierdo y derecho son hilos o no. La estructura de un nodo, siguiendo la representacion utilizada en lenguaje Pascal, vendria dada por la siguiente declaracion: Type ArbolHilvanado = ^Nodo Nodo = record Info: Valor; HiloIzq, HiloDer: Boolean; Izq, Der: ArbolHilvanado; end; Con el objeto de no mantener absolutamente ningun enlace nulo y para facilitar el recorrido del arbol, se suele añadir a la estructura un nodo raiz que no contiene informacion real (como se ha visto para otras estructuras de datos). El nodo raiz que representa el arbol vacio tendra la estructura que se muestra en la siguiente figura: HiloIzq Izq Info Der HiloDer CIERTO/FALSO NULO -- NULO CIERTO/FALSO Supongamos que el recorrido que se desea hacer del arbol es recorrido infijo. En este caso, cada puntero hilo enlazara con el sucesor infijo, si es un enlace derecho, y con el predecesor infijo, si es un enlace izquierdo. Se puede observar como, con esta nueva informacion, el proceso de recorrido del arbol se simplifica. Se comprueba que para cualquier nodo donde de un arbol binario enlazado de esta manera, se cumple que si donde^.HiloDer=CIERTO, el sucesor infijo de donde es donde^.Der (por definicion de los hilos). En otro caso (donde^.HiloDer=FALSO), el sucesor de donde se obtiene siguiendo un camino de enlaces izquierdos desde donde^.Der hasta que se encuentre un nodo para el que HiloIzq=CIERTO (similar a la busqueda del sucesor infijo en arboles binarios no hilvanados). El siguiente algoritmo encuentra el sucesor de cualquier nodo donde en un arbol binario hilvanado. Algoritmo Sucesor_Infijo Entrada arb: ArbolBinarioHilvanado Salida ArbolBinarioHilvanado Variable aux: ArbolBinarioHilvanado Inicio aux ( arb^.Der Si no arb^.HiloDer entonces Mientras no aux^.HiloIzq hacer aux ( aux^.izq Fin_mientras Fin_si Devolver ( aux ) fin SalPag Es interesante destacar que ahora es posible encontrar el sucesor en orden infijo de cualquier nodo sin necesidad de utilizar una pila auxiliar (o recursividad), con lo que se reducen los requerimientos de almacenamiento en memoria durante el proceso. De manera analoga, se puede encontrar el predecesor en orden infijo de cualquier nodo. Entonces se cumple que para un nodo donde, si donde^.HiloIzq=CIERTO, el predecesor infijo es donde^.Izq, sino el predecesor se obtiene siguiendo un camino de enlaces derechos desde donde^.Izq hasta que se encuentre un nodo para el que HiloDer=CIERTO. Si se desea recorrer el arbol binario siguiendo el orden infijo, es posible diseñar un algoritmo iterativo que lo haga eficientemente mediante llamadas sucesivas al algoritmo que localiza el sucesor de un nodo. Algoritmo Recorrido_Infijo Entrada arb: ArbolBinarioHilvanado Variable aux: ArbolBinarioHilvanado Inicio aux ( arb Mientras aux ( arb hacer aux ( Sucesor_Infijo ( aux ) Si ( aux = arb ) entonces Procesar ( aux^.info ) Fin_si Fin_mientras Fin Se puede comprobar que el coste computacional asociado a este algoritmo es O(n) para un arbol binario hilvanado con n nodos. En general, la utilizacion de enlaces hilos simplifica los algoritmos de recorrido del arbol, por lo que resultan recomendables cuando el recorrido del arbol (o los movimientos parciales dentro del mismo) es una operacion frecuente. Sin embargo, desde el punto de vista de la manipulacion general del arbol, hay que tener en cuenta que la insercion de nuevos nodos debe mantener en todo momento esta estructura de enlaces con los nodos sucesor y predecesor, y que cada vez que se inserte un nodo se debera comprobar si existen enlaces de este tipo que deban ser modificados o creados, ademas de los punteros normales que relacionan los nodos del arbol. 14.8. Representacion de arboles generales como arboles binarios Vamos a ver en este apartado que cualquier arbol se puede representar como un arbol binario. Esto es importante porque resulta mas complejo manipular nodos de grado variable (numero variable de relaciones) que nodos de grado fijo. Una posibilidad evidente de fijar un limite en el numero de relaciones seria seleccionar un numero k de hijos para cada nodo, donde k es el grado maximo para un nodo del arbol. Sin embargo, esta solucion desaprovecha mucho espacio de memoria. Lema 4: Para un arbol k-ario (es decir, grado k) con n nodos, cada uno de tamaño fijo, el numero de enlaces nulos en el arbol es n*(k-1)+1 de los n*k campos de tipo enlace existentes, n(1. Esto implica que para un arbol de grado 3, mas de 2/3 de los enlaces seran nulos. Y la proporcion de enlaces nulos se aproxima a 1 a medida que el grado del arbol aumenta. La importancia de poder utilizar arboles binarios para representar arboles generales reside en el hecho de que solo la mitad de los enlaces son nulos, ademas de facilitar su manipulacion. Para representar cualquier arbol por un arbol binario, vamos a hacer uso implicito de que el orden de los hijos de un nodo en un arbol general no es importante. Figura 8 Figura 9 La razon por la cual, para representar un arbol general, se necesitarian nodos con muchos enlaces es que, hasta ahora, hemos pensado en una representacion basada en la relacion padre-hijo dentro del arbol, y un nodo pueden tener un gran numero de hijos. Sin embargo, se puede encontrar una forma de representacion donde cada nodo solo necesite tener dos relaciones, una que lo una con el hijo que tenga mas a la izquierda y otra que lo una con el siguiente nodo hermano por la derecha. Estrictamente hablando, como el orden de los hijos en un arbol no es importante, cualquiera de los hijos de un nodo podria ser el hijo que esta mas a la izquierda el nodo padre y cualquiera de los nodos hermanos podria ser el siguiente hermano por la derecha. Por lo tanto, la eleccion de estos nodos no dejara de ser, hasta cierto punto, arbitraria. Podemos basarnos para esta eleccion en la representacion grafica del arbol que se desea almacenar. Veamos el siguiente ejemplo, el arbol binario correspondiente al arbol de la figura se obtiene conectando juntos todos los hermanos de un nodo y eliminando los enlaces de un nodo con sus hijos, excepto el enlace con el hijo que tiene mas a la izquierda. Este tipo de representacion se puede identificar con los arboles binarios que ya hemos visto, asociando el enlace izquierdo del arbol con el enlace al hijo de la izquierda y el enlace derecho con el enlace al nodo hermano. Se observa que de esta manera el nodo raiz nunca tendra un subarbol derecho, ya que no tiene ningun nodo hermano. Pero esto nos permite representar un bosque de arboles generales como un unico arbol binario, obteniendo primero la transformacion binaria de cada arbol y despues uniendo todos los arboles binarios considerando que todos los nodos raiz son hermanos. Ver el ejemplo de la figura. Figura 10 En todas estas transformaciones de arbol general a arbol binario hay que tener en cuenta la interpretacion que se deben hacer de las relaciones, no es lo mismo que un nodo este a la izquierda o a la derecha de otro, ya que los enlaces izquierdos unen un nodo con su hijo, mientras que los enlaces derechos unen dos nodos hermanos. De cualquier forma, teniendo en cuenta este aspecto, es posible aplicar los algoritmos de manipulacion de arboles binarios que se han visto hasta ahora. De hecho, en todos estos algoritmos se diferenciaba claramente entre el tratamiento del subabol izquierdo y el del subarbol derecho. 14.9. Arboles binarios de busqueda Los arboles binarios de busqueda son estructuras de datos que presentan un gran rendimiento cuando las funciones a realizar implican busquedas, inserciones y eliminacion de nodos. De hecho, con un arbol de busqueda, dichas operaciones se pueden realizar tanto a partir de un valor clave, como por un valor ordinal (es decir, encontrar un elemento con clave x, encontrar el sexto elemento mas pequeño, borrar el elemento con clave x, borrar el sexto elemento mas pequeño, insertar un elemento y determinar su ordinal dentro del arbol). Definicion: Un arbol binario de busqueda es un arbol binario, que puede estar vacio, y que si es no vacio cumple las siguientes propiedades: (1) Todos los nodos estan identificados por una clave y no existen dos elementos con la misma clave. (2) Las claves de los nodos del subarbol izquierdo son menores que la clave del nodo raiz. (3) Las claves de los nodos del subarbol derecho son mayores que la clave del nodo raiz. (4) Los subarboles izquierdo y derecho son tambien arboles binarios de busqueda. La primera propiedad resultaria redundante, ya que de las propieades (2), (3) y (4) se puede deducir que la clave de un nodo es unica. Sin embargo, la aparicion explicita de esta propiedad hace que la definicion sea mas clara. Operaciones en arboles binarios de busqueda Veamos ahora como manipular este tipo especial de arboles binarios. Estudiaremos las operaciones de busqueda, insercion y borrado. Busqueda La definicion de arbol binario de busqueda especifica un criterio en la estructuracion del arbol en funcion de las claves de los nodos. En este caso, existe un criterio de ordenacion de los nodos. Por lo tanto, sera bastante simple describir un metodo eficiente de busqueda que explote esa ordenacion. Suponer que se busca un elemento que posea una clave x. La busqueda comenzara por el nodo raiz del arbol. La clave de ese nodo informara por donde debe continuar la busqueda, ya no es necesario recorrer exhaustivamente todos los nodos del arbol. Si la clave del nodo es igual a x, la busqueda finaliza con exito. Si la clave es menor que x, se sabe que si existe un nodo en el arbol que posea como clave el valor x debera estar en el subarbol derecho, por lo tanto la busqueda debera continuar por esa parte del arbol. Si, por el contrario, la clave del nodo es mayor que x, entonces la buqueda debera continuar por el subarbol izquierdo. El proceso continuara hasta que se encuentre un nodo con clave igual a x o un subarbol vacio, en cuyo caso se puede asegurar que no existe ningun nodo con clave x en el arbol. Este metodo de busqueda sugiere seguir un esquema recursivo. Suponiendo que la clave que identifica cada nodo es un campo contenido en la informacion general del nodo, el algoritmo de busqueda quedaria como sigue: Algoritmo Buscar_Recurrente_ABB {* Buscar en el arbol arb la clave x *} {* Devolver la posicion del nodo donde se encuentre, NULO si no esta *} Entradas Valor(clave) x ArbolBinario arb Salida ArbolBinario Inicio Si(1) (arb es un arbol vacio) entonces Devolver (Arbol vacio) Sino(1) Si(2) (x = Informacion(clave) de arb) entonces Devolver (arb) Sino(2) Si(3) (x < Informacion(claver) de arb) entonces Devolver (Buscar_Recurrente_ABB (x, Hijo izquierdo de arb) ) Sino(3) Devolver (Buscar_Recurrente_ABB (x, Hijo derecho de arb) ) Fin_si(3) Fin_si(2) Fin_si(1) Fin En este ejemplo, la recursividad puede ser facilmente susituida por un esquema iterativo mediante la utilizacion de un bucle de repeticion mientras. En ese caso, el algoritmo de busqueda iterativo seria: Algoritmo Buscar_Iterativo_ABB { Buscar en el arbol arb la clave x } { Devolver la posicion del nodo donde se encuentre, NULO si no esta } Entradas Valor(clave) x ArbolBinario arb Salida ArbolBinario Variables ArbolBinario aux Boolean encontrado: (CIERTO, FALSO) Inicio aux ( arb encontrado ( falso Mientras (aux no sea arbol vacio) y (NO encontrado) hacer Si(1) (x = informacion (clave) de aux) entonces encontrado ( CIERTO Sino(1) Si(2) (x < Informacion (clave) de donde) entonces aux ( Hijo izquierdo de aux Sino(2) aux ( Hijo derecho de aux Fin_si(2) Fin_si(1) Fin_mientras Si(3) (encontrado) entonces Devolver (aux) Sino(3) Devolver (Arbol vacio) Fin_si(3) Fin SalPag El proceso de busqueda en un arbol binario de busqueda resulta muy eficaz. El coste asociado seria O(h), donde h es la altura del arbol. Hay que hacer notar que la dependencia es lineal con la altura del arbol y no con el numero de elementos del mismo. En funcion del numero de nodos en el arbol, n, el coste seria O(log n) (Esto es cierto si el arbol esta suficientemente equilibrado. En el peor de los casos el arbol binario de busqueda degeneraria en una lista y el coste llegaria a ser lineal.) El metodo de busqueda se asemeja mucho al metodo de busqueda binaria sobre arrays ordenados, tras la comparacion con un elemento se puede decidir en que region de la estructura se puede encontrar la informacion buscada, descartandose el resto de los elementos de la estructura. De esta forma, se reduce considerablemente el numero de comparaciones necesarias para localizar el elemento. Los algoritmos descritos, escritos en C++ podrian quedar de la siguiente manera: ( Arbol & Arbol::BuscarRecurrenteABB (Valor x) { PunteroArbol p_aux; if (esvacio == true) p_aux = this; else if (info == x) p_aux = this; else if (x < info) p_aux = &(izq.BuscarRecurrenteABB (x) ); else p_aux = &(der.BuscarRecurrenteABB (x) ); return (*p_aux); } Arbol & Arbol::BuscarIterativoABB (Valor x) { PunteroArbol p_aux; p_aux = this; while ( (p_aux->esvacio != true) && (p_aux->info != x) ) { if (x < info) p_aux = p_aux->izq; else p_aux = p_aux->der; } return (*p_aux); } ( En cuanto a buscar nodos en funcion de la posicion ocupada en el orden de las claves, es decir, por el ordinal de las claves, es necesario añadir a cada nodo un campo adicional que guarde el numero de elementos que posee su subarbol izquierdo mas uno (sea este campo TamIzq). De esta forma, el siguiente algoritmo permitiria realizar la busqueda: Algoritmo Buscar_Orden Entrada k: entero arb: ArbolBinario Salida ArbolBinario Variables aux: ArbolBinario encontrado: (CIERTO, FALSO) i: entero Inicio aux ( arb encontrado ( FALSO i ( k Mientras ( aux ( nulo ) y ( NO encontrado ) hacer Si(1) ( i = aux^.TamIzq ) entonces encontrado ( CIERTO Sino(1) Si(2) ( i < aux^.TamIzq ) entonces aux ( aux^.Izq Sino(2) i ( i - aux^.TamIzq aux ( aux^.Der Fin_si(2) Fin_si(1) Fin_mientras Si(3) ( encontrado ) entonces Devolver ( aux ) Sino(3) Devolver ( NULO ) Fin_si(3) Fin Como se puede observar, en este caso tambien es posible realizar el proceso de busqueda con un coste que depende linealmente de la altura del arbol. Insercion La insercion de un nuevo nodo en un arbol binario de busqueda debe realizarse de tal forma que se mantengan las propiedades del arbol. De modo que lo primero que hay que hacer es comprobar que en el arbol no existe ningun nodo con clave igual a la del elemento que se desea insertar. Si la busqueda de dicha clave falla, entonces se insertara el nuevo nodo en el punto donde se ha parado la busqueda, que sera el punto del arbol donde, de existir, deberia estar ubicada dicha clave. Hay que considerar que todo proceso de busqueda fallido termina en un enlace nulo, por tanto, el nodo a insertar siempre sera un nodo terminal, lo que facilitara la operacion. SalPag Insertar 19 ® Figura 11 El algoritmo que implementa la estrategia de insercion es el siguiente: Algoritmo Insertar Entrada Valor x ArbolBinario (por referencia) arb Salida (CIERTO, FALSO) {* el algoritmo informa si ha sido posible la insercion *} Variables PunteroArbol donde, padre encontrado: (CIERTO, FALSO) Inicio {* buscar x.clave en el arbol, donde indica la localizacion *} {* si donde=NULO entonces no esta y padre es el padre de donde *} padre ( Arbol Vacio donde ( arb encontrado ( FALSO Mientras ( (donde no sea un arbol vacio) y (no encontrado) ) hacer padre ( donde Si(1) (x.clave = Informacion (clave) de donde) entonces encontrado ( CIERTO Sino(1) Si(2) (x.clave < Informacion (clave) de donde) entonces donde ( Hijo izquierdo de donde Sino(2) donde ( Hijo derecho de donde Fin_si(2) Fin_si(1) Fin_mientras {insertar} Si(3) (no encontrado) entonces donde ( Crear_espacio Hijo izquierdo de donde ( Arbol vacio Hijo derecho de donde ( Arbol vacio Informacion de donde ( x Si(4) (padre es arbol vacio) entonces arbol ( donde {* insertar el primer nodo, la raiz *} Sino(4) Si(5) (x.clave < informacion (clave) de padre) entonces Hijo izquiedo de padre ( donde Sino(5) Hijo derecho de padre ( donde Fin_si(5) Fin_si(4) Devolver (CIERTO) Sino(3) Devolver (FALSO) Fin_si(3) Fin Esta funcion se podria implementar facilmente de forma recursiva de la siguiente manera: Algoritmo Insertar Entrada valor x PunteroArbol arb (por referencia) Salida (CIERTO, FALSO) {* el algoritmo informa si ha sido posible la insercion *} Inicio Si(1) (arb es arbol vacio) entonces arb ( Crear_espacio Hijo izquierdo de arb ( Arbol vacio Hijo derecho de arb ( Arbol vacio informacion de arb ( x Devolver (CIERTO) Sino(1) Si(2) (x.clave = Informacion (clave) de arb) entonces Devolver (FALSE) Sino(2) Si(3) (x.clave < Informacion (clave) de arb) entonces Devolver (Insertar (Hijo izquierdo de arb, x) ) Sino(3) Devolver (Insertar (Hijo derecho de arb, x ) Fin_si(3) Fin_si(2) Fin_si(1) Fin Estos algoritmo en C++, quedarian como sigue: ( bool Arbol::InsertarIterativo (Valor x) { PunteroArbol donde; bool enc = false, error = true; while ( (donde->esvacio != true) && (!enc) ) { if (x == donde->info) enc = true; else if (x < donde->info) donde = donde->izq; else donde = donde->der; } if (!enc) { error = false; donde->esvacio = false; donde->izq = new Arbol; donde->der = new Arbol; donde->info = x; } } SalPag bool Arbol::InsertarRecurrente (Valor x) { error = true; if (esvacio == true) { error = false; donde->esvacio = false; donde->izq = new Arbol; donde->der = new Arbol; donde->info = x; } else if (x != info) if (x < info) error = izq->InsertarRecurrente (x); else error = der->InsertarRecurrente (x); return error; } ( Si nos fijamos, la primera parte de la insercion es la busqueda del lugar en donde queremos insertar. Podemos utilizar el metodo de busqueda para evitar esa parte. Utilizando el metodo de busqueda (nos daria igual el metodo iterativo o el recursivo para hacerlo) nos quedaria la siguiente insercion: ( bool Arbol::Insertar (Valor x) { bool error = true; Arbol & arb = Buscar (x); if (arb->esvacio) { error = false; donde->esvacio = false; donde->izq = new Arbol; donde->der = new Arbol; donde->info = x; } return error; } ( Si los nodos del arbol poseen el campo TamIzq, comentado anteriormente, en el algoritmo de insercion habria que considerar la actualizacion de este campo en aquellos nodos donde sea necesario. La operacion de insercion de un nodo se puede hacer en un tiempo O(h), donde 'h' es la altura del arbol de busqueda. Borrado La operacion de borrado en un arbol de busqueda es muy simple. Hay que tener en cuenta que en todo arbol de busqueda los nodos se pueden ordenar por su clave si se recorre el arbol siguiendo el criterio infijo. El orden establecido por este recorrido se debe mantener aunque se elimine un nodo del arbol. Por tanto, no hay mas que utilizar el algoritmo de borrado sobre arboles binarios cuando se desea mantener el orden infijo de los nodos. Este algoritmo ha sido visto con anterioridad en el texto y no es necesario repetirlo en este apartado. Ejemplo de aplicacion de arboles binarios de busqueda Contar el numero de veces que aparecen las palabras que forman un texto. Algoritmo: - Leer el texto palabra a palabra. - Almacenar las palabras leidas en forma de arbol binario de busqueda con un campo asociado que indique el nunero de veces qe aparece cada una. - Cuando se lee una nueva palabra, comprobar si esta o no en el arbol, lo que indica si ya habia aparecido anteriormente o no. Si la palabra esta en el arbol aumentar su contador de apariciones en 1, sino insertarla en el arbol e iniciar el contador a 1. - Cuando se alcance el final del texto se tendra toda la informacion de interes en forma de arbol de busqueda, si se recorre este arbol en orden infijo se podra obtener un listado en orden alfabetico de las palabras con la frecuencia de aparicion de cada palabra. SalPag Escribiendo este algoritmo en forma de programa en Pascal, este podria quedar como sigue: Program Frecuencia_Palabras (input,output); {* Contar la frecuencia de aparicion de las palabras de un texto *} {* almacenado en un fichero *} {* Ejemplo de utilizacion de arboles binarios de busqueda *} Type Cadena = String[25]; Numeros = 1..MaxInt; Valor = Record Pal : Cadena; Cont: Numeros; End; PunteroArbol = ^NodoArbol; NodoArbol = record Info : Valor; Izq, Der: PunteroArbol; end; Var nombre : Cadena; fichero: Text; letras : Set Of Char; {* Leer el texto palabra a palabra *} {* La funcion indica si se ha alcanzado el final del fichero *} Function Leer ( Var texto: Text; Var palabra: Cadena): Boolean; Var fin: Boolean; ch : Char; Begin palabra := ''; fin := FALSE; While ( ( Not Eof ( texto ) ) and ( Not fin ) ) Do Begin Read ( texto, ch ); If ( ch In letras ) Then palabra := palabra + ch Else If ( palabra <> '' ) Then fin := TRUE; End; leer := Eof ( texto ); End; {* Recorrido infijo del arbol escribiendo la informacion de interes *} Procedure Infijo ( arbol: PunteroArbol ); Begin If ( arbol <> NIL ) Then Begin Infijo ( arbol^.Izq ); WriteLn ( arbol^.Info.Pal:15, ':':3, arbol^.Info.Cont:3 ); Infijo ( arbol^.Der ); End End; {* Operacion de insercion en el arbol de busqueda *} Procedure Insertar ( x: Cadena; Var arbol: PunteroArbol ); Var nodo, padre: PunteroArbol; encontrado : Boolean; Begin padre := NIL; nodo := arbol; encontrado := FALSE; While ( ( nodo <> NIL ) And ( Not encontrado ) ) Do Begin padre := nodo; If ( x = nodo^.Info.Pal ) Then encontrado := TRUE Else If ( x < nodo^.Info.Pal ) Then nodo := nodo^.Izq Else nodo := nodo^.Der; End; If ( Not encontrado ) Then Begin New ( nodo ); nodo^.Izq := NIL; nodo^.Der := NIL; nodo^.Info.Pal := x; nodo^.Info.Cont := 1; If ( padre = NIL ) Then arbol := nodo Else If ( x < padre^.Info.Pal ) Then padre^.Izq:=nodo Else padre^.Der:=nodo End Else nodo^.cont := nodo^.cont + 1; End; SalPag {* Algoritmo para contar la frecuencia de aparicion de las palabras *} Procedure Frecuencia ( Var texto: Text ); Var arbol : PunteroArbol; palabra : Cadena; fin_texto: Boolean; Begin arbol := NIL; fin_texto := FALSE; While ( Not fin_texto ) Do Begin fin_texto := Leer ( texto, palabra ); If ( palabra <> '' ) Then insertar ( palabra, arbol ); End; infijo ( arbol ); End; {* Bloque principal del programa *} BEGIN letras := ['a'..'z', 'A'..'Z']; Write ( 'Nombre del fichero a analizar: ' ); ReadLn ( nombre ); Assign ( fichero, nombre); Reset ( fichero ); frecuencia ( fichero ); Close ( fichero ) END. ( 14.10. Heaps (monticulos) Veamos otro tipo especial de arbol binario, los llamados heaps (moticulos), que se pueden representar eficazmente con un vector. Definicion: Un heap de maximos (minimos), max heap (min heap), es un arbol binario completo tal que, el valor de la clave de cada nodo es mayor (menor) o igual que las claves de sus nodos hijos (si los tiene). Monticulo de maximos max heap Monticulo de minimos mineap Figura 12 De la definicion se deduce que la clave contenida en el nodo raiz de un max heap (min heap) es la mayor (menor) clave del arbol. Pero esto no quiere decir que sea la unica con ese valor. La estructura heap tiene interesantes aplicaciones, por ejemplo, la ordenacion de arrays (algoritmo heapsort) o el mantenimiento de las llamadas colas de prioridad. Las colas de prioridad son un tipo especial de colas donde todo elemento que se inserta en la cola lleva asociado una prioridad, de forma que el elemento que se borra de la cola es el primero entre los que tengan la maxima (o minima) prioridad. Los heaps, como arboles binarios completos que son, se pueden representar de forma eficaz mediante una estructura secuencial (un array). A cada nodo del arbol se le asigna una posicion dentro de la secuencia en funcion del nivel del arbol en el que se encuentra y dentro de ese nivel de la posicion ocupada de izquierda a derecha. Por ejemplo: Figura 13 De forma que para un nodo representado por el elemento A[i] se cumple que: (i) El nodo padre estara localizado en la posicion [(i-1) / 2], si i > 0. El nodo raiz, i=0, no tiene padre). (ii) Si tiene hijos estaran localizados en las posiciones [2(i+1)-1] y [2(i+1)]. Si i > [(n+1) / 2 - 1], el nodo no tiene hijos. Una caracteristica fundamental de esta estructura de datos es la propiedad que caracteriza a un moticulo puede ser restaurada eficazmente tras cualquier modificacion de un nodo (cambiar el valor de la clave, insertar un nodo, borrar un nodo, etc.). Representacion de monticulos Ya se ha comentado que por ser el monticulo un arbol lleno, es eficiente su representacion mediante arrays. De manera que la representacion del monticulo contendra necesariamente un array donde guardar la informacion. Esto supondra tener que estimar un maximo para la cantidad de elementos que podemos guardar en el monticulo. Ademas del array sera necesario llevar la cuenta de cuantos de los elementos del array son validos (forman parte del heap). Tipos: Heap = registro Info: Vector [0..MAX-1] de Valor; Num : Entero entre 0 y MAX-1; fin A partir de esta informacion si hacemos la implementacion en una clase de C++, la parte privada de la clase heap quedaria como sigue: const int MAX = ?? class Heap { public: ... private: Valor Info[MAX]; int Num; } Operaciones basicas sobre monticulos Supongamos que se trata de un monticulo de maximos (cualquier comentario sobre este tipo de monticulos se puede extender facilmente a los monticulos de minimos). En este caso, se debe cumplir que la clave de cualquier nodo sea mayor o igual que las claves de sus hijos. Si se modifica el valor de un nodo incrementando su valor, entonces es posible que la propiedad del monticulo no se cumpla con respecto a sus nodos antecesores, no respecto a sus hijos. Esto implicaria ir ascendiendo por el arbol comprobando si el nodo modificado es mayor que el padre, si es asi intercambiarlos y repetir el proceso en un nivel superior hasta que se encuentre que no es necesario realizar ningun intercambio o que se llegue al nodo raiz. En cualquier caso, tras ese proceso se habra restaurado la propiedad del monticulo. Este algoritmo quedaria como sigue: Algoritmo Subir {* Se utiliza cuando se incrementa el valor del nodo situado en la posicion pos *} Entradas Heap arb Posicion pos (indice) SalPag Inicio Si ( (pos > 0) y (arb.Info[pos] > arb.Info[(pos - 1) / 2] ) entonces Intercambiar (arb.Info[pos] , arb.info[(pos - 1) / 2] ) Subir (arb, (pos - 1) / 2 ) Fin_si Fin Si por el contrario, modificamos un nodo haciendo disminuir su valor, el problema consistira en comprobar la propiedad respecto a sus descendientes. Si la clave del nodo es mayor que las claves de sus hijos, entonces la propiedad se sigue cumpliendo, si no es asi, hay que intercambiar la clave de este nodo con la del hijo que tenga la clave maxima y repetir todo el proceso desde el principio con este nodo hijo hasta que no se realice el intercambio. Algoritmo Bajar {* Se utiliza cuando disminuye el valor del nodo situado en la posicion pos *} Entradas Heap arb Posicion pos (indice) Variables Posicion max (indice) Inicio max ( pos Si ( ( (2*(pos+1) - 1) < n) y (arb.Info[2*(pos+1)-1] > arb.Info[max] ) ) entonces max ( 2*(pos+1)-1 Fin_si Si ( (2*(pos+1) < n ) y ( arb.Info[2*(pos+1)] > arb.Info[max] ) entonces max ( 2*(pos+1) Fin_si Si ( max ( pos ) entonces Intercambiar ( arb[pos], arb[max] ) Bajar (arb, max) Fin_si Fin A partir de estos dos algoritmos basicos que permiten restaurar la estructura del monticulo, se pueden definir las operaciones de insercion y borrado de elementos en esta estructura de datos. Insercion Al intentar añadir un nuevo elemento al monticulo, no se sabe cual sera la posicion que ocupara el nuevo elemento de la estructura, pero lo que si se sabe es que, por tratarse de un arbol completo, donde se debe enlazar el nuevo nodo, siempre sera en la ultima posicion de la estructura. Por ejemplo, en el siguiente monticulo formado por cinco elementos, si se intenta añadir un nuevo elemento, sea el que sea, se conoce cual sera la estructura final del arbol: Figura 14 Si se almacena en el nuevo nodo la informacion que se desea insertar, lo mas probable sera que la propiedad del monticulo no se conserve. Como el nuevo nodo siempre es terminal, para mantener la propiedad del monticulo bastara con aplicar el algoritmo subir a partir del nodo insertado, con lo que el algoritmo de insercion resulta verdaderamente simple. Algoritmo Insertar Entrada Heap arb Valor x Inicio arb.Num ( arb.Num + 1 arb.Info[arb.Num - 1] ( x Subir (arb, arb.Num - 1) Fin SalPag Borrar (una posicion 'pos' cualquiera) Al igual que en la operacion de insercion, hay que tener en cuenta que el monticulo es un arbol completo y que, para que se mantenga esa propiedad, el nodo que debe desaparecer realmente es el que esta situado en la ultima posicion. Por lo tanto, la estrategia a seguir para borrar cualquier nodo del monticulo podria ser: sustituir la informacion del nodo a borrar por la del utlimo nodo del monticulo y considerar que el arbol tiene un nodo menos (n-1); como con esta modificacion seguramente se habra alterado la propiedad del monticulo, entonces aplicar el algoritmo subir o bajar, lo que sea preciso, para restaurar esa propiedad. La aplicacion del algoritmo subir o del algoritmo bajar dependera de que la modificacion de la informacion del nodo haya implicado un incremento (aplicar subir) o una disminucion (aplicar bajar) de la clave. Algoritmo Borrar Entrada Heap arb Posicion pos (indice) Variable x: Valor Inicio x ( arb.info[pos] arb.Info[pos] ( arb.Info[arb.Num - 1] arb.Num ( arb.Num - 1 Si(1) (arb.Info[pos] ( x) entonces Si(2) (arb.Info[pos] > x ) entonces Bajar (arb, pos) Sino(2) Subir (arb, pos) Fin_si(2) Fin_si(1) Fin Aplicacion de los monticulos Los monticulos tienen como aplicacion fundamental el mantenimiento de las llamadas colas de prioridad. Esta estructura de datos es un tipo especial de cola, donde cada elemento lleva asociado un valor de prioridad, de forma que cuando se borra un elemento de la estructura, este sera el primero de los elementos con la mayor (menor) prioridad. En cualquier instante se puede insertar un elemento con prioridad arbitraria. Si la utilizacion de la cola de prioridad requiere borrar el elemento con la mayor (menor) prioridad, entonces se utiliza para su representacion un monticulo de maximos (minimos), donde resulta inmediata la localizacion de ese elemento. En un monticulo de maximos resulta inmediato obtener el valor maximo de las claves del arbol. Como se ha visto anteriormente, este valor esta siempre situado en la raiz del arbol, por lo tanto bastaria con acceder al primer elemento del array A[0]. Algoritmo Borrar_raiz Entrada Heap arb Inicio arb.Info[0] ( arb.Info[arb.Num - 1] arb.Num ( arb.Num - 1 Bajar (arb, pos) Fin Veamos algunos ejemplos practicos de colas de prioridad: Ejemplo 1: Supongamos que se desea informatizar la lista de espera para la realizacion de operaciones quirurgicas en un quirofano de un hospital. Se desea utilizar el quirofano de la manera mas eficiente posible, de forma que en todo instante se opere al enfermo que mas lo necesite siguiendo el orden de la lista de espera. En ese caso, es posible asignar algun tipo de prioridad a cada uno de los enfermos, en funcion, por ejemplo, de la gravedad de la operacion, del tiempo de ocupacion del quirofano o incluso, del precio de la operacion. De esta forma, cada vez que el quirofano quede libre se recurira a la lista de espera y se seleccionara a aquel enfermo con la prioridad mas alta. Desde el punto de vista de programacion del proceso, se podria utilizar una representacion de la lista de espera en funcion de un monticulo de maximos, siendo la informacion asociada con los nodos del arbol los datos de cada enfermo y la clave de identificacion la prioridad de los mismos. Cuando un enfermo ingresa para ser operado en el hospital, se le asigna una prioridad y se insertan sus datos como un nuevo nodo del monticulo (operacion insertar), cuando el quirofano queda libre, se ocupara con el enfermo cuyos datos esten situados en la raiz del monticulo (maxima prioridad) y se reestructurara el mismo. Ejemplo 2: La gestion de los recursos de un ordenador en un entorno multiusuario (CPU, memoria, disco, perifericos, etc.) se suele realizar tambien utilizando colas de prioridad. El problema se asemeja mucho al del ejemplo anterior. Existe un dispositivo que se desea utilizar y existen varios posibles usuarios, por lo tanto hay que seleccionar aquel usuario que permita utilizar de la manera mas eficiente posible dicho dispositivo. Para ello, el sistema operativo asigna una prioridad a cada peticion de utilizacion, de manera que se atiende a las peticiones en funcion de la prioridad y el orden temporal en que se han realizado. La prioridad asignada a cada prioridad puede depender de varias cosas. el tipo de usuario que la realiza (en un sistema multiusuario, no todos los usuarios tienen el mismo tratamiento, existen usuarios con mas prioridad que otros), el tiempo de utilizacion del dispositivo solicitado (normalmente un trabajo que requiera poco tiempo de utilizacion del dispositivo se debera atender antes que otro que requiera mucho mas tiempo, de esta manera se agiliza el tiempo de respuesta del sistema), el tiempo que hace que el usuario no accede a ese recurso, etc... En base a todas estas consideraciones se puede establecer una prioridad a cada peticion de utilizacion de un recurso del ordenador y mantener una cola de prioridad (generalmente un monticulo de maximos) para cada uno de estos recursos que gestione eficientemente su uso. ( 14.11. Ordenacion con arboles En los dos ultimos tipos de arboles binarios comentados, se ha visto como se puede organizar eficientemente la informacion en estas estructuras en base a una clave de informacion, de manera que sea facil extraer informacion relacionada con esa clave (buscar por clave, acceder a la clave maxima, acceder a la clave minima, etc.). Esto hace que parezca evidente la utilizacion de estas estructuras de datos para resolver un problema tan habitual como pueda ser el problema de la ordenacion de informacion. Si nos centramos en el problema de la ordenacion interna sobre arrays, que fue el problema estudiado en su momento, se puede pensar en los monticulos como el tipo de arboles que podrian resolver el problema. Hay que tener en cuenta que, normalmente, la representacion de los monticulos se hace precisamente con arrays y que en estas estructuras es muy facil acceder al elemento con clave maxima (o minima, segun sea la organizacion del monticulo), con lo que se podria establecer algun tipo de algoritmo que aprovechando esta propiedad ordene la informacion del array. Si consideramos que inicialmente el array puede estar arbitrariamente ordenado, esto implicara que, en general, no se cumplira la propiedad de monticulo de maximos, por lo que habria que empezar por formar un monticulo a partir de ese array. Una vez formado el monticulo, es facil saber que elemento debe ocupar la ultima posicion del array ordenado, ese elemento siempre sera el que ocupa la raiz del arbol (el primero del array). Si se intercambia el primer elemento con el ultimo, se habra logrado ubicar correctamente el elemento maximo. Se puede ahora considerar que el array tiene un elemento menos (el que esta bien colocado) y reorganizar el monticulo con un elemento menos. Si se repite este proceso hasta que se tenga un monticulo con un unico elemento, se puede asegurar que el array estara finalmente ordenado. Este metodo de ordenacion se conoce con el nombre de Heapsort y el algoritmo seria el siguiente: Algoritmo Heapsort Entrada Array[0..n - 1] vect Variable Indice i Inicio Hacer_Heap (vect) Desde i ( n - 1 hasta 1 hacer Intercambiar (vect[0], vect[i]) Bajar (vect[0..i-1], 0) Fin_desde Fin Para terminar, haria falta especificar como se puede construir un monticulo de maximos a partir de un array arbitrariamente ordenado. La solucion es bastante simple, ir formando monticulos de tamaño creciente hasta formar uno que contenga los n elementos del array. Comenzando desde atras hacia adelante, se puede considerar que los n div 2 ultimos elementos son nodos terminales y que, por lo tanto, forman monticulos de tamaño 1 que no requieren ningun tipo de reorganizacion. Si consideramos ahora secuencialmente los elementos a partir de n div 2 hasta 1, es como si se fuese añadiendo cada vez un nodo mas a cada uno de los monticulos ya formados, como esta insercion modifica la estructura del monticulo corespondiente, es necesario reorganizarlo mediante el procedimiento bajar. Al final del proceso, se puede asegurar que el array estara organizado en forma de monticulo de maximos. El algoritmo seria el siguiente: Algoritmo Hacer_Heap Entrada Array[0..n-1] vec Variable i: Indice Inicio Desde i ( (n - 1) / 2 hasta 0 hacer Bajar (vect, i) Fin SalPag Hay que tener en cuenta que tanto en este caso (algoritmo HacerHeap), como en el algoritmo anterior (Heapsort) se esta pasando al algoritmo Bajar un vector y no un heap, de manera que habria que modificar convenientemente el algoritmo Bajar para que funcionase de forma correcta. En cuanto al coste del algoritmo de ordenacion hay que tener en cuenta el coste de cada una de las dos partes del algoritmo, Hacer_Heap y la reorganizacion de 'n-1' monticulos mediante el algoritmo Bajar. La formacion del monticulo tiene un coste lineal con el tamaño del array, O(n), mientras que el coste del bucle que reorganiza los monticulos de tamaño decreciente es O(n*log n). Asintoticamente, la funcion logaritmica domina a la lineal y el coste final del algoritmo de ordenacion sera O(n*log n). Por lo tanto, resulta que el metodo de ordenacion heapsort es mas eficiente que los metodos directos vistos en el tema dedicado a vectores. 1 Demostraciones de estos lemas se pueden encontrar en Fundamentals of Data Structures in Pascal, Horowitz&Sahni, pags. 260,261 Algoritmos y estructuras de datos I Ricardo Ferris / Jesus Albert Ricardo Ferris / Jesus Albert Algoritmos y estructuras de datos I 92 Ricardo Ferris / Jesus Albert T