uoc.ei.tads
Class ArbreAVL<E>

java.lang.Object
  extended by uoc.ei.tads.ArbreAbstracte<E>
      extended by uoc.ei.tads.ArbreBinari<E>
          extended by uoc.ei.tads.ArbreBinariEncadenatImpl<E>
              extended by uoc.ei.tads.ArbreAVL<E>
All Implemented Interfaces:
java.io.Serializable, Arbre<E>, Contenidor<E>

public class ArbreAVL<E>
extends ArbreBinariEncadenatImpl<E>

Classe que implementa un arbre binari de cerca equilibrat AVL (Adelson- Velskii & Landis), el qual es caracteritza per tenir l'arrel més gran que tots els elements del seu subarbre esquerre (si en té) i més petita que tots els elements del seu subarbre dret (si en té); i, a més, els seus subarbres esquerre i dret (si n'hi ha) són també arbres de cerca. Es diu que l'arbre està equilibrat (height balanced) quan el valor absolut de la diferència d'altures dels seus subarbres és menor o igual que u i els seus subarbres també estan equilibrats. S'espera que les classes dels elements implementin java.lang.Comparable o bé que es faciliti un java.util.Comparator com a paràmetre del constructor.

Since:
1.5
See Also:
Serialized Form

Nested Class Summary
protected static class ArbreAVL.NodeAVL<EN>
          Classe que estén NodeArbre per a incorporar un atribut d'altura que permet comprovar i mantenir l'equilibri d'un arbre de nodes AVL.
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreBinariEncadenatImpl
ArbreBinariEncadenatImpl.NodeArbre<EN>
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreBinari
ArbreBinari.RecorregutFills<E>, ArbreBinari.RecorregutInordre<E>, ArbreBinari.RecorregutOrdreBasic<E>, ArbreBinari.RecorregutPerNivell<E>, ArbreBinari.RecorregutPostordre<E>, ArbreBinari.RecorregutPreordre<E>
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreAbstracte
ArbreAbstracte.RecorregutPerNivells<E>
 
Field Summary
protected  java.util.Comparator<E> comparador
          Comparador concret que permet deduir la prioritat entre els elements.
 
Fields inherited from class uoc.ei.tads.ArbreBinariEncadenatImpl
root
 
Constructor Summary
ArbreAVL()
          Constructor sense paràmetres.
ArbreAVL(java.util.Comparator<E> comparador)
          Constructor amb un paràmetre i elements d'una classe comparable amb el comparador donat.
 
Method Summary
 void afegir(E elemComp)
          Afegeix un element a la posició que li correspon, si es pot.
protected  int comparar(E elem1, E elem2)
          Mètode protegit que compara els elements rebuts.
 E consultar(E elemComp)
          Accessor de lectura d'un element de l'arbre.
protected  ArbreBinariEncadenatImpl.NodeArbre<E> crearNode(Posicio<E> pare, E elemComp)
          Sobreescriu el mètode de la superclasse per a incorporar l'atribut d'altura al node, que permet comprovar l'equilibri de l'arbre AVL.
protected  void equilibrar(Posicio<E> node)
          Mètode que restaura, si cal, l'equilibri de l'arbre de nodes després de cada inserció o supressió.
 E esborrar(E elemComp)
          Esborra l'element, si el troba d'acord amb el comparador.
 boolean hiHaComparador()
          Mètode per a saber si hi ha un comparador específic.
 
Methods inherited from class uoc.ei.tads.ArbreBinariEncadenatImpl
afegir, afegirFillDret, afegirFillEsquerre, arrel, esborrar, estaBuit, fillDret, fillEsquerre, intercanviar, nombreElems, reemplacar, reemplacarSubarbre
 
Methods inherited from class uoc.ei.tads.ArbreBinari
elements, esFulla, fills, posicions, recorregutInordre, recorregutPostordre, recorregutPreordre, toString
 
Methods inherited from class uoc.ei.tads.ArbreAbstracte
nombreElems, nombreFills, recorregutPerNivells, 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 concret que permet deduir la prioritat entre els elements. Pot tenir valor null i aleshores s'utilitza la interfície java.lang.Comparable

Constructor Detail

ArbreAVL

public ArbreAVL()
Constructor sense paràmetres. S'espera que les classes dels elements implementin la interfície java.lang.Comparable.


ArbreAVL

public ArbreAVL(java.util.Comparator<E> comparador)
Constructor amb un paràmetre i elements d'una classe comparable amb el comparador donat.

Parameters:
comparador - comparador que permet deduir la prioritat
Throws:
ExcepcioParametreIncorrecte - si el comparador és null
Method Detail

equilibrar

protected void equilibrar(Posicio<E> node)
Mètode que restaura, si cal, l'equilibri de l'arbre de nodes després de cada inserció o supressió. S'espera un NodeAVL no null.

Parameters:
node - arbre o subarbre de nodes que s'ha d'equilibrar

crearNode

protected ArbreBinariEncadenatImpl.NodeArbre<E> crearNode(Posicio<E> pare,
                                                          E elemComp)
Sobreescriu el mètode de la superclasse per a incorporar l'atribut d'altura al node, que permet comprovar l'equilibri de l'arbre AVL.

Overrides:
crearNode in class ArbreBinariEncadenatImpl<E>
Parameters:
pare - pare del nou node
elemComp - element comparable que es vol desar al node
Returns:
node arbre binari nou que emmagatzema l'element i incorpora l'altura per defecte u (fulla)

afegir

public void afegir(E elemComp)
Afegeix un element a la posició que li correspon, si es pot. Si l'element ja hi era, d'acord amb el comparador, el sobreescriu.

Parameters:
elemComp - element comparable que es vol afegir a l'arbre
Throws:
ExcepcioElementsNoComparables - si l'element és no comparable

esborrar

public E esborrar(E elemComp)
Esborra l'element, si el troba d'acord amb el comparador.

Parameters:
elemComp - element comparable que es vol suprimir de l'arbre
Returns:
l'element esborrat; o null, si no hi era
Throws:
ExcepcioContenidorBuit - si l'arbre està buit
ExcepcioElementsNoComparables - si l'element és no comparable

consultar

public E consultar(E elemComp)
Accessor de lectura d'un element de l'arbre. Si no el troba, d'acord amb el comparador, retorna null.

Parameters:
elemComp - element comparable que es vol consultar
Returns:
l'element interessat; o null, si no hi era
Throws:
ExcepcioContenidorBuit - si l'arbre està buit
ExcepcioElementsNoComparables - si l'element és no comparable

hiHaComparador

public boolean hiHaComparador()
Mètode per a saber si hi ha un comparador específic. Si no hi és s'utilitza l'operació de comparació de java.lang.Comparable.

Returns:
cert o fals, segons si hi ha o no hi ha un comparador específic assignat

comparar

protected int comparar(E elem1,
                       E elem2)
                throws ExcepcioElementsNoComparables
Mètode protegit que compara els elements rebuts. Si a la classe principal hi ha definit un comparador, el mètode delega en el mètode java.util.Comparator.compare(o1, o2); altrament delega en el mètode java.lang.Comparable.compareTo(o) implementat per la classe de l'element.

Parameters:
elem1 - primer objecte de la mateixa classe
elem2 - segon objecte de la mateixa classe
Returns:
un enter negatiu, zero o positiu, segons si el primer element té menys, igual o més prioritat que el segon element, d'acord amb la implementació del comparador
Throws:
ExcepcioElementsNoComparables - si algun element és no comparable