Package mx.unam.ciencias.edd

Class ArbolAVL<T extends Comparable<T>>

java.lang.Object

mx.unam.ciencias.edd.ArbolBinario<T>

mx.unam.ciencias.edd.ArbolBinarioOrdenado<T>

mx.unam.ciencias.edd.ArbolAVL<T>

All Implemented Interfaces:

Iterable<T>, Coleccion<T>

public class ArbolAVL<T extends Comparable<T>>
extends ArbolBinarioOrdenado<T>

Clase para árboles AVL.

Un árbol AVL cumple que para cada uno de sus vértices, la diferencia entre la áltura de sus subárboles izquierdo y derecho está entre -1 y 1.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	ArbolAVL.VerticeAVL	Clase interna protegida para vértices.

Nested classes/interfaces inherited from class mx.unam.ciencias.edd.ArbolBinario

ArbolBinario.Vertice

Field Summary

Fields inherited from class mx.unam.ciencias.edd.ArbolBinarioOrdenado

ultimoAgregado

Fields inherited from class mx.unam.ciencias.edd.ArbolBinario

elementos, raiz

Constructor Summary

Constructors

Constructor	Description
ArbolAVL()	Constructor sin parámetros.
ArbolAVL(Coleccion<T> coleccion)	Construye un árbol AVL a partir de una colección.

Method Summary

Modifier and Type	Method	Description
void	agrega(T elemento)	Agrega un nuevo elemento al árbol.
void	elimina(T elemento)	Elimina un elemento del árbol.
void	giraDerecha(VerticeArbolBinario<T> vertice)	Lanza la excepción UnsupportedOperationException: los árboles AVL no pueden ser girados a la derecha por los usuarios de la clase, porque se desbalancean.
void	giraIzquierda(VerticeArbolBinario<T> vertice)	Lanza la excepción UnsupportedOperationException: los árboles AVL no pueden ser girados a la izquierda por los usuarios de la clase, porque se desbalancean.
protected ArbolBinario<T>.Vertice	nuevoVertice(T elemento)	Construye un nuevo vértice, usando una instancia de ArbolAVL<T extends Comparable<T>>.VerticeAVL.

Methods inherited from class mx.unam.ciencias.edd.ArbolBinarioOrdenado

busca, dfsInOrder, dfsPostOrder, dfsPreOrder, eliminaVertice, getUltimoVerticeAgregado, intercambiaEliminable, iterator

Methods inherited from class mx.unam.ciencias.edd.ArbolBinario

altura, contiene, equals, esVacia, getElementos, limpia, raiz, toString, vertice

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

ArbolAVL

public ArbolAVL()

Constructor sin parámetros. Para no perder el constructor sin parámetros de ArbolBinarioOrdenado.

ArbolAVL

public ArbolAVL(Coleccion<T> coleccion)

Construye un árbol AVL a partir de una colección. El árbol AVL tiene los mismos elementos que la colección recibida.

Parameters:

coleccion - la colección a partir de la cual creamos el árbol AVL.

Method Details

nuevoVertice

protected ArbolBinario<T>.Vertice nuevoVertice(T elemento)

Construye un nuevo vértice, usando una instancia de ArbolAVL<T extends Comparable<T>>.VerticeAVL.

Overrides:

nuevoVertice in class ArbolBinario<T extends Comparable<T>>

Parameters:

elemento - el elemento dentro del vértice.

Returns:

un nuevo vértice con el elemento recibido dentro del mismo.

agrega

public void agrega(T elemento)

Agrega un nuevo elemento al árbol. El método invoca al método ArbolBinarioOrdenado.agrega(T), y después balancea el árbol girándolo como sea necesario.

Specified by:

agrega in interface Coleccion<T extends Comparable<T>>

Overrides:

agrega in class ArbolBinarioOrdenado<T extends Comparable<T>>

Parameters:

elemento - el elemento a agregar.

elimina

public void elimina(T elemento)

Elimina un elemento del árbol. El método elimina el vértice que contiene el elemento, y gira el árbol como sea necesario para rebalancearlo.

Specified by:

elimina in interface Coleccion<T extends Comparable<T>>

Overrides:

elimina in class ArbolBinarioOrdenado<T extends Comparable<T>>

Parameters:

elemento - el elemento a eliminar del árbol.

giraDerecha

public void giraDerecha(VerticeArbolBinario<T> vertice)

Lanza la excepción UnsupportedOperationException: los árboles AVL no pueden ser girados a la derecha por los usuarios de la clase, porque se desbalancean.

Overrides:

giraDerecha in class ArbolBinarioOrdenado<T extends Comparable<T>>

Parameters:

vertice - el vértice sobre el que se quiere girar.

Throws:

UnsupportedOperationException - siempre.

giraIzquierda

public void giraIzquierda(VerticeArbolBinario<T> vertice)

Lanza la excepción UnsupportedOperationException: los árboles AVL no pueden ser girados a la izquierda por los usuarios de la clase, porque se desbalancean.

Overrides:

giraIzquierda in class ArbolBinarioOrdenado<T extends Comparable<T>>

Parameters:

vertice - el vértice sobre el que se quiere girar.

Throws:

UnsupportedOperationException - siempre.