Download Cap_4(tda_Red_Black)_2008

ÁRBOLES
RED-BLACK
Introducción
Los árboles RED-BLACK son un tipo de árbol binario de búsqueda (ABB) con la
particularidad de ser balanceados lo que nos asegura un tiempo en las operaciones básicas
(insertar, buscar, eliminar) de O(lg n) en el peor de los casos.
Un ABB es un RED-BLACK si cumple con las siguientes propiedades:
-
Todos sus nodos son negros o rojos.
Toda hoja (entiéndase por hoja a los hijos de un nodo que no contienen datos) es
negras.
Si un nodo es rojo, entonces sus dos hijos son negros.
Todo camino simple desde un nodo a una hoja descendiente tiene el mismo
número de nodos negros.
Ejemplo de un árbol RED-BLACK:
3
1
0
5
2
4
8
DEFINICION
Los arboles RED-BLACK son un tipo de arboles de búsqueda binaria, donde sus
nosos son de color negro o rojos, pero tienen la propiedad de ser balanceados, el
ser de tipo ABB significa que el insertar, buscar o eliminar en el peor de los casos
el costo de las operaciones es Ο(logn) en el peor de los casos.
Para que un arbol sea un RED-BLACK debe cumplir con las siguientes
propiedades:
1)
2)
3)
4)
Todo nodo deber ser rojo o negro.
Su raiz debe ser negra.
Toda hoja del arbol debe ser Negra.
Si un nodo en rojo su hijo debe ser negro.
2
5) Todo camino simple de un nodo a la hoja tiene el mismo numero de nodos
negro.
5
5
6
3
3
1
8
4
7
9
La fig muestra un ejemplo del Red Black
ESTRUCTURA DE UN NODO RED-BLACK
Tipo
Nombre
Comparable
Int
Nodo_RedBlack
Nodo_RedBlack
Nodo_RedBlack
Datos
Color
izq
der
Padre
INSERTAR
Como sabemos la inserción de este arbol es igual que el insertado en un arbol
binario, pero con la propiedad de que el nodo insertado siempre va ser rojo.
Luego de tener insertado el nodo en el árbol se rompera la propiedad Red-Black si
y solo si el padre es rojo, si el padre es negro no existen problemas tal como se ve
en este ejemplo, en el que se ha insertado C y su padre es rojo:
B
A
3
(Recordar que nunca un nodo rojo tiene un padre rojo.)
Ahora que se ha insertado el nodo y se rompió una propiedad, existen 2 formas de
arreglarlo.
Caso 1°
Si el tío del nodo es rojo se recolorea el padre, el abuelo y el tío como se ve en la
figura:
C
B
C
D
B
A
D
A
Como se ve el tío de A es D y es rojo, por lo que B (padre), D(tío) y A(abuelo) se
recolorean, si C fuera raiz se colorea negro nuevamente.
Caso 2°
Si el tío es negro se aplica una rotación simple o doble y se recolorea de esta
forma, el tipo de rotación depende de en que posición están el padre y el nodo a
que causa el problema, esto es, si el nodo con problemas y el padre son ambos
hijos derechos o ambos hijos izquierdos se hace una rotación simple y sino una
rotación doble.
C
B
A
C
D
A
B
C
D
4
Rotación Doble
(Acá se ve como A es hijo derecho de B, y B es hijo izquierdo de C entonces corresponde una
rotación doble)
Cuando el padre tiene en el mismo sentido que el nodo con insertado se hace una
rotacion simple.
C
B
B
A
C
A
Rotacion Simple
(Acá se ve como A es hijo izquierdo de B y B es hijo izquierdo de C)
El costo de insertar en un arbol RED-BLACK es de Ο(log n).
EJEMPLO DE INSECION
Se insertaran los siguientes nodos en un árbol Red-Black
5
8
3
2
1
6
7
9
Se inserta el 5, queda negro porque es la raíz.
5
Caso 1
5
5
5
8
5
3
8
3
Como 5 es raíz
se pinta negro
2
5
8
3
2
8
3
6
8
3
Como 2 es hijo izq.
y 1 también, rotación
simple
Caso 2
5
5
1
2
1
1
2
5
8
2
5 debería ser rojo,
como es raíz es
negro
Tío es rojo y
padre también
Caso 2
5
3
8
2
1
8
3
6
7
Como 6 es hijo izq.
y 7 también, rotación
doble
6
5
5
Caso 1
2
1
7
3
2
6
1
8
7
3
6
8
9
Como tío de9 es rojo
se recolorea
5
2
1
7
3
6
8
9
Lema: Un árbol RED-BLACK con “n” nodos internos, tiene altura a lo mas 2*lg(n+1).
7
Estructura de un nodo para un árbol RED-BLACK
TIPO
Booleano
Tipo_Clave
Nodo
Nodo
Nodo
NOMBRE
Color
Valor
Hijo_Izq
Hijo_Der
Padre
Utilidad, ventajas y desventajas
Los árboles Red-Black son útiles cuando los valores que contienen los nodos tienen la
misma probabilidad de ser accedidos, esto significa que su estructura permite tener en
general el mismo tiempo de acceso para todos los nodos (logN), tales como aplicaciones de
control de usuarios en una red de Internet, por lo que no es recomendable usarlo en
aplicaciones en las que algunos datos tienen prioridad sobre otros y se desea que estos se
encuentre lo mas cerca posible de la raíz.
Entre las ventajas en este tipo de árboles se encuentran:
1° La facilidad de implementación: Este es un ABB con un identificador adicional, por lo
que se puede reutilizar código de un ABB, la búsqueda es la misma.
2° El tamaño de los nodos es pequeño, ya que tiene 3 punteros a nodos (padre, hijo
derecho, hijo izquierdo), el dato y un BIT para identificar el color, esto se traduce en que, el
tamaño que los datos fuera del árbol ocupan es prácticamente el mismo tamaño que ocupará
el árbol construido en memoria.
3° La estructura asegura un tiempo de inserción, búsqueda y eliminación proporcional a
Log N, por ejemplo si la cantidad de datos en el árbol es 1.000.000 el costo para cualquiera
de las operaciones básicas es alrededor de O(20).
8
Búsqueda
Como se explico anteriormente un árbol Red-Black es un árbol binario de búsqueda
balanceado, el balanceo se hace por medio de la coloración de los nodos pero esta no tiene
ninguna significancia en la búsqueda así que se hace de la misma forma que en un ABB.
Ejemplo
Se tiene el siguiente árbol y se va a buscar el valor 4 en él.
1- 4 es menor que 5 así que busca en el sub árbol izquierdo de 5.
2- 4 es mayor que 3 así que busca en el sub árbol derecho de 3.
3- 4 es igual a 4 así que se retorna ese nodo.
Si no hubiera encontrado el nodo habría hecho 3 comparaciones, esto corresponde con la
altura de el árbol, dado que los árboles Red-Black son balanceados la altura del árbol no
supera los 2*logN+1, esto significa que el árbol puede desbalancearse a lo mas el doble
hacia un lado, lo que ocurre en el caso de que el sub árbol mas largo contiene nodos rojos y
negros alternados y el sub árbol mas corto contiene solo nodos negros.
De esto se deduce que la búsqueda tiene un costo proporcional a logN.
9
Inserción:
Este tipo de árboles provee una implementación y entendimiento fáciles en relación a la
inserción con respecto a otras estructuras de búsqueda.
Cuando se inserta un nodo al árbol este nuevo nodo siempre va a ser rojo, este se inserta al
árbol como en cualquier otro árbol binario.
Luego de tener insertado el nodo en el árbol se va a romper la propiedad Red-Black si y
solo si el padre es rojo, si el padre es negro no existen problemas tal como se ve en este
ejemplo, en el que se ha insertado C y su padre es rojo:
(Recordar que nunca un nodo rojo tiene un padre rojo.)
Ahora que se ha insertado el nodo y se rompió una propiedad, existen 2 formas de
arreglarlo.
Caso 1° Si el tío del nodo es rojo se recolorea el padre, el abuelo y el tío como se ve en la
figura:
Como se ve el tío de C es D y es rojo, por lo que B (padre), D(tío) y A(abuelo) se
recolorean.
10
Caso 2°
Si el tío es negro se aplica una rotación simple o doble y se recolorea de esta forma, el tipo
de rotación depende de en que posición están el padre y el nodo a que causa el problema,
esto es, si el nodo con problemas y el padre son ambos hijos derechos o ambos hijos
izquierdos se hace una rotación simple y sino una rotación doble.
Rotación Doble
(Acá se ve como C es hijo derecho de B, y B es hijo izquierdo de A entonces corresponde
una rotación doble)
En este caso 0 es hijo izquierdo y el padre (1)
hijo izquierdo por lo que se hace una rotación
simple sobre 1 en la que el árbol queda de esta
forma:
es
(Como se puede notar se supone que las hojas
tienen hijos negros)
Rotación Simple
Resumen: La inserción se hace de la misma forma que en un ABB, cuando se producen
problemas al insertar un nodo si su tío es rojo se recolorea, si su tío es negro se rota y
después se recolorea, el tipo de rotación depende de la orientación del nodo insertado y de
la orientación del padre, si son iguales se rota simple, si son distintas se hace la rotación
doble.
11
Ejemplo de Inserción:
Se insertaran los siguientes nodos en un árbol Red-Black
En los gráficos I=Insertar, C=Colorear, R=Rotar.
Se inserta el 5, queda negro porque es la raíz.
Se inserta el 2 y el 8 y no hay problemas.
Se inserta el 3 y su padre (2) es rojo así que se procede a ver que tipo de problema es, como
su tío (8) es rojo, solo se recolorea.
Ahora se inserto el (4) y su padre es
rojo y su tío es negro así que sabemos
que hay que rotar y colorear. Como el
nodo (4) es hijo derecho y el padre(3)
también se hace una rotación simple
y la recoloración.
12
Ahora insertamos el 1 y no causa problemas pero insertamos el 0 y si causa problemas,
como se aprecia su padre es rojo y su tío es negro así que hay que rotar, como el padre (1) y
el nodo (0) son ambos hijos izquierdos (tienen la misma orientación) se hace una rotación
simple y recoloración.
Al recolorear el (1) hace problemas y su tío (8) es negro, como el (1) y su padre (3) son
hijos izquierdos se hace una rotación simple y se recolorea nuevamente y el árbol final
queda así:
Obs.: Recordar que el paso final es hacer siempre hacer la raíz negra.
Costo: La inserción consiste en la ubicación del nodo en una hoja y un número de
intercambio de punteros y coloraciones que no depende de la cantidad de nodos en el árbol,
por lo que tiene un costo proporcional a la altura, esto significa: logN.
13
Eliminación:
La eliminación de un dato en un árbol RED-BLACK consta de dos pasos, primero
se procede con el mismo método de eliminación en un ABB normal, es decir buscar el
elemento a eliminar y remplazarlo por el mayor de sus descendientes reduciendo el
problema a la eliminación de una hoja; luego se procede a restablecer las propiedades para
el balanceo de un RED-BLACK.
El método siguiente para la eliminación se basa en la idea de que, el eliminar un
nodo rojo no afecta las propiedades del árbol RED-BLACK por lo que no se produce
ningún problema, pero al eliminar un nodo negro se rompe la propiedad numero 4 (todo
camino simple desde un nodo a una hoja descendiente tiene el mismo número de nodos
negros), es decir, faltaría un nodo negro en todos los caminos que pasaban por el nodo
eliminado, en otras palabras, quedamos “debiendo” un nodo negro en esos caminos, por lo
que es necesario tomar ciertas medidas para restablecer el árbol, con este fin marcamos la
hoja que reemplaza al nodo eliminado con un marcador de negro; como todas las hojas son
siempre negras, esta en particular será “doblemente negra”, situación que debemos
solucionar llevando el marcador de negro hasta un nodo rojo, lo que hará que este nodo
pase a ser negro.
Se puede presentar uno de ocho casos, de los cuales analizaremos solo 4, pues
depende de la orientación que tenga el nodo a eliminar (si es hijo derecho o hijo izquierdo)
y la solución en ambos casos es simétrica.
CASO 1:
Se presenta cuando el hermano de la hoja doblemente negra es negro y su hijo izquierdo es
rojo.
SOLUCION:
Realizamos una rotación simple, y el hermano de x toma el color del padre y el padre toma
el color negro, el marcador de doble negro se elimina automáticamente.
A
C
X
C
A
B
B
X
14
CASO II:
Si el sobrino de x es hijo derecho, intercambiamos los colores del hermano y sobrino de x y
realizamos una rotación simple, lo que nos lleva al caso anterior.
A
A
X
B
X
C
C
B
CASO III:
Se presenta cuando el hermano y ambos sobrinos de la hoja doblemente negra son negros.
SOLUCION:
Hacemos subir el marcador negro un nivel “quitando un negro” en el nivel original.
A
A
X
B
X
B
15
CASO IV:
Se presenta cuando el hermano de la hoja doblemente negra es rojo.
SOLUCION:
Intercambiando los colores del padre y el hermano del nodo doblemente negro y realizando
una rotación se convierte en un caso del tipo I, II o III.
A
B
A
B
X
X
C
D
C
D
16
Ejemplo de eliminación:
Eliminaremos todos los nodos de un árbol en el siguiente orden:
1, 12, 7, 15, 18, 20, 8, 13, 9.
9
9
7
Eliminar (1)
15
1
8
12
7
18
13
15
8
12
20
7
Marcador
en la raíz:
se elimina
9
15
8
18
13
20
7
15
12
18
13
Se presenta
el caso 2
nuevamente
9
8
Se presenta
el caso 2
20
12
18
13
20
17
9
9
7
Eliminar (12)
15
8
12
7
15
8
18
13
20
9
7
7
18
13
20
Como 12 es rojo
se elimina
9
12
15
15
8
8
13
13
18
18
20
12
20
18
9
9
Eliminar (7)
7
8
15
8
13
Como 7 es rojo,
simplemente se
elimina
15
7
18
13
18
20
20
9
9
8
Eliminar (15)
15
13
15
18
13
20
9
8
8
20
9
Se produce
el caso 1
13
18
8
18
18
20
13
20
9
9
13
Eliminar (9)
13
13
13
9
9 es rojo
en su
nueva
posición,
se elimina
sin
problemas
Solo nos
queda 13,
simplemente
se borra
19
Red-Black y 2-3-4
Existe una relación entre un árbol Red-Black y un 2-3-4, esto significa que podemos pasar
un árbol 2-3-4 a un árbol Red-Black. La relación de la que se habla es muy estrecha por lo
que hacer esta conversión no implica nuevos cálculos ni reestructuración de ninguno de los
2 árboles.
El método de conversión consiste en convertir cada nodo en el árbol 2-3-4 en una
combinación que se sabe de antemano de nodos Red-Black. La conversión de nodos se
hace de la siguiente forma como se muestra en la figura:
Cada 2-nodo queda igual y de color negro.
Cada 3-nodo (2 claves 3 hijos) se transforma en un negro y un rojo.
Y cada 4-nodo (3 claves 4 hijos) se transforma en 1 negro y dos rojos:
Ya que los árboles 2-3-4 tienen la propiedad de que todas las hojas están a la misma
distancia de la raíz y en la conversión cada nodo 2-3-4 se convierte en una combinación de
nodos Red-Black pero siempre con 1 nodo negro, el árbol Red-Black contendrá siempre la
misma cantidad de nodos negros desde la raíz hasta las hojas, esto permite que después de
la conversión de los nodos se tenga un árbol Red-Black cumpliendo todas las propiedades y
no halla que hacer ningún cambio ni comprobación de las propiedades.
20
Ejemplo de conversión de un árbol 2-3-4 en un Red-Black
Aquí se puede apreciar como cada nodo 2-3-4 fue transformado en su equivalente
combinación de nodos Red-Black
21
Aplicación.
Como ya lo dijimos anteriormente los árboles balanceados como son en este caso
los RED-BLACK resultan ventajosos en aplicaciones en las cuales es necesario acceder a
los datos en forma uniforme, es decir, no existe una prioridad conocida para ciertos datos
sobre otros. Es por esta razón que hemos decidido utilizar esta estructura para implementar
una aplicación que controle el acceso de los usuarios a un sistema cualquiera. La aplicación
controlara los datos de identificación de usuarios (login o nombre de usuario y su respectiva
password) permitiendo lograr un bajo costo en la búsqueda (para comparar que los datos
ingresados por el usuario sean correctos) y mantención de la lista de usuarios registrados.
22