|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbreAbstracte<E>
uoc.ei.tads.ArbreBinari<E>
uoc.ei.tads.ArbreBinariEncadenatImpl<E>
uoc.ei.tads.ArbreAVL<E>
public class ArbreAVL<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.
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 |
---|
protected java.util.Comparator<E> comparador
Constructor Detail |
---|
public ArbreAVL()
public ArbreAVL(java.util.Comparator<E> comparador)
comparador
- comparador que permet deduir la prioritat
ExcepcioParametreIncorrecte
- si el comparador és nullMethod Detail |
---|
protected void equilibrar(Posicio<E> node)
node
- arbre o subarbre de nodes que s'ha d'equilibrarprotected ArbreBinariEncadenatImpl.NodeArbre<E> crearNode(Posicio<E> pare, E elemComp)
crearNode
in class ArbreBinariEncadenatImpl<E>
pare
- pare del nou nodeelemComp
- element comparable que es vol desar al node
public void afegir(E elemComp)
elemComp
- element comparable que es vol afegir a l'arbre
ExcepcioElementsNoComparables
- si l'element és no
comparablepublic E esborrar(E elemComp)
elemComp
- element comparable que es vol suprimir de l'arbre
ExcepcioContenidorBuit
- si l'arbre està buit
ExcepcioElementsNoComparables
- si l'element és no
comparablepublic E consultar(E elemComp)
elemComp
- element comparable que es vol consultar
ExcepcioContenidorBuit
- si l'arbre està buit
ExcepcioElementsNoComparables
- si l'element és no
comparablepublic boolean hiHaComparador()
protected int comparar(E elem1, E elem2) throws ExcepcioElementsNoComparables
elem1
- primer objecte de la mateixa classeelem2
- segon objecte de la mateixa classe
ExcepcioElementsNoComparables
- si algun element és no
comparable
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |