Package mx.unam.ciencias.edd

Class ArbolRojinegro<T extends Comparable<T>>

java.lang.Object

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

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

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

All Implemented Interfaces:

Iterable<T>, Coleccion<T>

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

Clase para árboles rojinegros. Un árbol rojinegro cumple las siguientes propiedades:

1. Todos los vértices son NEGROS o ROJOS.
2. La raíz es NEGRA.
3. Todas las hojas (null) son NEGRAS (al igual que la raíz).
4. Un vértice ROJO siempre tiene dos hijos NEGROS.
5. Todo camino de un vértice a alguna de sus hojas descendientes tiene el mismo número de vértices NEGROS.

Los árboles rojinegros se autobalancean.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	ArbolRojinegro.VerticeRojinegro	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
ArbolRojinegro()	Constructor sin parámetros.
ArbolRojinegro(Coleccion<T> coleccion)	Construye un árbol rojinegro 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.
Color	getColor(VerticeArbolBinario<T> vertice)	Regresa el color del vértice rojinegro.
void	giraDerecha(VerticeArbolBinario<T> vertice)	Lanza la excepción UnsupportedOperationException: los árboles rojinegros 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 rojinegros 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 ArbolRojinegro<T extends Comparable<T>>.VerticeRojinegro.

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

ArbolRojinegro

public ArbolRojinegro()

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

ArbolRojinegro

public ArbolRojinegro(Coleccion<T> coleccion)

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

Parameters:

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

Method Details

nuevoVertice

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

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

Overrides:

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

Parameters:

elemento - el elemento dentro del vértice.

Returns:

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

getColor

public Color getColor(VerticeArbolBinario<T> vertice)

Regresa el color del vértice rojinegro.

Parameters:

vertice - el vértice del que queremos el color.

Returns:

el color del vértice rojinegro.

Throws:

ClassCastException - si el vértice no es instancia de ArbolRojinegro<T extends Comparable<T>>.VerticeRojinegro.

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 recoloreando vértices y girando el árbol 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 recolorea 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.

giraIzquierda

public void giraIzquierda(VerticeArbolBinario<T> vertice)

Lanza la excepción UnsupportedOperationException: los árboles rojinegros 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.

giraDerecha

public void giraDerecha(VerticeArbolBinario<T> vertice)

Lanza la excepción UnsupportedOperationException: los árboles rojinegros 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.