ARBOLES
ROJO – NEGROS
INTEGRANTES
• Bazan Gonzales Jose Antonio
• García López Carlos Omar
DEFINICION
Los árboles Rojo – Negros es un
tipo de árbol que estan
balanceados de tal manera que el
tiempo de realizar operaciones
sea O(log n) en el peor de los
casos.
CARACTERISTICAS
• Fueron inventados por R. Bayer el cuál los llamo
árboles simetricos binarios.
• El Nodo contiene un campo extra el cuál se llama color.
• El árbol puede recorrerse por cualquier color, ya sea rojo
o negro.
• Los recorridos mas largos varian a lo mas el doble del
mas corto, esto quiere decir que el árbol esta
practicamente balanceado.
PROPIEDADES
• Cada Nodo solo puede tener un solo color ya
sea Rojo ó Negro.
• Cada apuntador de Hoja es de color negro.
• Si el Nodo es Rojo ambos Hijos son negros
• Cada camino desde cualquier Nodo hasta una
Hoja contiene el mismo número de Nodos
negros.
NODORB
enum BOOL{ FALSO, VERDADERO};
enum COLOR{ NEGRO, ROJO};
template<class T> class NODO_ARBOL{
public:
NODO_ARBOL(T x){dato = x; izquierdo = derecho = NULL; Color = NEGRO};
NODO_ARBOL<T>
*GetIzq(){return izquierdo;};
void
SetIzq(NODO_ARBOL<T> *ptr){izquierdo = ptr;};
NODO_ARBOL<T>
*GetDer(){return derecho;};
void
SetDer(NODO_ARBOL<T> *ptr){derecho = ptr;};
T
GetDato(){return dato;};
COLOR
GetColor(){return Color;};
void
SetColor(COLOR C){ Color = C;}
void
SetDato(T x){ dato = x;};
private:
NODO_ARBOL<T> *izquierdo, *derecho;
T dato;
COLOR Color;
}
ROTACION
• Las operaciones INSERTA y ELIMINA de
un arbol Rojo-Negro modifican la estructura
de este y pueden violar las propiedades de
los mismos antes mencionadas, por lo cual
es necesario reestablecerlas lo que
implicaria cambiar el color de algunos
nodos.
TIPOS DE ROTACION
• Rotacion Izquierda:
– Cuando realizamos una Rotacion Izquierda a un
nodo x, asumimos que su hijo derecho no es
nulo.
y
y
x
a
x
b
a
y
b
y
TIPOS DE ROTACION
• Rotacion Derecha:
– Cuando realizamos una Rotacion Derecha a
un nodo Y, asumimos que su hijo izquierdo
no es nulo.
y
y
x
a
x
b
a
y
b
y
CODIGO PARA ROTAR A LA IZQUIERDA
void ARBOLRB<T>::RotarIzq(NodoRB <T> *x){
NodoRB<T> *y;
y = x -> GetDer();
x = SetDer(Y -> GetIzq());
y -> setIzq(x);
if(Padre(x) == NULL)
Raiz = y;
else{
if (Padre(x) -> GetIzq() == x)
Padre(x) -> SetIzq(y);
else
Padre(x) -> SetDer(y);
}
}
SENTINELA
El sentinela es un modo auxiliar que nos
ayudará para el proceso de eliminación de
un nodo, al insertar un nuevo ambos hijos
deberán apuntar al sentinela, el sentinela
será de color negro y no guardará ningún
dato, éste se declarará dentro de la clase
árbol
Declaración de un sentinela
//parte privada de la clase ARBOLRB
private:
NODORB *RAIZ, SENTINELA(-26554); // se crea con
// un dato arbitrario
};
INSERCIÓN
Un arbol Rojo-Negro es un arbol binario, por lo tanto
una inserción en este se hara de la misma forma que
en un binario, pero el nodo a insertar sera siempre
rojo. Posteriormente se reajustan las propiedades del
mismo. Al momento dehacer la insercion, los
apuntadores derecho e izquierdo del nuevo nodo son
apuntados hacia el “centinela”.
Existen tres casos para la inserción de un nuevo nodo.
CASOS DE INSERCIÓN
• Caso 1: El tio de x es Rojo.
– Como el abuelo de x es negro, se colorea al
padre y al tio de x de Negro y de Rojo al
abuelo.
• Caso 2: El tio de x es Negro y x es hijo
derecho.
– Se usa una rotación a la izquierda para llevarlo
al caso tres, en el que x es hijo izquierdo
• Caso 3: El tio de x es Negro y x es hijo
izquierdo.
– Como x y su padreson rojos, se hace una
rotacion derecha, para colorear al padrede x de
negro y al abuelo de x de rojo, de modo que la
nueva raiz del subarbol es el padre de x, cuyo
hijo izquierdo es x e hijo derecho el abuelo de
x.
INSERTA
BOOL ARBOLRB<T>::Inserta(T x){
NodoRB<T> *aux, *y;
if(inserta2(x,Raiz)){ // dentro de este inserta se modifican los
aux = Localiza(x); //apuntadores al centinela
aux -> SetColor(ROJO);
while(aux != Raiz && Padre(aux) -> GetColor = ROJO){
if(Padre(aux) = Padre(Padre(aux)) -> GetIzq()){
y = Padre(Padre(aux)) -> GetDer();
if(y -> GetColor() = ROJO){
Padre(aux) -> SetColor(Negro);
y -> SetColor(NEGRO);
Padre(Padre(aux)) -> SetColor(ROJO);
aux = Padre(Padre(aux));
}
else{
if(aux = Padre(aux) -> GetDer()){
aux = Padre(aux);
RotarIzq(aux);
CONTINUACIÓN
Padre(aux) -> SetColor(NEGRO);
Padre(Padre(aux)) -> SetColor(ROJO);
RotarDer(Padre(Padre(aux)));
}
}
}
else
//lo mismo que el if pero con GetIzq y GetDer intercambiados
}
Raiz -> SetColor(NEGRO);
return VERDADERO;
}
return FALSO;
}
ELIMINA
void NODORB<T> ARBOLRB<T>::Elimina(T dato){
NODORB<T> *z, *y, * x;
z = Localiza(dato);
if(z -> GetIzq() = &SENTINELA || z -> GetDer() =
&SENTINELA)
y =z;
else
y = Sucesor(z);
if(y -> GetIzq() != SENTINELA)
x = y -> GetIzq();
else
x = y -> Getder();
if(Padre(y) = SENTINELA)
RAIZ = x;
CONTINUA
else{
if(EsIzq(y))
Padre(y) -> SetIzq(x);
else
Padre(y) -> Setder(x);
}
if(y != z){
// copiar los campos de y a z
}
if( y -> GetColor() == NEGRO)
Reordena(x);
}
REORDENA
void ARBOLRB<T>::Reordena(NodoRB <T> *ptr){
NodoRB<T> *aux;
while(ptr != Raiz && ptr -> GetColor = NEGRO){
if(ptr = Padre(ptr) -> GetIzq()){
aux = Padre(ptr) -> GetDer();
if(aux -> GetColor() = ROJO){
aux -> SetColor(NEGRO);
Padre(ptr) -> SetColor(ROJO);
RotarIzq(Padre(ptr));
aux = Padre(ptr) -> GetDer();
}
if(aux -> GetIzq() -> GetColor() == NEGRO && aux -> GetDer() -> GetColor == NEGRO){
aux -> SetColor(ROJO);
ptr = padre(ptr);
}
CONTINUACION
else{
if(aux -> GetDer() -> GetColor() == NEGRO){
aux -> GetIzq() -> SetColor(NEGRO);
aux -> SetColor(ROJO);
RotarDer(aux);
aux = Padre(ptr) -> GetDer();
}
aux -> SetColor(Padre(ptr) -> GetColor);
Padre(ptr) -> SetColor(NEGRO);
aux -> GetDer -> SetColor(NEGRO);
RotarIzq(Padre(ptr));
ptr = Raiz;
}
}
else
//lo mismo que el if pero con GetIzq y GetDer intercambiados
}
ptr -> setColor(NEGRO);
}
SUCESOR
El sucesor es una funcion que nos regresa el valor del dato
siguiente al dato actual, pero siguiendo las reglas del
recorrido en orden , es decir si existen los numeros 5, 8 , 9
en el arbol, la funcion Sucesor del 5 me debera retornar
un apuntador al dato siguiente en el recorrido el cual es 8.
Descargar

Arboles Rojo-Negros(Version de Lagrimita y mi Muchacho)