uoc.ei.tads
Class ArbreBinariVectorImpl<E>

java.lang.Object
  extended by uoc.ei.tads.ArbreAbstracte<E>
      extended by uoc.ei.tads.ArbreBinari<E>
          extended by uoc.ei.tads.ArbreBinariVectorImpl<E>
All Implemented Interfaces:
java.io.Serializable, Arbre<E>, Contenidor<E>
Direct Known Subclasses:
CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl

public class ArbreBinariVectorImpl<E>
extends ArbreBinari<E>

Classe que implementa les operacions de qualsevol arbre binari, el qual es caracteritza per organitzar els seus elements (nodes) formant una jerarquia: tot node (tret de l'arrel que es el cap de la jerarquia) és descendent d'un node únic, i pot ser ascendent d'un màxim de dos nodes (quan no té descendents s'anomena fulla). En la representació seqüencial de l'arbre s'organitzen els nodes dins d'un vector de manera que els fills i el pare són accessibles aplicant només una fòrmula. La primera posició del vector contindrà sempre l'arrel de l'arbre; si un node està a la posició [k], el seu fill esquerre estarà a [2*k] i el seu fill dret a [2*k+1]. Aquesta representació té dues operacions modificadores (afegir al final i esborrar l'última posició) que permeten mantenir una estructura d'arbre quasicomplet; és a dir, no hi haurà cap posició lliure en un recorregut per nivells de l'arbre. Atès que la primera posició [0] del vector no s'utilitza per facilitar els càlculs esmentats, si el nombre de caselles del vector és potència de dos, l'arbre podrà arribar a ser complet.

Since:
1.5
See Also:
Serialized Form

Nested Class Summary
 
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  Rang<E>[] elems
          Taula d'elements del contenidor.
static int MAXIM_ELEMENTS_PER_DEFECTE
          Capacitat màxima, per defecte, del contenidor.
protected  int n
          Nombre d'elements que hi ha actualment al contenidor.
 
Constructor Summary
ArbreBinariVectorImpl()
          Constructor sense paràmetres (capacitat màxima, per defecte).
ArbreBinariVectorImpl(int max)
          Constructor amb un paràmetre.
 
Method Summary
 Posicio<E> afegir(Posicio<E> pare, E elem)
          Afegeix un element com a nou fill de la posició rebuda.
 Posicio<E> afegirFillDret(Posicio<E> pare, E elem)
          Afegeix un element com a fill dret de la posició rebuda, si es pot.
 Posicio<E> afegirFillEsquerre(Posicio<E> pare, E elem)
          Afegeix un element com a fill esquerre de la posició rebuda.
 Posicio<E> arrel()
          Accessor de lectura de l'arrel de l'arbre, si n'hi ha.
 void esborrar(Posicio<E> pare, Posicio<E> fill)
          Esborra el subarbre representat per la posició fill, si es pot.
 boolean estaBuit()
          Mètode per a comprovar si el contenidor està buit.
 boolean estaPle()
          Mètode per a comprovar si el contenidor està ple.
 Posicio<E> fillDret(Posicio<E> pos)
          Accessor de lectura del fill dret d'una posició de l'arbre.
 Posicio<E> fillEsquerre(Posicio<E> pos)
          Accessor de lectura del fill esquerre d'una posició de l'arbre.
 void intercanviar(Posicio pos1, Posicio pos2)
          Intercanvia dues posicions dins de l'arbre.
 int nombreElems()
          Accessor de lectura del nombre d'elements que hi ha al contenidor.
 Posicio<E> pare(Posicio<E> pos)
          Accessor de lectura del pare d'una posició de l'arbre, si n'hi ha.
 E reemplacar(Posicio<E> pos, E elem)
          Reemplaça l'element contingut a la posició rebuda.
 
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

MAXIM_ELEMENTS_PER_DEFECTE

public static final int MAXIM_ELEMENTS_PER_DEFECTE
Capacitat màxima, per defecte, del contenidor.

See Also:
Constant Field Values

n

protected int n
Nombre d'elements que hi ha actualment al contenidor.


elems

protected Rang<E>[] elems
Taula d'elements del contenidor. Les posicions comencen pel zero.

Constructor Detail

ArbreBinariVectorImpl

public ArbreBinariVectorImpl()
Constructor sense paràmetres (capacitat màxima, per defecte).


ArbreBinariVectorImpl

public ArbreBinariVectorImpl(int max)
Constructor amb un paràmetre. Crea un vector amb una capacitat de màxim.

Parameters:
max - nombre màxim d'elements de l'arbre
Throws:
ExcepcioParametreIncorrecte - si la capacitat màxima del nou arbre és negativa
Method Detail

nombreElems

public int nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor.

Returns:
nombre d'elements que conté actualment

estaBuit

public boolean estaBuit()
Mètode per a comprovar si el contenidor està buit.

Specified by:
estaBuit in interface Contenidor<E>
Overrides:
estaBuit in class ArbreAbstracte<E>
Returns:
cert o fals, segons si està buit o no ho està

estaPle

public boolean estaPle()
Mètode per a comprovar si el contenidor està ple.

Returns:
cert o fals, segons si està ple o no ho està

arrel

public Posicio<E> arrel()
Accessor de lectura de l'arrel de l'arbre, si n'hi ha.

Returns:
arrel de l'arbre
Throws:
ExcepcioContenidorBuit - si l'arbre està buit

afegir

public Posicio<E> afegir(Posicio<E> pare,
                         E elem)
Afegeix un element com a nou fill de la posició rebuda. Si el pare és null, s'afegeix a l'arrel; si és una fulla, s'afegeix com a fill esquerre; i si el pare té únicament un fill, s'afegeix com a l'altre fill.

Parameters:
pare - posició de referència
elem - element que es vol afegir a l'arbre
Returns:
La posició del node afegit.
Throws:
ExcepcioPosicioInvalida - Si la posició de pare és invàlida per a poder afegir un fill. Això inclou també els casos en que el pare ja tingui dos fills i el cas en que els fills caiguin fora del rang màxim permès al crear l'arbre.

afegirFillEsquerre

public Posicio<E> afegirFillEsquerre(Posicio<E> pare,
                                     E elem)
Afegeix un element com a fill esquerre de la posició rebuda.

Specified by:
afegirFillEsquerre in class ArbreBinari<E>
Parameters:
pare - posició de referència
elem - element que es vol afegir a l'arbre
Returns:
La posició del node afegit.
Throws:
ExcepcioPosicioInvalida - Si la posició de pare és invàlida per a poder afegir un fill. Això inclou també els casos en que el pare ja tingui fill esquerre i el cas en que aquest caigui fora del rang màxim permès al crear l'arbre.

afegirFillDret

public Posicio<E> afegirFillDret(Posicio<E> pare,
                                 E elem)
Afegeix un element com a fill dret de la posició rebuda, si es pot.

Specified by:
afegirFillDret in class ArbreBinari<E>
Parameters:
pare - posició de referència
elem - element que es vol afegir a l'arbre
Returns:
La posició del node afegit.
Throws:
ExcepcioPosicioInvalida - Si la posició de pare és invàlida per a poder afegir un fill. Això inclou també els casos en que el pare ja tingui fill dret i el cas en que aquest caigui fora del rang màxim permès al crear l'arbre.

pare

public Posicio<E> pare(Posicio<E> pos)
Accessor de lectura del pare d'una posició de l'arbre, si n'hi ha.

Parameters:
pos - posició de referència
Returns:
pare de la posició rebuda; o null si era l'arrel.

fillEsquerre

public Posicio<E> fillEsquerre(Posicio<E> pos)
Accessor de lectura del fill esquerre d'una posició de l'arbre.

Specified by:
fillEsquerre in class ArbreBinari<E>
Parameters:
pos - posició de referència
Returns:
fill esquerre de la posició rebuda; o null si no en té.
Throws:
ExcepcioPosicioInvalida - si la posició no és vàlida.

fillDret

public Posicio<E> fillDret(Posicio<E> pos)
Accessor de lectura del fill dret d'una posició de l'arbre.

Specified by:
fillDret in class ArbreBinari<E>
Parameters:
pos - posició de referència
Returns:
fill dret de la posició rebuda; o null si no en té.
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

esborrar

public void esborrar(Posicio<E> pare,
                     Posicio<E> fill)
Esborra el subarbre representat per la posició fill, si es pot. Si la posició del pare és null, esborra l'arbre sencer.

Parameters:
pare - posició del pare; pot ser null
fill - posició del fill
Throws:
ExcepcioPosicioInvalida - si alguna posició és no vàlida o bé pare no és el pare de fill.
See Also:
esborrar(Posicio, Posicio)

reemplacar

public E reemplacar(Posicio<E> pos,
                    E elem)
Reemplaça l'element contingut a la posició rebuda.

Parameters:
elem - nou element
pos - posició de referència
Returns:
element que hi havia a la posició abans de reemplaçar-lo.

intercanviar

public void intercanviar(Posicio pos1,
                         Posicio pos2)
Intercanvia dues posicions dins de l'arbre. Els objectes posició s'intercanvien de posició, amb lo qual el seu contingut es manté constant.

Parameters:
pos1 - primera de les dues posicions de referència.
pos2 - segona de les dues posicions de referència.