Arbol rojo negro

ARBOLES
ROJO – NEGROS

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 porcualquier 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
Hojacontiene el mismo número de Nodos
negros.

NODORB
enum BOOL{ FALSO, VERDADERO};
enum COLOR{ NEGRO, ROJO};
template class NODO_ARBOL{
public:
NODO_ARBOL(T x){dato = x; izquierdo = derecho = NULL; Color = NEGRO};
NODO_ARBOL
*GetIzq(){return izquierdo;};
void
SetIzq(NODO_ARBOL *ptr){izquierdo = ptr;};
NODO_ARBOL
*GetDer(){return derecho;};
void
SetDer(NODO_ARBOL *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 *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 esnecesario
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
hijoizquierdo no es nulo.
y

y

x

a

x

b

a

y

b

y

CODIGO PARA ROTAR A LA
IZQUIERDA
void ARBOLRB::RotarIzq(NodoRB *x){
NodoRB *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 auxiliarque 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ÓNUn 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 nuevonodo.

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 supadreson 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::Inserta(T x){
NodoRB *aux, *y;
if(inserta2(x,Raiz)){ // dentro de este inserta se modifican los
aux = Localiza(x); //apuntadores al centinela
aux...