uoc.ei.tads
Class ArbolBinarioVectorImpl<E>

java.lang.Object
  extended by uoc.ei.tads.ArbolAbstracto<E>
      extended by uoc.ei.tads.ArbolBinario<E>
          extended by uoc.ei.tads.ArbolBinarioVectorImpl<E>
All Implemented Interfaces:
java.io.Serializable, Arbol<E>, Contenedor<E>
Direct Known Subclasses:
ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl

public class ArbolBinarioVectorImpl<E>
extends ArbolBinario<E>

Clase que implementa las operaciones de cualquier arbol binario, el cual se caracteriza por organizar sus elementos (nodos) formando una jerarquía: todo nodo (excepto la raíz) es descendiente de un nodo único, y puede ser ascendente de un máximo de dos nodos (cuando no tiene descendientes se nombra a hoja). En la representación secuencial del arbol se organizan los nodos dentro de de un vector de manera que los hijos y el padre son accesibles aplicando solo una formula. La primera posición del vector contendrá siempre la raíz del arbol; si un nodo está en la posición [k], su hijo izquierdo estará en la [2*k] y su hijo derecho en la [2*k+1]. Esta representación tiene dos operaciones modificadoras (añadir al final y borrar la última posición) que permiten mantener una estructura de arbol quasicompleto; es decir, no habrá ningúna posición libre en un recorrido por niveles del arbol. Dado que la primera posición [0] del vector no se utiliza para facilitar los cálculos mencionados, si el número de casillas del vector es potencia de dos, el arbol podrá llegar a ser completo.

See Also:
Serialized Form

Nested Class Summary
 
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  Rango<E>[] elems
          Tabla de elementos del contenedor.
static int MAXIMO_ELEMENTOS_POR_DEFECTO
          Capacidad máxima, por defecto, del contenedor.
protected  int n
          Número de elementos que hay actualmente al contenedor.
 
Constructor Summary
ArbolBinarioVectorImpl()
          Constructor sin parámetros (capacidad máxima, por defecto).
ArbolBinarioVectorImpl(int max)
          Constructor con un parámetro.
 
Method Summary
 void borrar(Posicion<E> padre, Posicion<E> hijo)
          Borra el subárbol representado por la posición hijo, si se puede.
 boolean estaLleno()
          Método para comprobar si el contenedor está lleno.
 boolean estaVacio()
          Método para comprobar si el contenedor está vacío.
 Posicion<E> hijoDerecho(Posicion<E> pos)
          Accesor de lectura del hijo derecho de una posición del arbol.
 Posicion<E> hijoIzquierdo(Posicion<E> pos)
          Accesor de lectura del hijo izquierdo de una posición del arbol.
 Posicion<E> insertar(Posicion<E> padre, E elem)
          Añade un elemento como nuevo hijo de la posición escogida.
 Posicion<E> insertarHijoDerecho(Posicion<E> padre, E elem)
          Añade un elemento como hijo derecho de la posición escogida, si se puede.
 Posicion<E> insertarHijoIzquierdo(Posicion<E> padre, E elem)
          Añade un elemento como hijo izquierdo de la posición escogida.
 void intercambiar(Posicion pos1, Posicion pos2)
          Intercambia dos posiciones dentro de de l'arbol.
 int numElems()
          Accesor de lectura del número de elementos que hay al contenedor.
 Posicion<E> padre(Posicion<E> pos)
          Accesor de lectura del padre de una posición del arbol, si hay.
 Posicion<E> raiz()
          Accesor de lectura de la raíz del arbol, si hay.
 E reemplazar(Posicion<E> pos, E elem)
          Reemplaza el elemento contenido en la posición escogida.
 
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

MAXIMO_ELEMENTOS_POR_DEFECTO

public static final int MAXIMO_ELEMENTOS_POR_DEFECTO
Capacidad máxima, por defecto, del contenedor.

See Also:
Constant Field Values

n

protected int n
Número de elementos que hay actualmente al contenedor.


elems

protected Rango<E>[] elems
Tabla de elementos del contenedor. Las posiciones empiezan por el cero.

Constructor Detail

ArbolBinarioVectorImpl

public ArbolBinarioVectorImpl()
Constructor sin parámetros (capacidad máxima, por defecto).


ArbolBinarioVectorImpl

public ArbolBinarioVectorImpl(int max)
Constructor con un parámetro. Crea un vector con una capacidad de max.

Parameters:
max - número máximo de elementos del arbol
Throws:
ExcepcionParametroIncorrecto - si la capacidad máxima del nuevo arbol es negativa
Method Detail

numElems

public int numElems()
Accesor de lectura del número de elementos que hay al contenedor.

Returns:
número de elementos que contiene actualmente

estaVacio

public boolean estaVacio()
Método para comprobar si el contenedor está vacío.

Specified by:
estaVacio in interface Contenedor<E>
Overrides:
estaVacio in class ArbolAbstracto<E>
Returns:
cierto o falso, según si está vacío o no lo está

estaLleno

public boolean estaLleno()
Método para comprobar si el contenedor está lleno.

Returns:
cierto o falso, según si está lleno o no lo está

raiz

public Posicion<E> raiz()
Accesor de lectura de la raíz del arbol, si hay.

Returns:
raíz del arbol
Throws:
ExcepcionContenedorVacio - si el arbol está vacío

insertar

public Posicion<E> insertar(Posicion<E> padre,
                            E elem)
Añade un elemento como nuevo hijo de la posición escogida. Si el padre es null, se añade en la raíz; si es una hoja, se añade como hijo izquierdo; y si el padre tiene únicamente un hijo, se añade como el otro hijo.

Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
La posición del nodo añadido.
Throws:
ExcepcionPosicionInvalida - Si la posición de padre es inválida para poder añadir un hijo. Eso incluye también los casos en que el padre ya tenga dos hijos y el caso en que los hijos caigan fuera del rango máximo permitido al crear el arbol.

insertarHijoIzquierdo

public Posicion<E> insertarHijoIzquierdo(Posicion<E> padre,
                                         E elem)
Añade un elemento como hijo izquierdo de la posición escogida.

Specified by:
insertarHijoIzquierdo in class ArbolBinario<E>
Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
La posición del nodo añadido.
Throws:
ExcepcionPosicionInvalida - Si la posición de padre es inválida para poder añadir un hijo. Eso incluye también los casos en que el padre ya tenga hijo izquierdo y el caso en que este caiga fuera del rango máximo permitido al crear el arbol.

insertarHijoDerecho

public Posicion<E> insertarHijoDerecho(Posicion<E> padre,
                                       E elem)
Añade un elemento como hijo derecho de la posición escogida, si se puede.

Specified by:
insertarHijoDerecho in class ArbolBinario<E>
Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
La posición del nodo añadido.
Throws:
ExcepcionPosicionInvalida - Si la posición de padre es inválida para poder añadir un hijo. Eso incluye también los casos en que el padre ya tenga hijo derecho y el caso en que este caiga fuera del rango máximo permitido al crear el arbol.

padre

public Posicion<E> padre(Posicion<E> pos)
Accesor de lectura del padre de una posición del arbol, si hay.

Parameters:
pos - posición de referencia
Returns:
padre de la posición recibida; o null si era la raíz.

hijoIzquierdo

public Posicion<E> hijoIzquierdo(Posicion<E> pos)
Accesor de lectura del hijo izquierdo de una posición del arbol.

Specified by:
hijoIzquierdo in class ArbolBinario<E>
Parameters:
pos - posición de referencia
Returns:
hijo izquierdo de la posición escogida; o null si no tiene.
Throws:
ExcepcionPosicionInvalida - si la posición no es válida.

hijoDerecho

public Posicion<E> hijoDerecho(Posicion<E> pos)
Accesor de lectura del hijo derecho de una posición del arbol.

Specified by:
hijoDerecho in class ArbolBinario<E>
Parameters:
pos - posición de referencia
Returns:
hijo derecho de la posición escogida; o null si no tiene.
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

borrar

public void borrar(Posicion<E> padre,
                   Posicion<E> hijo)
Borra el subárbol representado por la posición hijo, si se puede. Si la posición del padre es null, borra el arbol entero.

Parameters:
padre - posición del padre; puede ser null
hijo - posición del hijo
Throws:
ExcepcionPosicionInvalida - si alguna posición es no válida o bien padre no es el padre de hijo.

reemplazar

public E reemplazar(Posicion<E> pos,
                    E elem)
Reemplaza el elemento contenido en la posición escogida.

Parameters:
elem - nuevo elemento
pos - posición de referencia
Returns:
elemento que había a la posición antes de reemplazarlo.

intercambiar

public void intercambiar(Posicion pos1,
                         Posicion pos2)
Intercambia dos posiciones dentro de de l'arbol. Los objetos posición se intercambian de posición, con lo cual su contenido se mantiene constante.

Parameters:
pos1 - primera de las dos posiciones de referencia.
pos2 - segunda de las dos posiciones de referencia.