Captulo 5. rboles5 rboles5.1 Descripcin y terminologa fundamental.5.2 Especificacin del TDA rbol.5.3 Ejemplos de uso del TDA rbol.5.4 Implementaciones del TDA rbol.5.5 Especificacin del TDA rbol Binario.5.6 Ejemplos de uso del TDA rbol Binario.5.7 Implementaciones del TDA rbol Binario.5.8 rboles Parcialmente Ordenados: Colas de Prioridad. 5.9 rboles Binarios de Bsqueda.

5.1 Descripcin y terminologa fundamentalUn rbol es una coleccin de elementos entre los cuales existe una estructura jerrquica definida mediante una relacin de paternidad entre los elementos. Entre los elementos, que llamaremos nodos, se distingue uno que es el nodo raz. Matemticamente, un rbol es un grafo no orientado, conexo y acclico en el que existe un vrtice destacado llamado raz. Un rbol A n-ario (en adelante slo rbol), siendo n1, es un conjunto de elementos del mismo tipo tal que:O bien es el conjunto vaco, en cuyo caso se le denomina rbol vaco.O bien no es vaco, en cuyo caso existe un elemento distinguido llamado raz, y el resto de los elementos se distribuyen en en m subconjuntos disjuntos A1 ,..., Am, con 0mn, cada uno de los cuales es un rbol n-ario, llamados subrboles del rbol original.

5.1 Descripcin y terminologa fundamentalCuando el orden de los subrboles importa, el rbol se dice ordenado. Se dice que la raz del rbol A es padre de la raz de los subrboles A1 ,..., Am y que las raices de los subrboles A1 ,..., Am son hijos de la raz de A.

Un rbol binario A es un conjunto de elementos del mismo tipo tal que:O bien es el conjunto vaco, en cuyo caso se le denomina rbol vaco.O bien no es vaco, en cuyo caso existe un elemento distinguido llamado raz, y el resto de los elementos se distribuyen en dos subconjuntos disjuntos A1, A2, cada uno de los cuales es un rbol binario, llamados respectivamente subrboles izquierdo y derecho del rbol original.

5.1 Descripcin y terminologa fundamentalNo es lo mismo un rbol 2-ario que un rbol binario, ya que en el rbol binario se distingue entre sbrboles izquierdo y derecho. Los trminos padre e hijo descritos para rboles n-arios son tambin utilizados para rboles binarios. Otros trminos comunes son los siguientes:Camino: Si existe una secuencia de nodos nl ,..., nk tal que ni es padre de ni+1, para 1i k, entonces la secuencia se denomina camino del nodo nl al nodo nk. La longitud de un camino es el nmero de nodos del camino menos 1. Existe un camino de longitud 0 de todo nodo a s mismo.Ascendiente/Descendiente: Un nodo a es ascendiente de un nodo b (y b descendiente de a), si existe un camino del nodo a al nodo b. Por tanto todo nodo es ascendiente (y descendiente) de s mismo. Los ascendientes (y descendientes) de un nodo, excluido el propio nodo, se denominan ascendientes (y descendientes) propios.Hoja: Nodo sin descendientes propios. Altura: La altura de un nodo en un rbol es la longitud del camino ms largo de ese nodo a una hoja. La altura de un rbol es la altura de la raz.Profundidad: La profundidad de un nodo es la longitud del camino nico desde ese nodo a la raz.

5.2 Especificacin del TDA rbolEspecificacin informal del TDA Arbol

Arbol = TDA con operaciones crea,vacio, raiz,padre, hijoIzquierdo, hermanoDerecho,info, insertaHijo, insertaHermano, suprimeHijo, suprimeHermano, modifica, nodoNulo.

DESCRIPCIN:Los valores del TDA Arbol son arboles n-arios donde cada nodo contiene un dato del tipo Elemento. Las posiciones de los nodos en el rbol son del tipo Posicion. Los rboles son mutables: insertaHijo, insertaHermano, suprimeHijo, suprimeHermano y modifica aaden, eliminan y modifican respectivamente elementos de un rbol.OPERACIONES:crea() devuelve (A:Arbol)efecto: Devuelve el rbol vaco A.

5.2 Especificacin del TDA rbolvacio(A:Arbol) devuelve (booleano)efecto: Devuelve cierto si A es el rbol vaco, y falso en caso contrario.

raiz(A:Arbol) devuelve (Posicion)efecto: Devuelve la posicin del nodo raz en el rbol A. Si el rbol A est vaco, devuelve nulo.

padre(A:Arbol; P:Posicion) devuelve (Posicion)requerimientos: El rbol A es no vaco y P no es nodo nuloefecto: Devuelve la posicin del nodo padre del nodo P en el rbol A. Si P es la raiz devuelve nulo

hijoIzquierdo(A:Arbol; P:Posicion) devuelve (Posicion)requerimientos: El rbol A es no vaco y P no es nodo nulo.efecto: Devuelve la posicin del nodo hijo ms a la izquierda del nodo P en el rbol A. Si el nodo P no tiene hijos, devuelve nulo

5.2 Especificacin del TDA rbolhermanoDerecho(A:Arbol; P:Posicion) devuelve (Posicion)requerimientos: El rbol A es no vaco. P no es nodo nulo.efecto: Devuelve la posicin del nodo hermano derecho del nodo P en el rbol A. Si el nodo P no tiene hermano derecho, devuelve nulo

info(A:Arbol; P:Posicion) devuelve (E:Elemento)requerimientos: El rbol A es no vaco. P no es nodo nulo.efecto: Devuelve en E} el contenido del nodo P en el rbol A.insertaHijo(A:Arbol; P:Posicion; E:Elemento)requerimientos: Si el rbol A es no vaco, entonces P no es nodo nulo.modifica: A.efecto: Aade un nodo, con contenido E, como hijo ms a la izquierda del nodo P en el rbol A. Si el rbol A es vaco, entonces aade un nodo con contenido E como raz del rbol A.

5.2 Especificacin del TDA rbolinsertaHermano(A:Arbol; P:Posicion; E:Elemento)requerimientos: El rbol A es no vaco. P no es nodo nulo. P no es la raiz. modifica: A.efecto: Aade un nodo, con contenido E, como hermano derecho del nodo P en el rbol A.

suprimeHijo(A:Arbol; P:Posicion)requerimientos: El rbol A es no vaco. El nodo P no es nulo.modifica: A.efecto: Suprime el hijo ms a la izquierda del nodo P en el rbol A y todos sus descendientes.suprimeHermano(A:Arbol; P:Posicion)requerimientos: El rbol A es no vaco. El nodo P no es nulo.modifica: A.efecto: Suprime el hermano derecho del nodo P en el rbol A y todos sus descendientes.

5.2 Especificacin del TDA rbolmodifica(A:Arbol; P:Posicion; E:Elemento)requerimientos: El rbol A es no vaco. El nodo P no es nodo nulo.modifica: A.efecto: Modifica el contenido del nodo P en el rbol A, cambindolo por el nuevo contenido E.nodoNulo(P:Posicion) devuelve (booleano)efecto: Devuelve cierto si P es nulo, y falso en caso contrario.

5.2 Especificacin del TDA rbolLa interface Java del TDA rbol de acuerdo a esta especificacin, y sus excepciones, es la siguiente: package arbolInterface;import arbolException.*;public interface Arbol { public boolean vacio(); public Object raiz(); public Object padre(Object posicion) throws ArbolVacioException, NodoNuloException; public Object hijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException; public Object hermanoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException; public Object info(Object posicion) throws ArbolVacioException, NodoNuloException; public void insertaHijo(Object posicion, Object elemento) throws NodoNuloException; public void insertaHermano(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException, RaizException;

5.2 Especificacin del TDA rbol public void suprimeHijo(Object posicion) throws ArbolVacioException, NodoNuloException; public void suprimeHermano(Object posicion) throws ArbolVacioException, NodoNuloException; public void modifica(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException; public boolean nodoNulo(Object posicion);} // fin interface Arbol

package arbolException;public class ArbolException extends Exception { public ArbolException() { super(); }; public ArbolException(String s) { super(s); };}package arbolException;public class ArbolVacioException extends ArbolException { public ArbolVacioException() { super(); }; public ArbolVacioException(String s) { super(s); };}

5.2 Especificacin del TDA rbolpackage arbolException;public class NodoNuloException extends ArbolException { public NodoNuloException() { super(); }; public NodoNuloException(String s) { super(s); };}package arbolException;public class RaizException extends ArbolException { public RaizException() { super(); }; public RaizException(String s) { super(s); };}package arbolException;public class NodoNoNuloException extends ArbolException { public NodoNoNuloException() { super(); }; public NodoNoNuloException(String s) { super(s); }; }

5.3 Ejemplos de uso del TDA rbolVeremos en esta seccin algunos ejemplos de uso del TDA rbol. Uno de los aspectos fundamentales en rboles son los esquemas de recorrido. Aprovecharemos esta seccin para describir las distintas formas de recorrido en rboles haciendo uso de las operaciones del TDA, es decir, los procedimientos de recorrido se mostrarn como operaciones a un nivel de abstraccin mayor, y por tanto sern independientes de la implementacin del TDA.

Los tres esquemas fundamentales de recorrido en rboles se denominan:orden previo o preorden,orden simtrico o inorden, orden posterior o postorden.

Orden previo o PreordenSi el rbol es vaco, entonces la lista vaca es el listado de los nodos del rbol en preorden.Si el rbol no es vaco, el listado en preorden de sus nodos est formado, primero, por la raz del rbol, seguido por los nodos del primer subrbol en preorden, luego por los nodos del segundo subrbol en preorden, y as sucesivamente hasta los nodos del ltimo subrbol en preorden.

5.3 Ejemplos de uso del TDA rbolOrden simtrico o InordenSi el rbol es vaco, entonces la lista vaca es el listado de los nodos del rbol en inorden.Si el rbol no es vaco, el listado en inorden de sus nodos est formado, primero, por los nodos del primer subrbol en inorden, seguido por la raz del rbol, luego por los nodos del segundo subrbol en inorden, y as sucesivamente hasta los nodos del ltimo subrbol en inorden.

Orden posterior o PostordenSi el rbol es vaco, entonces la lista vaca es el listado de los nodos del rbol en postorden.Si el rbol no es vaco, el listado en postorden de sus nodos est formado, primero, por los nodos del primer subrbol en postorden, luego por los nodos del segundo subrbol en postorden, y as sucesivamente hasta los nodos del ltimo subrbol en postorden, y finalmente, por la raz del rbol.

5.3 Ejemplos de uso del TDA rbolimport arbolInterface.*;import arbolException.*;import java.io.*;class ArbolUtil { static public void preOrden(Arbol arbol, Object p) { try { if (arbol.nodoNulo(p)) return; Object e = arbol.info(p); System.out.println(e); Object q = arbol. hijoIzquierdo(p); while (!arbol.nodoNulo(q)) { preOrden(arbol, q); q = arbol. hermanoDerecho(q); } } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin preOrden

5.3 Ejemplos de uso del TDA rbol static public void inOrden(Arbol arbol, Object p) { try { if (arbol.nodoNulo(p)) return; Object q = arbol.hijoIzquierdo(p); inOrden(arbol,q); Object e = arbol.info(p); System.out.println(e); while (!arbol.nodoNulo(q)) { q = arbol. hermanoDerecho(q); inOrden(arbol,q); } } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin inOrden

5.3 Ejemplos de uso del TDA rbol static public void postOrden(Arbol arbol, Object p) { try { if (arbol.nodoNulo(p)) return; Object q = arbol.hijoIzquierdo(p); while (!arbol.nodoNulo(q)) { postOrden(arbol,q); q = arbol.hermanoDerecho(q); } Object e = arbol.info(p); System.out.println(e); } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin postOrden

} // fin class ArbolUtil

5.4 Implementaciones del TDA rbolLas clases Arbol y Posicion pueden escribirse bsicamente de la siguiente forma:class Posicion { protected Object info; protected Posicion hijoIzquierdo; protected Posicion padre; protected Posicion hermanoDerecho;} class Arbol { Posicion arbol;}

5.4 Implementaciones del TDA rbolpackage arbol;class Posicion { protected Object info; protected Posicion hijoIzquierdo; protected Posicion padre; protected Posicion hermanoDerecho; public boolean equals(Object o) { if (o==null) return false; Posicion p = (Posicion)o; return (this==p); }} // fin class Posicion

5.4 Implementaciones del TDA rbolpackage arbol;import arbolException.*;public class Arbol implements arbolInterface.Arbol { Posicion arbol; public Arbol() { arbol = null; } public boolean vacio() { return (nodoNulo(arbol)); } public Object raiz(){ return arbol; } public Object padre(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.padre; }

5.4 Implementaciones del TDA rbol public Object hijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.hijoIzquierdo; } public Object hermanoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.hermanoDerecho; } public Object info(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.info; }

5.4 Implementaciones del TDA rbol public void insertaHijo(Object posicion, Object elemento) throws NodoNuloException { Posicion p = (Posicion)posicion; if ((!vacio())&&(nodoNulo(p))) throw new NodoNuloException(); Posicion aux = new Posicion(); aux.info = elemento; aux.hijoIzquierdo = null; if (vacio()) { aux.padre = null; aux.hermanoDerecho = null; arbol = aux; } else { aux.padre = p; aux.hermanoDerecho = p.hijoIzquierdo; p.hijoIzquierdo = aux; } }

5.4 Implementaciones del TDA rbolpublic void insertaHermano(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException, RaizException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); if (p==raiz()) throw new RaizException(); Posicion aux = new Posicion(); aux.info = elemento; aux.hijoIzquierdo = null; aux.hermanoDerecho = p.hermanoDerecho; p.hermanoDerecho = aux; aux.padre = p.padre; }

5.4 Implementaciones del TDA rbol public void suprimeHijo(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); Posicion aux = (Posicion)hijoIzquierdo(p); if (!nodoNulo(aux)) { while(!nodoNulo(hijoIzquierdo(aux))) suprimeHijo(aux); p.hijoIzquierdo = aux.hermanoDerecho; } }

5.4 Implementaciones del TDA rbol public void suprimeHermano(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); Posicion aux = (Posicion)hermanoDerecho(p); if (!nodoNulo(aux)) { while(!nodoNulo(hijoIzquierdo(aux))) suprimeHijo(aux); p.hermanoDerecho = aux.hermanoDerecho; } }

5.4 Implementaciones del TDA rbol public void modifica(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); p.info = elemento; }

public boolean nodoNulo(Object posicion) { return (posicion==null); }

} // fin class Arbol

5.5 Especificacin del TDA rbol BinarioPara el TDA rbol Binario consideramos un conjunto de operaciones muy similar al que hemos descrito para el TDA rbol, con la diferencia de que las operaciones de posicionamiento, insercin y eliminacin van dirigidas hacia el hijo izquierdo y hacia el hijo derecho de un nodo dado, en lugar de hacia el hijo izquierdo y hacia el hermano como se definan en el TDA rbol. Es importante notar la diferencia entre rboles n-arios y rboles binarios, ya que son TDA's distintos. En el rbol binario, los subrboles se contituyen desde su creacin como subrboles izquierdos o derechos mientras que en un rbol, un subrbol puede ser creado como subrbol de ms la izquierda y despus dejar de serlo.

5.5 Especificacin del TDA rbol BinarioEspecificacin informal del TDA rbol BinarioArbolBinario = TDA con operaciones crea,vacio, raiz, padre, hijoIzquierdo, hijoDerecho,info, insertaIzquierdo, insertaDerecho, suprimeIzquierdo, suprimeDerecho, modifica, nodoNulo.DESCRIPCIN:Los valores del TDA ArbolBinario son arboles binarios donde cada nodo contiene un dato del tipo Elemento. Las posiciones de los nodos en el rbol son del tipo Posicion. Los rboles son mutables: insertaIzquierdo, insertaDerecho, suprimeIzqquierdo, suprimeDerecho} y modifica aaden, eliminan y modifican respectivamente elementos de un rbol.OPERACIONES:crea() devuelve (A:ArbolBinario)efecto: Devuelve el rbol vaco A.

5.5 Especificacin del TDA rbol Binariovacio(A:ArbolBinario) devuelve (booleano)efecto: Devuelve cierto si A es el rbol vaco, y falso en caso contrario.raiz(A:ArbolBinario) devuelve (Posicion)efecto: Devuelve la posicin del nodo raz en el rbol A. Si el rbol A est vaco, devuelve nulo padre(A:ArbolBinario; P:Posicion) devuelve (Posicion)requerimientos: El rbol A es no vaco. El nodo P es no nulo. efecto: Devuelve la posicin del nodo padre del nodo P en el rbol A. Si P es la raiz, devuelve nulo.

hijoIzquierdo(A:ArbolBinario; P:Posicion) devuelve (Posicion)}requerimientos: El rbol A es no vaco. El nodo P es no nulo.efecto: Devuelve la posicin del nodo hijo izquierdo del nodo P en el rbol A. Si el nodo P no tiene hijo izquierdo, devuelve nulo.

5.5 Especificacin del TDA rbol BinariohijoDerecho(A:ArbolBinario; P:Posicion) devuelve (Posicion)requerimientos: El rbol A es no vaco. El nodo P es no nulo.efecto: Devuelve la posicin del nodo hijo derecho del nodo P en el rbol A. Si el nodo P no tiene hijo derecho, devuelve nuloinfo(A:ArbolBinario; P:Posicion) devuelve (E:Elemento)requerimientos: El rbol A es no vaco. El nodo P es no nulo.efecto: Devuelve en E el contenido (etiqueta) del nodo P en el rbol A.insertaIzquierdo(A:ArbolBinario; P:Posicion; E:Elemento)requerimientos: Si el rbol A es no vaco, entonces el nodo P es no nulo y el nodo hijo izquierdo de P es nulomodifica: A.efecto: Aade un nodo, con contenido E, como hijo izquierdo del nodo P en el rbol A. Si el rbol A es vaco, entonces aade un nodo con contenido E como raz del rbol A.

5.5 Especificacin del TDA rbol BinarioinsertaDerecho(A:ArbolBinario; P:Posicion; E:Elemento)requerimientos: El rbol A es no vaco. El nodo P es no nulo. El nodo hijo derecho de P es nulomodifica: A.efecto: Aade un nodo, con contenido E, como hijo derecho del nodo P en el rbol A.

suprimeIzquierdo(A:ArbolBinario; P:Posicion)requerimientos: El rbol A es no vaco. El nodo P es no nulo.modifica: A.efecto: Suprime el hijo izquierdo del nodo P en el rbol A y todos sus descendientes.

suprimeDerecho(A:ArbolBinario; P:Posicion)requerimientos: El rbol A es no vaco. El nodo P es no nulo.modifica: A.efecto: Suprime el hijo derecho del nodo P en el rbol A y todos sus descendientes.

5.5 Especificacin del TDA rbol Binariomodifica(A:ArbolBinario; P:Posicion; E:Elemento)requerimientos: El rbol A es no vaco. El nodo P es no nulo.modifica: A.efecto: Modifica el contenido del nodo P en el rbol A, cambindolo por el nuevo contenido E.nodoNulo(P:Posicion) devuelve (booleano)efecto: Devuelve cierto si P es nulo, y falso en caso contrario.

5.5 Especificacin del TDA rbol BinarioLa interface Java del TDA rbol de acuerdo a esta especificacin es la siguiente (las excepciones utilizadas son las mismas que las del TDA rbol):

package arbolBinarioInterface;import arbolException.*;public interface ArbolBinario {public boolean vacio(); public Object raiz(); public Object padre(Object posicion) throws ArbolVacioException, NodoNuloException; public Object hijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException; public Object hijoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException; public Object info(Object posicion) throws ArbolVacioException, NodoNuloException;

5.5 Especificacin del TDA rbol Binariopublic void insertaHijoIzquierdo(Object posicion, Object elemento) throws NodoNuloException, NodoNoNuloException; public void insertaHijoDerecho(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException, NodoNoNuloException;public void suprimeHijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException;public void suprimeHijoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException;public void modifica(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException;public boolean nodoNulo(Object posicion);

} // fin class ArbolBinario

5.6 Ejemplos de uso del TDA rbol BinarioComo ejemplos de uso de rboles binarios veremos tambin los esquemas de recorrido para estos, los cuales difieren con respecto a los recorridos para rboles generales ya que ambos tipos de datos y sus conjuntos de opraciones son diferentes. Para rboles binarios, se definen los recorridos en preorden, inorden y postorden de la siguiente forma:

Preorden:Si el rbol binario es vaco, entonces la lista vaca es el listado de los nodos del rbol binario en preorden.Si el rbol binario no es vaco, el listado en preorden de sus nodos est formado, primero, por la raz del rbol, seguido por los nodos del subrbol izquierdo en preorden, y finalmente, por los nodos del subrbol derecho en preorden.

5.6 Ejemplos de uso del TDA rbol BinarioInorden:Si el rbol binario es vaco, entonces la lista vaca es el listado de los nodos del rbol binario en inorden.Si el rbol binario no es vaco, el listado en inorden de sus nodos est formado, primero, por los nodos del subrbol izquierdo en inorden, seguido por la raz del rbol, y finalmente, por los nodos del subrbol derecho en inorden.

Postorden:Si el rbol binario es vaco, entonces la lista vaca es el listado de los nodos del rbol binario en postorden.Si el rbol binario no es vaco, el listado en postorden de sus nodos est formado, primero, por los nodos del subrbol izquierdo en postorden, luego por los nodos del subrbol derecho en postorden, y finalmente, por la raz del rbol.

5.6 Ejemplos de uso del TDA rbol Binarioimport arbolBinarioInterface.*;import arbolException.*;import java.io.*;

class ArbolBinarioUtil {

static public void preOrden(ArbolBinario arbol, Object p) { try { if (arbol.nodoNulo(p)) return; Object e = arbol.info(p); System.out.println(e); preOrden(arbol,arbol.hijoIzquierdo(p)); preOrden(arbol,arbol.hijoDerecho(p)); } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin preOrden

5.6 Ejemplos de uso del TDA rbol Binario static public void inOrden(ArbolBinario arbol, Object p) { try { if (arbol.nodoNulo(p)) return; inOrden(arbol,arbol.hijoIzquierdo(p)); Object e = arbol.info(p); System.out.println(e); inOrden(arbol,arbol.hijoDerecho(p)); } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin inOrden

5.6 Ejemplos de uso del TDA rbol Binario static public void postOrden(ArbolBinario arbol, Object p) { try { if (arbol.nodoNulo(p)) return; postOrden(arbol,arbol.hijoIzquierdo(p)); postOrden(arbol,arbol.hijoDerecho(p)); Object e = arbol.info(p); System.out.println(e); } catch (ArbolException e) { System.err.println("Error en el uso del Arbol: e"); } } // fin postOrden

} // fin class ArbolBinarioUtil

5.7 Implementaciones del TDA rbol BinarioLas clases ArbolBinario y Posicion pueden escribirse bsicamente de la siguiente forma:class Posicion { protected Object info; protected Posicion hijoIzquierdo; protected Posicion padre; protected Posicion hijoDerecho;}

class ArbolBinario { Posicion arbol;}

5.7 Implementaciones del TDA rbol Binariopackage arbolBinario;

class Posicion { protected Object info; protected Posicion hijoIzquierdo; protected Posicion padre; protected Posicion hijoDerecho; public boolean equals(Object o) { if (o==null) return false; Posicion p = (Posicion)o; return (this==p); }} // fin class Posicion

5.7 Implementaciones del TDA rbol Binariopackage arbolBinario;import arbolException.*;public class ArbolBinario implements arbolBinarioInterface.ArbolBinario{ Posicion arbol; public ArbolBinario() { arbol = null; } public boolean vacio() { return (nodoNulo(arbol)); } public Object raiz(){ return arbol; } public Object padre(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.padre; }

5.7 Implementaciones del TDA rbol Binario public Object hijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.hijoIzquierdo; } public Object hijoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.hijoDerecho; } public Object info(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); return p.info; }

5.7 Implementaciones del TDA rbol Binario public void insertaHijoIzquierdo(Object posicion, Object elemento) throws NodoNuloException, NodoNoNuloException { Posicion p = (Posicion)posicion; if (!vacio()) { if (nodoNulo(p)) throw new NodoNuloException();if (!nodoNulo(hijoIzquierdo(p))) throw new NodoNoNuloException();} Posicion aux = new Posicion(); aux.info = elemento; aux.hijoIzquierdo = null; aux.hijoDerecho = null; if (vacio()) { aux.padre = null; arbol = aux; } else { aux.padre = p; p.hijoIzquierdo = aux; } }

5.7 Implementaciones del TDA rbol Binario public void insertaHijoDerecho(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException, NodoNoNuloException { Posicion p = (Posicion)posicion; if (vacio()) throw new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); if (!nodoNulo(hijoDerecho(p))) throw new NodoNoNuloException(); Posicion aux = new Posicion(); aux.info = elemento; aux.hijoIzquierdo = null; aux.hijoDerecho = null; aux.padre = p; p.hijoDerecho = aux; }

5.7 Implementaciones del TDA rbol Binario public void suprimeHijoIzquierdo(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); Posicion aux = (Posicion)hijoIzquierdo(p); if (!nodoNulo(aux)) { suprimeHijoIzquierdo(aux); suprimeHijoDerecho(aux); p.hijoIzquierdo = null; } }

5.7 Implementaciones del TDA rbol Binario public void suprimeHijoDerecho(Object posicion) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); Posicion aux = (Posicion)hijoDerecho(p); if (!nodoNulo(aux)) { suprimeHijoIzquierdo(aux); suprimeHijoDerecho(aux); p.hijoDerecho = null; } }

5.7 Implementaciones del TDA rbol Binario public void modifica(Object posicion, Object elemento) throws ArbolVacioException, NodoNuloException { Posicion p = (Posicion)posicion; if (vacio()) new ArbolVacioException(); if (nodoNulo(p)) throw new NodoNuloException(); p.info = elemento; }

public boolean nodoNulo(Object posicion) { return (posicion==null); }

} // fin class ArbolBinario

5.8 rboles Parcialmente Ordenados: Colas de prioridadEn un captulo anterior vimos una implementacin de colas de prioridad mediante estructuras de datos lineales, en concreto, mediante representacin enlazada con apuntadores. En esa implementacin, la operacin inserta gastaba un tiempo de ejecucin O(n) en el peor caso, si bien la operacin suprime se realiza en un tiempo de ejecucin constante O(1). La implementacin que veremos en esta seccin para colas de prioridad requiere un tiempo de ejecucin O(logn) para ambas operaciones, lo que supone una mejora sustancial para valores grandes de n.

5.8 rboles Parcialmente Ordenados: Colas de prioridadEn esta implementacin, los elementos de la cola de prioridad se organizan en un rbol binario que est lo ms balanceado posible. En el nivel ms bajo, en el cual pueden faltar algunas nodos (lo cual no puede producirse en niveles superiores), se exige adems que los nodos que falten sean los de ms a la derecha posible. El rbol binario es parcialmente ordenado, es decir, la prioridad de un nodo no es menor que la de sus hijos, por lo que en la raz estar siempre el elemento con mayor prioridad

5.8 rboles Parcialmente Ordenados: Colas de prioridadrbol binario parcialmente ordenado balanceado

5.8 rboles Parcialmente Ordenados: Colas de prioridadPodemos usar como representacin un vector A en el cual:si hay n nodos en el rbol, se usan las n primeras posiciones del vector, A[1] contiene el elemento situado en la raz del arbol, el hijo izquierdo del nodo A[i] est, si existe, est en A[2i], el hijo derecho de A[i] est, si existe, est en A[2i+1]el padre del elemento representado en A[i] est en A[idiv2], para i>1.Esta representacin de rboles parcialmente ordenados se denomina comnmente representacin por montculos. La ventaja est en que se aprovecha la posibilidad de operar aritmticamente con los ndices del vector para obtener, con tiempos de ejecucin constantes, las posiciones de los padres e hijos izquierdo y derecho. La desventaja es que se requiere determinar a priori el nmero mximo de elementos en el rbol.

5.8 rboles Parcialmente Ordenados: Colas de prioridadLa interface del TDA Cola de Prioridad se corresponde con el que presentamos en el captulo de colas para colas de prioridad. No obstante, la especificacin del TDA Cola de Prioridad que estamos considerando en esta seccin es diferente a la que consideramos anteriormente. La diferencia radica en que ahora no se tiene en cuenta la propiedad FIFO para elementos de igual prioridad. Por tanto, no suponemos ahora ningn orden en el procesamiento de dos elementos con igual prioridad (si queremos imponer un orden ser necesario dar mayor prioridad a uno de ellos)

5.8 rboles Parcialmente Ordenados: Colas de prioridadLa implementacin completa en Java es la siguiente:package colaPrioridadBasadaArbol;import colaException.*;

public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {

private static int max = 100; private Object elementos[]; private int prioridades[]; private int ultimo;

public ColaPrioridad() { elementos = new Object[max+1]; prioridades = new int[max+1]; ultimo = 0; }

5.8 rboles Parcialmente Ordenados: Colas de prioridad public boolean vacia() { return (ultimo==0); }

public Object primero() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); return elementos[1]; }

public int primero_prioridad() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); return prioridades[1]; }

5.8 rboles Parcialmente Ordenados: Colas de prioridad public void inserta(Object elemento, int prioridad) { ultimo++; int i = ultimo; boolean encontrado = false; while((i>1)&&(!encontrado)) { int padre = i/2; if (prioridad

5.8 rboles Parcialmente Ordenados: Colas de prioridad public void suprime() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); Object elemento = elementos[ultimo]; int prioridad = prioridades[ultimo]; ultimo--; int i=1; int j=2*i; boolean encontrado=false; while((j

5.9 rboles Binarios de BsquedaUn rbol binario de bsqueda es un rbol binario formado por elementos en los cuales se asume un orden lineal, y stos se organizan en el rbol de la forma: todos los elementos almacenados en el subrbol izquierdo de cualquier nodo son menores que el elemento almacenado en dicho nodotodos los elementos almacenados en el subrbol derecho de cualquier nodo son mayores que el elemento almacenado en ese nodo Los rboles binarios de bsqueda se utilizan tpicamente como estructura de datos para la representacin de conjuntos con operaciones:inserta, para insertar un elemento dado en un conjuntosuprime, para suprimir un elemento determinado de un conjuntomiembro, para saber si un elemento dado pertenece o no a un conjunto.Todas estas operaciones pueden realizarse en un tiempo de ejecucin promedio O(logn) para un conjunto de n elementos.

5.9 rboles Binarios de BsquedaOtras posibles operaciones que puede realizarsecon el mismo tiempo de ejecucin promedio usando rboles binarios de bsqueda son:min, que devuelve el elemento mnimo de un rbol suprime_min, que elimina el elemento mnimo de un rbol max, que devuelve el elemento mximo de un rbol suprime_max, que elimina el elemento mximo de un rbolPodramos usar tambin rboles binarios de bsqueda para representar colas de prioridad (en este caso permitiramos almacenar elementos repetidos en el rbol, asumiendo, por ejemplo, que los elementos almacenados en el subrbol derecho de cualquier nodo son mayores o iguales que el elemento almacenado en ese nodo).

5.9 rboles Binarios de BsquedaEspecificacin Informal

ArbolBinarioBusqueda = TDA con operaciones crea, destruye, vacio, inserta, suprime, miembro.

DESCRIPCIN:Los valores del TDA ArbolBinarioBusqueda son rboles binarios de bsqueda de elementos del tipo Elemento. Los rboles binarios de bsqueda son mutables: inserta} y suprime aaden yeliminan elementos en el rbol respectivamente.

OPERACIONES:crea() devuelve (A:ArbolBinarioBusqueda)efecto: Devuelve el rbol binario de bsqueda vaco A.

5.9 rboles Binarios de Bsquedavacio(A:ArbolBinarioBusqueda) devuelve (booleano)efecto: Devuelve cierto si A es el rbol vaco, y falso en caso contrario.inserta(A:ArbolBinarioBusqueda; E:Elemento)modifica: A.efecto: Aade el elemento E al rbol binario de bsqueda A.

suprime(A:ArbolBinarioBusqueda; E:Elemento)modifica: A.efecto: Suprime el elemento E, si existe, del rbol binario de bsqueda A.

miembro(A:ArbolBinarioBusqueda; E:Elemento) devuelve (booleano)efecto: Devuelve cierto si E es un elemento del rbol binario de bsqueda A, y falso en caso contrario.

5.9 rboles Binarios de BsquedaLa interface en Java del TDA rbol Binario de Bsqueda es la siguiente:package arbolBinarioBusquedaInterface;import Comparable;public interface ArbolBinarioBusqueda { public boolean vacio(); public void inserta(Comparable elemento); public void suprime(Comparable elemento); public boolean miembro(Comparable elemento);} // fin interface ArbolBinarioBusquedaLos elementos deben implementar la interface Comparable porque as lo requiere el TDA rbol Binario de Bsqueda al asumirse un rden lineal entre sus elementos.

5.9 rboles Binarios de BsquedaLa interface en Java del TDA rbol Binario de Bsqueda es la siguiente:package arbolBinarioBusquedaInterface;import Comparable;public interface ArbolBinarioBusqueda { public boolean vacio(); public void inserta(Comparable elemento); public void suprime(Comparable elemento); public boolean miembro(Comparable elemento);} // fin interface ArbolBinarioBusquedaLos elementos deben implementar la interface Comparable porque as lo requiere el TDA rbol Binario de Bsqueda al asumirse un rden lineal entre sus elementos.

5.9 rboles Binarios de Bsquedapackage arbolBinarioBusqueda;import Comparable;

public class ArbolBinarioBusqueda implements arbolBinarioBusquedaInterface.ArbolBinarioBusqueda {

private Comparable info; private ArbolBinarioBusqueda izquierdo, derecho;

public ArbolBinarioBusqueda() { info = null; izquierdo = null; derecho = null; } public boolean vacio() { return ((info==null)&&(izquierdo==null)&&(derecho==null)); }

5.9 rboles Binarios de Bsqueda public void inserta(Comparable elemento) { if (vacio()) { info = elemento; izquierdo = new ArbolBinarioBusqueda(); derecho = new ArbolBinarioBusqueda(); } else if (elemento.menorQue(info)) { izquierdo.inserta(elemento); } else { derecho.inserta(elemento); } }

5.9 rboles Binarios de Bsqueda public void suprime(Comparable elemento) { if (vacio()) return; if (elemento.menorQue(info)) { izquierdo.suprime(elemento); } else if (elemento.mayorQue(info)) { derecho.suprime(elemento); } else if ((izquierdo.vacio())&&(derecho.vacio())) { info = null; derecho = null; izquierdo = null; } else if (izquierdo.vacio()) { info = derecho.info; izquierdo = derecho.izquierdo; derecho = derecho.derecho; }

5.9 rboles Binarios de Bsqueda else if (derecho.vacio()) { info = izquierdo.info; derecho = izquierdo.derecho; izquierdo = izquierdo.izquierdo; } else { ArbolBinarioBusqueda min = derecho; while (!min.izquierdo.vacio()) min = min.izquierdo; info = min.info; min.info = min.derecho.info; min.izquierdo = min.derecho.izquierdo; min.derecho = min.derecho.derecho; } }

5.9 rboles Binarios de Bsqueda public boolean miembro(Comparable elemento) { if (vacio()) return false; if (elemento.equals(info)) return true; if (elemento.menorQue(info)) return izquierdo.miembro(elemento); return derecho.miembro(elemento); }

} // fin class ArbolBinarioBusqueda

*