Post on 28-Oct-2014
description
Mgter. Juan Pablo Apaza Condori 1
UNIVERSIDAD CATÓLICA DE SANTA MARIA P. P. INGENIERÍA SISTEMAS
LABORATORIO DE ALGORITMIA Y ESTRUCTURA DE DATOS I
ÁRBOLES ROJINEGROS (RED BLACK TREE)
I OBJETIVOS
Explicar el TAD Árbol Rojo Negro Implementar el TAD Árbol Rojo Negro. Utilizar el TAD Árbol Rojo Negro para la resolución de problemas.
II TEMAS
TAD Árbol Rojo Negro Inserción, eliminación en un Árbol Rojo Negro
III MARCO TEÓRICO ¿PARA QUÉ SIRVEN?
Son una clase de árboles binarios de búsqueda �equilibrados� (altura máxima logarítmica en el número de nodos) para garantizar coste O(log n) de las operaciones básicas del TAD diccionario.
Últimamente, por alguna razón que veremos, han estado más �de moda� que los árboles AVL.
ÁRBOL ROJO NEGRO: DEFINICIÓN
Árbol binario de búsqueda con un bit adicional en cada nodo, su color, que puede ser rojo o negro.
Ciertas condiciones sobre los colores de los nodos garantizan que la profundidad de ninguna hoja es más del doble que la de ninguna otra (el árbol está �algo equilibrado�).
Cada nodo es un registro con: color (rojo o negro), clave (la clave de búsqueda), y tres punteros a los hijos (i, d) y al padre (p).
Si los punteros son NIL, imaginaremos que son punteros a nodos �externos� (hojas).
Sesión
2
id3934546 pdfMachine by Broadgun Software - a great PDF writer! - a great PDF creator! - http://www.pdfmachine.com http://www.broadgun.com
Mgter. Juan Pablo Apaza Condori 2
ÁRBOL ROJO NEGRO: CONDICIONES
Condiciones rojinegras: RN1 - Cada nodo es rojo o negro. RN2 - Toda hoja (NIL) es negra. RN3 - Si un nodo es rojo, sus dos hijos son negros. RN4 - Todo camino desde un nodo a cualquier hoja descendente contiene el mismo número
de nodos negros.
ÁRBOL ROJO NEGRO: TERMINOLOGÍA
Terminología: Altura negra de un nodo x, an(x): es el número de nodos negros desde x (sin incluir
x) hasta cualquier hoja descendente de x. Altura negra de un árbol: la altura negra de su raíz.
ÁRBOL ROJO NEGRO: EJEMPLO
Mgter. Juan Pablo Apaza Condori 3
ÁRBOL ROJO NEGRO: LEMA
Lema Todo árbol rojinegro con n nodos internos tiene una altura menor o igual que 2 log(n+1).
Consecuencias del lema: Las operaciones de búsqueda pueden implementarse en tiempo O(log n) para árboles
rojinegros con n nodos. ¿Y la inserción y el borrado?
Veremos a continuación que también pueden realizarse en tiempo O(log n) sin que el árbol deje de ser rojinegro.
ÁRBOL ROJO NEGRO: INSERTAR
Al insertar nuevos elementos en árboles rojinegros, en tiempo O(log n), se debe garantizar que el árbol resultante continúe siendo rojinegro
En los árboles rojinegros las hojas son vacías y negras Los nuevos elementos se colocan como padres de hojas Cada nuevo elemento se coloca como una estructura del árbol binario Como las hojas deben ser negras, el nodo que contiene la llave a insertarse se colorea como
rojo No se aumenta la altura negra del árbol
La única propiedad que puede violarse es la referente al color del padre del nodo que se ha insertado
ÁRBOL ROJO NEGRO: PATRONES DE AJUSTE Los tres patrones de ajuste que pueden ser necesarios después de la inserción de un nodo V en un árbol rojo negro. Los ajustes sólo serán necesarios cuando P es rojo. PATRÓN 1 Cuando U es rojo solo se necesita una recoloración. Esto puede propagarse hacia arriba en el árbol, produciendo rotaciones y/o recoloraciones adicionales.
G
P
V
NIL NIL
G
P
V
NIL NIL
U U
Mgter. Juan Pablo Apaza Condori 4
PATRÓN 2 Si U es negro y V es un hijo izquierdo aplicamos una operación rotar-derecha (g) (en el centro) seguida de una recoloración (derecha). Esto detendrá la propagación.
PATRÓN 3 Si U es negro y V es un hijo derecho aplicamos una doble rotación consistente de una operación rotar-izquierda (p) seguida de rotar-derecha (g) (en el centro) y entonces una recolección (derecha). Esto también detendrá la propagación.
S V
P
NIL NIL
S
G
P
V
NIL U
NIL S
G
P
V
NIL U
NIL
U
G
U
G
P
V
NIL NIL
S
G
P
V
NIL NIL U
S
G
P
V
NIL NIL U
S
Mgter. Juan Pablo Apaza Condori 5
ÁRBOL ROJO NEGRO: EJEMPLO DE INSERCIÓN Generar el árbol Rojo Negro con la siguiente secuencia de datos: 10, 5, 1, 2, 15, 18, 3, 20, 40 1 Insertar 10, 5
2 Insertar 1
10
5
V
NIL
NIL
NIL
G
1
P
NIL
U
10 V
NIL NIL
1
NIL U
NIL
G
5 P
V 10
NIL NIL
10
5 V
NIL NIL
NIL
P
Mgter. Juan Pablo Apaza Condori 6
3 Insertar 2
4 Insertar 15
5 Insertar 18
10
V
NIL
1
NIL U
5
G
NIL NIL
2 P
NIL
15
NIL NIL
18
10 V
NIL
1
NIL U
5
G
NIL NIL
2
P
NIL
15
NIL NIL
18
10
V NIL
1
NIL
U
5 G
NIL NIL
2
P
NIL NIL
15
10
V NIL NIL
1
NIL
NIL
U
5 G
NIL
2
P 10
V NIL NIL
1
NIL
NIL
U
5 G
NIL
2
P
Mgter. Juan Pablo Apaza Condori 7
6 Insertar 3
U
P
10 V
NIL
1
NIL
5
G
NIL
2
NIL
15
NIL NIL
18
NIL
3
NIL
U P 10
V
NIL
1
NIL
5
G
NIL
2
NIL
15
NIL NIL
18
NIL
3
NIL
Mgter. Juan Pablo Apaza Condori 8
7 Insertar 20
U P 10
V NIL
1
NIL
5
G
NIL
2
NIL
15
NIL
18
NIL
3
NIL
NIL NIL
20
U P 10
V NIL
1
NIL
5
G
NIL
2
NIL
15
NIL
18
NIL
3
NIL
NIL NIL
20
Mgter. Juan Pablo Apaza Condori 9
8 Insertar 40
PROPUESTOS Elabore el árbol rojo negro de la siguiente secuencia de datos: 1. 10, 13, 15, 50, 30, 40, 60, 25, 28 2. 100, 190, 120, 205, 115, 148, 230, 262, 174
U P
10
V
NIL
1
NIL
5
G
NIL
2
NIL
15
NIL
18
NIL
3
NIL
NIL
20
NIL NIL
40
5
U
P
10
V
NIL
1
NIL
G
NIL
2
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 10
ÁRBOL ROJO NEGRO: ELIMINAR
Coincide con la operación de supresión en los árboles de búsqueda binaria Sin embargo, es necesario mantener la estructura de los árboles rojinegros Para evitar repeticiones se introduce vigía, nil(A), el cual representa las hojas del árbol rojinegro Si el nodo suprimido y fuese rojo, entonces, las alturas negras no cambian y, en tal caso,
termina Si el nodo suprimido y fuese negro, entonces, las ramas que pasen por y tienen un nodo negro
menos, lo que viola la condición de los árboles rojinegros. En este caso es necesario ajustar colores.
ÁRBOL ROJO NEGRO: PATRONES DE AJUSTE Los cuatro patrones de ajuste que pueden ser necesarios después de la eliminación de un nodo U de un árbol rojo negro. El nodo que sustituye a U está etiquetado con V. Los ajustes solo son necesarios si V es un nodo negro distinto de la raíz. PATRÓN 1 Si S es rojo, con una operación rotar izquierda (P) (en el centro), seguida de la recoloración mostrada en la derecha, este caso se transforma en uno de los otros tres casos.
NR
V+ S
P
NL
NIL NIL
NIL NIL
NIL NIL
NR V+
S P
NL
NIL NIL NIL NIL
NIL NIL
NR V+
S P
NL
NIL NIL NIL NIL
NIL NIL
Mgter. Juan Pablo Apaza Condori 11
PATRÓN 2 Si S y sus dos hijos son negros, sólo se necesita una recoloración. Esto se puede propagar hacia arriba en el árbol.
PATRÓN 3 Si S es negro y su hijo derecho es rojo aplicamos una operación rotar izquierda (P) (en el centro), seguida de la recoloración mostrada a la derecha. Esto restablece la regla del negro en el árbol.
NR
V+ S
P
NL
NIL NIL
NIL NIL
NIL NIL
NR V
S P
NL
NIL NIL NIL NIL
NIL NIL
NR V
S P
NL
NIL NIL NIL NIL
NIL NIL
NR
V+ S
P
NL
NIL NIL
NIL NIL
NIL NIL
NR
V S
P
NL
NIL NIL
NIL NIL
NIL NIL
Mgter. Juan Pablo Apaza Condori 12
PATRÓN 4 Si S y su hijo derecho son negros, y su hijo izquierdo es rojo, aplicamos una operación de Rotar derecha (S) (en el centro) seguida de la recoloración mostrada a la derecha. Este caso se transforma en el mostrado en el patrón 3.
NR
V+ S
P
NL
NIL NIL
NIL NIL
NIL NIL
NR
V+ S
P
NL
NIL
NIL
NIL NIL
NIL NIL
NR
V+ S
P
NL
NIL
NIL
NIL NIL
NIL NIL
Mgter. Juan Pablo Apaza Condori 13
ÁRBOL ROJO NEGRO: EJEMPLOS DE ELIMINACIÓN EJEMPLO 1 Eliminar el 3 del siguiente árbol rojo negro.
SOLUCIÓN
U
P
10
V
NIL
1
NIL
5
G
NIL
2
NIL
15
NIL
18
NIL
NIL
20
NIL NIL
40
10
NIL
1
NIL
5
NIL
2
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 14
EJEMPLO 2 Eliminar el 2 del siguiente árbol rojo negro.
SOLUCIÓN
10
NIL
1
NIL
5
NIL
2
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
10 NIL
NIL
5
1
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 15
EJEMPLO 3 Eliminar el 15 del siguiente árbol rojo negro.
SOLUCIÓN 1 Aplicando el patrón 3
NR
S
P
V+
NIL
1 NIL
5
NL
NIL
2 10
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
10
NIL
1
NIL
5
NIL
2
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 16
2 Rotamos a la izquierda
Como V tiene ahora un antepasado negro adicional en este subárbol, la unidad extra de color negro ha sido absorbida
3 Aplicamos recoloración
V
NR
S
P
NIL
1
NIL
5
NL
NIL
2
10
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
V
NR
S
P
NIL
1
NIL
5
NL
NIL
2
10
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 17
EJEMPLO 4 Eliminar el 5 y luego 3 del siguiente árbol rojo negro.
SOLUCIÓN 1 Dado que el nodo V es rojo:
NR
S
P
V
NIL
1 NIL
3
NL NIL
2 10
NIL
18
NIL
NIL
20
NIL NIL
40
10
NIL
1
NIL
5
NIL
2
NIL
15
NIL
18 NIL
3
NIL
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 18
2 Eliminando 3
Como V tiene ahora la unidad extra de color negro entonces es absorbida
NL NR
S
P
V
NIL
1
NIL
2
NIL
10
NIL
18
NIL
20
NIL NIL
40
NL NR
S
P
V+
NIL
1
NIL
2
NIL
10
NIL
18
NIL
20
NIL NIL
40
Mgter. Juan Pablo Apaza Condori 19
PROPUESTOS Dado el siguiente árbol rojo negro 1 Eliminar el nodo con valor 20 2 Eliminar el nodo con valor 4 3 Eliminar el nodo con valor 9
10 2
NIL
9
4
NIL
16
6 20
NIL
18
NIL NIL NIL
40
NIL NIL
1
NIL NIL
3
NIL NIL
5
NIL
7
NIL
8
NIL
Mgter. Juan Pablo Apaza Condori 20
ÁRBOL ROJO NEGRO:: PROGRAMA EN C++
red-black.h
typedef int A; class ArbolRN{ private: class NodoRN{ public: A clave; NodoRN *der, *izq, *pad; int color; NodoRN(A ele,NodoRN*padre=NULL){ clave=ele; izq=der=NULL; pad=padre; color=1;//rojo } void show(){ cout<<clave<<"\t"<<color<<"\t"; (pad)?cout<<pad->clave:cout<<"NULL";cout<<"\n"; } }; NodoRN *Raiz; public: ArbolRN(){Raiz=NULL;} void showTree(NodoRN*root=NULL,bool r=true); void insertar_rn(A ele); void busqueda(A ele); protected: void rotacion_der(NodoRN*); void rotacion_izq(NodoRN*); NodoRN* insertar_abb(NodoRN**,NodoRN*,A); void restaurar_color(NodoRN*); NodoRN* busqueda_rn(NodoRN**,A); }; ArbolRN::NodoRN* ArbolRN::insertar_abb(NodoRN **root,NodoRN *padre,A ele) { if(!(*root)){ *root=new NodoRN(ele,padre); return (*root); } else if (ele <(*root)->clave) insertar_abb(&((*root)->izq),(*root),ele); else if (ele>(*root)->clave) insertar_abb(&((*root)->der),(*root),ele); else{
Mgter. Juan Pablo Apaza Condori 21
cout<<"No puede haber claves repetidas"; } } void ArbolRN::rotacion_izq(NodoRN*nodo) { NodoRN*aux=NULL; aux=nodo->der; nodo->der=aux->izq; if(aux->izq!=NULL) aux->izq->pad=nodo; aux->pad=nodo->pad; if(nodo->pad==NULL) Raiz=aux; else { if(nodo==nodo->pad->izq) nodo->pad->izq=aux; else nodo->pad->der=aux; } aux->izq=nodo; nodo->pad=aux; } void ArbolRN::rotacion_der(NodoRN*nodo) { NodoRN*aux=NULL; aux=nodo->izq; nodo->izq=aux->der; if(aux->der!=NULL) aux->der->pad=nodo; aux->pad=nodo->pad; if(aux->pad==NULL) Raiz=aux; else { if(nodo==nodo->pad->der) nodo->pad->der=aux; else nodo->pad->izq=aux; } aux->der=nodo; nodo->pad=aux; } void ArbolRN::insertar_rn(A ele){ NodoRN *x=insertar_abb(&Raiz,0,ele); restaurar_color(x); } void ArbolRN::busqueda(A ele){ NodoRN *pNode=busqueda_rn(&Raiz,ele); if(!pNode) cout<<"No esta el elemento"; else cout<<"elemento si esta"; } ArbolRN::NodoRN* ArbolRN::busqueda_rn(NodoRN** root, A ele){
Mgter. Juan Pablo Apaza Condori 22
if(!(*root)){ cout<<"No se encontro elemento"; return 0; } else if (ele <(*root)->clave) busqueda_rn(&((*root)->izq),ele); else if (ele>(*root)->clave) busqueda_rn(&((*root)->der),ele); else return (*root); } void ArbolRN::restaurar_color(NodoRN*nodo) { NodoRN*aux=NULL; while(nodo!=Raiz && nodo->pad->color==1) { if(nodo->pad==nodo->pad->pad->izq){ aux=nodo->pad->pad->der; if(aux && aux->color==1) { nodo->pad->color=0; aux->color=0; nodo->pad->pad->color=1; nodo=nodo->pad->pad; } else{ if(nodo==nodo->pad->der){ nodo=nodo->pad; rotacion_izq(nodo); } nodo->pad->color=0; nodo->pad->pad->color=1; rotacion_der(nodo->pad->pad); } } else{ aux=nodo->pad->pad->izq; if(aux && aux->color==1) { nodo->pad->color=0; aux->color=0; nodo->pad->pad->color=1; nodo=nodo->pad->pad; } else{ if(nodo==nodo->pad->izq){ nodo=nodo->pad; rotacion_der(nodo); } nodo->pad->color=0; nodo->pad->pad->color=1; rotacion_izq(nodo->pad->pad); } } } Raiz->color=0; }
Mgter. Juan Pablo Apaza Condori 23
void ArbolRN::showTree(NodoRN* root,bool r){ if(r) root=Raiz; if(!root) return; showTree(root->izq,false); root->show(); showTree(root->der,false); }
red-black.cpp
#include<iostream.h> #include"red-black.h" void main(){ ArbolRN A1; A1.insertar_rn(29); A1.insertar_rn(19); A1.insertar_rn(12); A1.insertar_rn(50); A1.insertar_rn(15); A1.insertar_rn(33); A1.insertar_rn(70); A1.insertar_rn(23); A1.insertar_rn(42); A1.insertar_rn(61); A1.insertar_rn(25); A1.insertar_rn(31); A1.insertar_rn(66); A1.insertar_rn(64); A1.insertar_rn(63); A1.insertar_rn(32); A1.insertar_rn(62); A1.eliminar_rn(33); /* A1.eliminar_rn(42); A1.eliminar_rn(50); A1.eliminar_rn(61); A1.eliminar_rn(62); A1.eliminar_rn(19);*/ A1.showTree(); cin.get(); }
Mgter. Juan Pablo Apaza Condori 24
Presione F5 o haga clic en
Mgter. Juan Pablo Apaza Condori 25
IV ACTIVIDADES 1 Ingrese a la siguiente dirección URL
http://reptar.uta.edu/NOTES5311/REDBLACK/RedBlack.html
Mgter. Juan Pablo Apaza Condori 26
2 Ingrese a la siguiente dirección URL http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
Mgter. Juan Pablo Apaza Condori 27
V EJERCICIOS 1 Insertar 40, 33, 46, 6, 8, 24, 18, 22, 25, 60 en un árbol rojo negro 2 Implementar ña operación eliminar en un árbol rojo negro
SupresionRN( A, z ) { if (left(z) = nil(A)) or (right(z) = nil(A)) then y := z; else y := SucesorABB(z); if left(y) ? nil(A) then x := left( y ); else x := right( y ); p(x) := p(y); if p(y) = nil then root( A ) := x; else if y = left( p(y) ) then left( p(y) ) := x else right( p(y) ) := x; if y ? z then key(z) = key( y ); if C(y) = black then AjustarSupresionRN( A, x ) } AjustarSupresionRN( A, x ) { /* Ciclo principal */ while x ? root(A) and C(x) = black do { if x = left( p(x) ) then { w := right( p(x) ); if C(w) = red then { 1) C(w) := black; C(p(x)) := red; LeftRotate( A, p(x) ); w := right( p(x) ) }; if ambos hijos de w son negros then {
Mgter. Juan Pablo Apaza Condori 28
2) C(w) := red; x := p(x) } else { if C(right(w)) = black then { 3) C( left(w) ) := black; C(w) := red; RightRotate( A, w ); w := right( p(x) ) }; 4) C(w) := C(p(x)); C(p(x) := black; C(right(w)) := black; LeftRotate( A, p(x) ); x := root( A ) } } else { código simétrico intercambiando "left" y "right" } }; C(x) := black }