|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbolAbstracto<E>
uoc.ei.tads.ArbolBinario<E>
uoc.ei.tads.ArbolBinarioEncadenadoImpl<E>
uoc.ei.tads.ArbolAVL<E>
public class ArbolAVL<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.
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 |
---|
protected java.util.Comparator<E> comparador
Constructor Detail |
---|
public ArbolAVL()
public ArbolAVL(java.util.Comparator<E> comparador)
comparador
- comparador que permite deducir la prioridad
ExcepcionParametroIncorrecto
- si el comparador es nullMethod Detail |
---|
protected void equilibrar(Posicion<E> nodo)
nodo
- arbol o subárbol de nodos que se debe equilibrarprotected ArbolBinarioEncadenadoImpl.NodoArbol<E> crearNodo(Posicion<E> padre, E elemComp)
crearNodo
in class ArbolBinarioEncadenadoImpl<E>
padre
- padre del nuevo nodoelemComp
- elemento comparable que se quiere guardar al nodo
public void insertar(E elemComp)
elemComp
- elemento comparable que se quiere añadir al arbol
ExcepcionElementosNoComparables
- si el elemento es no
comparablepublic E borrar(E elemComp)
elemComp
- elemento comparable que se quiere suprimir del arbol
ExcepcionContenedorVacio
- si el arbol está vacío
ExcepcionElementosNoComparables
- si el elemento es no
comparablepublic E consultar(E elemComp)
elemComp
- elemento comparable que se quiere consultar
ExcepcionContenedorVacio
- si el arbol está vacío
ExcepcionElementosNoComparables
- si el elemento es no
comparablepublic boolean hayComparador()
protected int comparar(E elem1, E elem2) throws ExcepcionElementosNoComparables
elem1
- primer objeto de la misma claseelem2
- segundo objeto de la misma clase
ExcepcionElementosNoComparables
- si algún elemento es no
comparable
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |