uoc.ei.tads
Class ArbolAVL<E>

java.lang.Object
  extended by uoc.ei.tads.ArbolAbstracto<E>
      extended by uoc.ei.tads.ArbolBinario<E>
          extended by uoc.ei.tads.ArbolBinarioEncadenadoImpl<E>
              extended by uoc.ei.tads.ArbolAVL<E>
All Implemented Interfaces:
java.io.Serializable, Arbol<E>, Contenedor<E>

public class ArbolAVL<E>
extends ArbolBinarioEncadenadoImpl<E>

Clase que implementa un arbol binario de busqueda equilibrado AVL (Adelson- Velskii & Landis), el cual se caracteriza para tener la raíz más grande que todos los elementos de su subárbol izquierdo (si tiene) y más pequeña que todos los elementos de su subárbol derecho (si tiene); y, además, sus subárboles izquierdo y derecho (si hay) son también árboles de busqueda. Se dice que el arbol está equilibrado (height balanced) cuando el valor absoluto de la diferencia de alturas de sus subárboles es menor o igual que uno y sus subárboles también están equilibrados. Se espera que las clases de los elementos implementen java.lang.Comparable o bien que se facilite un java.util.Comparator como parámetro del constructor.

See Also:
Serialized Form

Nested Class Summary
protected static class ArbolAVL.NodoAVL<EN>
          Clase que extiende NodoArbol para incorporar un atributo de altura que permite comprobar y mantener el equilibrio de un arbol de nodos AVL.
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbolBinarioEncadenadoImpl
ArbolBinarioEncadenadoImpl.NodoArbol<EN>
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbolBinario
ArbolBinario.RecorridoHijos<E>, ArbolBinario.RecorridoInorden<E>, ArbolBinario.RecorridoOrdenBasico<E>, ArbolBinario.RecorridoPorNiveles<E>, ArbolBinario.RecorridoPostorden<E>, ArbolBinario.RecorridoPreorden<E>
 
Field Summary
protected  java.util.Comparator<E> comparador
          Comparador concreto que permite deducir la prioridad entre los elementos.
 
Fields inherited from class uoc.ei.tads.ArbolBinarioEncadenadoImpl
root
 
Constructor Summary
ArbolAVL()
          Constructor sin parámetros.
ArbolAVL(java.util.Comparator<E> comparador)
          Constructor con un parámetro y elementos de una clase comparable con el comparador dado.
 
Method Summary
 E borrar(E elemComp)
          Borra el elemento, si lo encuentra de acuerdo con el comparador.
protected  int comparar(E elem1, E elem2)
          Método protegido que compara los elementos recibos.
 E consultar(E elemComp)
          Accesor de lectura de un elemento del arbol.
protected  ArbolBinarioEncadenadoImpl.NodoArbol<E> crearNodo(Posicion<E> padre, E elemComp)
          Sobrescribe el método de la superclase para incorporar el atributo de altura al nodo, que permite comprobar el equilibrio del arbol AVL.
protected  void equilibrar(Posicion<E> nodo)
          Método que restaura, si es preciso, el equilibrio del arbol de nodos después de cada inserción o supresión.
 boolean hayComparador()
          Método para saber si hay un comparador específico.
 void insertar(E elemComp)
          Añade un elemento a la posición que le corresponde, si se puede.
 
Methods inherited from class uoc.ei.tads.ArbolBinarioEncadenadoImpl
borrar, estaVacio, hijoDerecho, hijoIzquierdo, insertar, insertarHijoDerecho, insertarHijoIzquierdo, intercambiar, numElems, raiz, reemplazar, reemplazarSubarbol
 
Methods inherited from class uoc.ei.tads.ArbolBinario
elementos, esHoja, hijos, posiciones, recorridoInorden, recorridoPostorden, recorridoPreorden, toString
 
Methods inherited from class uoc.ei.tads.ArbolAbstracto
numElems, numHijos, recorridoPorNiveles, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

comparador

protected java.util.Comparator<E> comparador
Comparador concreto que permite deducir la prioridad entre los elementos. Puede tener valor null y entonces se utiliza la interfaz java.lang.Comparable

Constructor Detail

ArbolAVL

public ArbolAVL()
Constructor sin parámetros. Se espera que las clases de los elementos implementen la interfaz java.lang.Comparable.


ArbolAVL

public ArbolAVL(java.util.Comparator<E> comparador)
Constructor con un parámetro y elementos de una clase comparable con el comparador dado.

Parameters:
comparador - comparador que permite deducir la prioridad
Throws:
ExcepcionParametroIncorrecto - si el comparador es null
Method Detail

equilibrar

protected void equilibrar(Posicion<E> nodo)
Método que restaura, si es preciso, el equilibrio del arbol de nodos después de cada inserción o supresión. Se espera un NodoAVL no null.

Parameters:
nodo - arbol o subárbol de nodos que se debe equilibrar

crearNodo

protected ArbolBinarioEncadenadoImpl.NodoArbol<E> crearNodo(Posicion<E> padre,
                                                            E elemComp)
Sobrescribe el método de la superclase para incorporar el atributo de altura al nodo, que permite comprobar el equilibrio del arbol AVL.

Overrides:
crearNodo in class ArbolBinarioEncadenadoImpl<E>
Parameters:
padre - padre del nuevo nodo
elemComp - elemento comparable que se quiere guardar al nodo
Returns:
nodo arbol binario nuevo que almacena el elemento e incorpora la altura por defecto uno (hoja)

insertar

public void insertar(E elemComp)
Añade un elemento a la posición que le corresponde, si se puede. Si el elemento ya existía, de acuerdo con el comparador, lo sobrescribe.

Parameters:
elemComp - elemento comparable que se quiere añadir al arbol
Throws:
ExcepcionElementosNoComparables - si el elemento es no comparable

borrar

public E borrar(E elemComp)
Borra el elemento, si lo encuentra de acuerdo con el comparador.

Parameters:
elemComp - elemento comparable que se quiere suprimir del arbol
Returns:
el elemento borrado; o null, si no existia
Throws:
ExcepcionContenedorVacio - si el arbol está vacío
ExcepcionElementosNoComparables - si el elemento es no comparable

consultar

public E consultar(E elemComp)
Accesor de lectura de un elemento del arbol. Si no lo encuentra, de acuerdo con el comparador, retorna null.

Parameters:
elemComp - elemento comparable que se quiere consultar
Returns:
el elemento interesado; o null, si no existía
Throws:
ExcepcionContenedorVacio - si el arbol está vacío
ExcepcionElementosNoComparables - si el elemento es no comparable

hayComparador

public boolean hayComparador()
Método para saber si hay un comparador específico. Si no se utiliza la operación de comparación de java.lang.Comparable.

Returns:
cierto o falso, según si hay o no hay un comparador específico asignado

comparar

protected int comparar(E elem1,
                       E elem2)
                throws ExcepcionElementosNoComparables
Método protegido que compara los elementos recibos. Si en la clase principal hay definido un comparador, el método delega en el método java.útil.Comparator.compadre(o1, o2); sino delega en el método java.lang.Comparable.compareTo(o) implementado por la clase del elemento.

Parameters:
elem1 - primer objeto de la misma clase
elem2 - segundo objeto de la misma clase
Returns:
un entero negativo, cero o positivo, según si el primer elemento tiene menos, igual o más prioridad que el segundo elemento, de acuerdo con la implementación del comparador
Throws:
ExcepcionElementosNoComparables - si algún elemento es no comparable