Download UNIVERSIDAD MICHOACANA SAN NICOLAS DE HIDALGO

UNIVERSIDAD MICHOACANA SAN NICOLAS DE HIDALGO
División de Estudios de Postgrado de la Facultad de Ingeniería Eléctrica.
Dr. Juan J. Flores Romero
Implementación del Programa Arbol Rojo-Negro.
Presenta: Estela Erendira Arriga Mora.
INTRODUCCIÓN
El árbol es una estructura de datos fundamental en la computación. Un ejemplo de una
organización de este tipo es la forma en como se almacenan los ficheros en los arboles o en
estructuras de similares en los sistemas operativos.
Los árboles se usan también en diseño de compiladores, procesamiento de texto y
algoritmos de búsqueda.
Un árbol definido no recursivamente consiste en un conjunto de nodos, y de aristas
orientadas que conectan pares de nodos. Definido recursivamente un árbol es o bien vacío o
costa de una raíz y cero o más subarboles.
Se considerara un árbol con raíz, aquel que tiene las siguientes propiedades:
1) Se tiene un nodo que se distingue como raíz.
2) A cada nodo c exceptuando la raíz, le llega una arista exactamente de otro nodo p, a la
cual se le llama padre de c Decimos que c es uno de los hijos de p.
3) Hay un único camino desde la raíz, hasta cada nodo. El numero de aristas del mismo
recibe el nombre de longitud del camino.
A
B
F
C
G
D
Nodo
A
B
C
D
F
G
H
Altura
2
1
0
1
0
0
0
Profundidad
0
1
1
1
2
2
2
H
En la figura anterior el nodo raíz es A, y los hijos de A son B, C, D. A es la raíz y no tiene
padre. Todos los demás nodos tiene padre; por ejemplo, el padre de b es A, los nodos no
tienen hijos reciben el nombre de hojas. Las hojas de este árbol son C, F,G, H.
La longitud del un camino de A á F es de dos (aristas), y la de l camino de A á A es cero
aristas.
Un árbol con N nodos debe tener N-1 aristas por que cada nodo, excepto a la raíz; le llega
una arista. la profundidad un nodo en un árbol es la longitud del camino que va desde la
raíz siempre hasta ese nodo. En consecuencia la profundidad de la raíz es siempre es cero,
y la de cualquier nodo es la de un camino que va desde el nodo hasta la hoja más profunda
bajo de el. La altura de un nodo es la longitud de un camino que va desde el nodo hasta la
hoja mas profunda bajo de él. La altura de un árbol se define como la altura de su raíz.
Los nodos que tienen el mismo padre son hermanos, Luego B, C, D son hermanos si hay un
camino del nodo U al nodo V entonces decimos que U es ascendiente de V y que V es un
descendiente propio de U, el tamaño de un nodo es igual al número de sus descendientes
que tiene (incluyendo dicho nodo). El tamaño de B es 3 y de C es 1. El tamaño del arbol se
define como su raíz.
ARBOLES BINARIOS
Un árbol binario es un árbol en que ningún nodo pude tener mas de dos hijos.
(hijo izquierdo e hijo derecho) también se puede dar el caso de que exista un solo hijo ya
sea izquierdo o derecho. Se tendrá entonces que el árbol tiene raíz nodos e hijos (Los
nodos que tengan descendientes son llamados padres y a los últimos conocidos como
hojas).
Existen los siguientes métodos para recorrer un árbol binario.
1) Pre-Orden
 Se visita la raíz.
 Se recorre el subarbol izquierdo en Pre-Orden.
 Se recorre el subarbol derecho en Pre-orden.
2) Post-Orden
 Se recorre el subarbol izquierdo en Post-Orden.
 Se recorre el subarbol derecho en Post-Orden.
 Se visita la raíz.
3) En-Orden
 Se recorre el subarbol izquierdo en En-Orden.
 Se visita la raíz.
 Se recorre el subarbol derecho En-Orden.
En este tipo de arboles se pueden realizar la búsqueda de un nodo.
ARBOLES ROJO-NEGRO
Un árbol Rojo-Negro es un árbol binario de busqueda que verifica las siguientes
propiedades además de contar con las del árbol binario.
1.
2.
3.
4.
Cada nodo es de color rojo o negro.
La raíz es negra.
Si un nodo es rojo sus dos hijos deben ser negros.
Todos los caminos desde un nodo a una refencia null deben contener el mismo número
de nodos negros.
En este tipo de árbol cualquier camino desde la raíz contiene B nodos negros, entonces al
árbol debe tener al menos 2B-1 nodos negros. Teniendo que la raíz es negra y no pueden
existir dos nodos consecutivos color rojo en un camino, la altura de un árbol Rojo-Negro es
a lo sumo 2log(N+1). Como consecuencia, esta garantizado que la búsqueda de la
operación es logarítmica.
ARBOL ROJO-NEGRO
Raíz
20
Hijo derecho de la raíz
(padre de los nodos 15 y 17)
Hijo izquierdo (hoja)
15
18
Hijo izquierdo de la raíz
(padre del nodo 28)
26
17
28
Hijo derecho (hoja)
Hijo derecho (hoja)
Nota: Los nodos de color son rojos
INSERCION
Mediante la inserción se dan de alta los nodos en el árbol. Los nodos a insertar son rojos y a
medida que se insertan se alteran las propiedades del árbol Rojo-Negro.
La coloración de los nodos de cualquier camino de la raíz hasta una hoja, es necesario
asegurar que no es dos veces mas largo que cualquier otro por lo que un árbol rojo rojonegro es aproximadamente balanceado para lograr esto es necesario las rotaciones hacia la
izquierda o hacia la derecha según sea necesario.
ROTAR A LA DERCHA (T,Y)
X
Y

ROTAR A LA IZQUIERDA (T,Y)
X


Y



Caso 1: El padre y el hijo izquierdo son rojos, el tío es rojo. Este caso se resuelve
coloreando el tío de negro y el padre rojo.
Caso 2: El hijo derecho rojo el padre rojo y el tío negro. Este caso se resuelve con una
rotación hacia la izquierda.
Caso3: El hijo es rojo el padre es rojo y el tío es negro. Este caso se resuelve con una
rotación hacia la derecha.
BORRADO
El borrado en un árbol rojo-negro es en tiempo (lg n). Su algoritmo general es el
siguiente:
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2
then y  z
3
else y  TREE-SUCCESSOR(z)
4 if left[y]  nil[T]
5
then x  left[y]
6
else x  right[y]
7 p[x]  p[y]
8 if p[y] = nil[T]
9
then root[T]  x
10
else if y = left[p[y]]
11
then left[p[y]]  x
12
else right[p[y]] x
13 if y  z
14
then key[z]  key[y]
15
 If y has other fields, copy them, too.
16 If color[y] = BLACK
17
Then RB-DELETE-FIXUP(T,x)
18 return y
Este algoritmo hace uso del algoritmo de reparar borrado este ultimo se encarga de
restablecer las propiedades de coloración de los nodos y realiza las llamadas a los métodos
de rotación para restaurar las propiedades del árbol rojo-negro. Este algoritmo se presenta
continuación.
RB-DELETE-FIXUP(T, x)
1 while x  root[T] and color[x] = BLACK
2
do if x = left[p[x]]
3
then w  right [p[x]]
4
if color[w] = RED
5
then color[w]  BLACK
Case 1
6
color[p[x]]  RED
Case 1
7
LEFT-ROTATE(T, p[x])
Case 1
8
w  right[p[x]]
Case 1
9
if color[left[w]] = BLACK and color[right[w]] = BLACK
10
then color[w]  RED
Case 2
11
x  p[x]
Case 2
12
else if color[right[w]] = BLACK
13
then color[left[w]]  BLACK
Case 3
14
color[w]  RED
Case 3
15
RIGHT-ROTATE(T,w)
Case 3
16
w  right[p[x]]
Case 3
17
color[w]  color[p[x]]
Case 4
18
color[p[x]]  BLACK
Case 4
19
color[right[w]]  BLACK
Case 4
20
LEFT-ROTATE(T, p[x])
Case 4
21
x  root[T]
Case 4
22
else (same as then clause
with "right" and "left" exchanged)
23
color[x]  BLACK
IMPLEMENTACION
CLASE nodoRN
Para implementar este tipo de árbol se necesita definir el nodo este esta en el archivo
nodoRN.java.
Las variables publicas que se declaran son las siguientes:
info: Esta variable de tipo int contendrá la información del nodo. El árbol implementado
es un árbol de datos de tipo enteros.
Para acceder a la información de un nodo. Variable de tipo nodoRN.info
Donde la variable de tipo nodoRN hace referencia al nodo y la variable info arrojara un
valor de tipo int. Se utiliza también la variable dato la cual se utiliza para introducir la
información a la variable info en método constructor nodoRN.
color: Esta variable es de tipo int y recibe un valor numérico. Esta variable esta incializada
con el valor de 0 el cual en este programa identifica al color negro y el valor de 1 será el
color rojo. (Recordando que la raíz es negra una de las propiedades de los arboles rojonegros). La primera inserción será una raíz de color negra y el segundo elemento será un
nodo de color rojo. Este nodo será coloreado en el método ordena.
Para acceder al color de un nodo. Variable de tipo nodoRN.color
Donde la variable de tipo nodoRN hace referencia al nodo y la variable color arrojara un
valor de 0 o 1.
izq: Es una variable de tipo nodoRN la cual permite que el nodo tenga un apuntador hacia
su izquierda.
Para acceder a la izquierda de un nodo. Variable de tipo nodoRN.izq
Donde la variable de tipo nodoRN hace referencia al nodo y la variable izq tendrá la
referencia del nodo que esta hacia su izquierda. Si se quisiera saber la información de dicho
nodo: Variable de tipo nodoRN.izq.info
der: Es una variable de tipo nodoRN la cual permite que el nodo tenga un apuntador hacia
su derecha.
Para acceder a la derecha de un nodo. Variable de tipo nodoRN.der
Donde la variable de tipo nodoRN hace referencia al nodo y la variable der tendrá la
referencia del nodo que esta hacia su derecha. Si se quisiera saber la información de ese
nodo: Variable de tipo nodoRN.der.info.
a: Es una variable de tipo nodoRN la cual permite que un nodo tenga un apuntador hacia su
padre.
Para acceder a la derecha de un nodo. Variable de tipo nodoRN.a
Donde la variable de tipo nodoRN hace referencia al nodo y la variable a tendrá la
referencia del padre de ese nodo. Si se quisiera saber la información de su padre Variable
de tipo nodoRN.a.info.
CLASE arbolRN
En el archivo arbolRN.java se tiene declarada la variable raíz la cual por ser de tipo
nodoRN contiene todos los campos mencionados anteriormente.
hijo: Esta variable declarada como private de tipo nodoRN. Se usa en el método inserta,
ordena, rotar_izq, rotar_der, minimo, sucesor, borraRN, reapara_borraRN.
Para acceder a la información de esta variable se utiliza la instrucción hijo.info (en el
método inserta).
padre: Variable declarada como private de tipo nodoRN. Se usa en el método inserta, y
sirve pare guardar la referencia de la variable hijo antes de que esta ultima cambie. Ya que
esta variable va contener la referencia de otra variable de tipo nodoRN es necesario que
este declarada del mismo tipo, de no hacerlo el compilador envía un error de conversión de
tipos.
sentinela : Variable declarada como static de tipo nodoRN. Esta variable contiene el valor
entero 5000 y su color es negro (0). Se utiliza para que los nodos creados, los padres que no
tengan uno de los dos hijos o la raíz tengan una referencia. Esta referencia se utiliza en
varios métodos, en el método ordena. El algoritmo RB-INSERT y LEFT-ROTATE (libro:
Introduction to Algorithms.) Asume que existe el "tío" del nodo insertado y el enlazador de
java no envía un mensaje de error pero en el caso de no existir en "tío" es necesario
acceder a esa referencia y se manda entonces al sentimela. En todos los nodos creados sus
referencias izq y der contienen sentinelas y dejan de tenerlas en el momento en que se
inserte un hijo a dicho nodo.
y, z, x: Son variables auxiliares declarada como private de tipo nodoRN y se utilizan en
varios los métodos ordena , rotar_izq, rotar_der, borraRN, sucesor y repara_RN.
El archivo nodoRN.java contiene la clase publica nodoRN de tal forma que otra clase
puede hacer uso de sus variables de clase info, color, izq, der y a. El único método que
contiene es el método de tipo nodoRN publico se encarga de inicalizar las variables, el
método recibe un dato de tipo int y el valor que contiene inicializa a la variable info
también de tipo int, incializa las variables izq, der, a con null (ya que estas son de tipo
nodoRN), la variable color se inicializa con el valor de cero (recordando que este valor
representa al color negro) .
El primer dato a insertar va hacer la raíz y su color será negro(0) y el primer nodo izquierdo
y derecho después de la raíz serán los hijos de la raíz (y al mismo tiempo hojas) del árbol.
Todo nodo insertado después de la raíz su campo color será igual a rojo (1).
Se declara una variable sentinela de tipo nodoRN, está variable es estática y contiene el
valor entero de 5000.
En el archivo arbolRN.java contiene la clase publica arbolRN la cual como se menciono
anteriormente permite declarar las variables raíz, hijo, padre, sentinela, y, z y x.
El método estático main permite crear una variable de l de tipo arbolRN y mediante esta
variable llama al método insertaRN enviando a este un valor de tipo entero.
El método publico insertaRN recibe un dato de tipo entero y no devuelve ningún tipo de
valor. Si la variable raíz es nula (es decir no contiene ninguna referencia) el árbol es vacío y
entonces se crea la raíz. Esta contendrá la referencia del dato que se ha introducido. Las izq
y der de la raíz contendrán la referencia del sentinela. También la el campo a de la raíz
tendrá una referencia hacia el sentinela el cual será el padre de la raíz.
En caso de que la raíz no sea nula los demás elementos insertados serán los hijos de la raíz
si el elemento es menor que la raíz será su hijo izquierdo y si es mayor serán su hijo
derecho después de que la raíz tenga hijos, los demás elementos serán hijos de los hijos de
la raíz. Esto lo logra mediante una llamada al método inserta, después de insertar un dato
hace una llamada al procedimiento ordena el cual verifica y restaura las propiedades del
árbol rojo-negro atravéz de rotaciones y cambios de color.
El método publico inserta no devuelve valor pero se encarga de construir el árbol. Si el
dato existe en el árbol no lo acepta de lo contrario compara el dato con la variable hijo.info
(La cual estaba tenia la referencia de la raíz en el método insertaRN) y determina su
inserción a la izquierda o la derecha de esta, esto se repite con todos los demás datos del
árbol hasta encontrar su lugar.
El método publico ordena no devuelve valor alguno, colorea a los nodos insertados
después de la raíz de color rojo (Le asigna al nodo es su campo color el valor de 1) y
verifica si se altera alguna de las propiedades del árbol rojo-negro según el caso a tratar
colorea los nodos y hace llamados a los procedimientos rotar_izq o rotar_der.
Los métodos públicos rotar_izq y rotar_der se encargan de rotar la variable que reciben
tipo nodoRN.
Los métodos públicos preorden, postorden y enorden llamados por el main son formas
de recorrer el árbol. La llamada a los métodos no contienen argumentos. Cada uno de estos
métodos envía la variable hijo de tipo nodoRN que es recibida por otro método llamado de
forma similar al que envío la variable y se encarga recorrer el árbol e imprimir los datos.
El método publico buscarRN es llamado por el main que envía un dato de tipo int, este
valor es recibido en buscarRN y envía un el dato al método buscar este empieza a
compara el dato con la variable de referencia hijo y "camina" por cada una de sus ramas si
encuentra al elemento lo envía pero si no lo encuentra envía el valor del sentinela (5000).
Este método también es llamado por el método borrarRN.
El método publico sucesor se encarga de enviar el sucesor del nodo que le es enviado.
Si la variable enviada nodorN.der es distinto de sentinela se llamara al método minimo este
encontrara al elemento minimo de ese nodo y lo regresara al sucesor.
El método minino recibe una variable de tipo nodoRN y mientras hijo sea distinto de
sentinela bajara por el árbol hacia la izquierda cuando encuentre el elemento menor lo
mandara al método sucesor.
El método borrarRN recibe un dato entero y llama al método buscarRN una vez que lo
encuentra lo borra cambiando las referencias de su padre. Este método se auxilia de
método sucesor y el método rapara_borraRN.
El método repara_borraRN cambia los colores de los nodos y realiza las rotaciones para
restaurar las propiedades de un árbol rojo-negro.
ERRORES
Durante la compilación y el enlazamiento del programa se presentaron diversos tipos de
errores. Los más frecuentes fueron errores de sintaxis que marcaba el compilador de java
una vez corregidos estos; En algunas ocasiones el enlazador de java marcaba error de
apuntador nulo. Esto se corrigió revisando en el código la línea que mandaba ese tipo de
error y revisando las referencias a las que se llamaba. Los mas difíciles a tratar fueron los
errores de tipo lógico en esto fuer necesario revisar el pseudocodigo, el programa
(generalmente se corregía al comparar o reestructurar el pseudocodigo o el programa ).
Bibliografía
Marks Allen Weiss, "Estructura de datos en JAVATM . Compatible en JAVA
Wesley,1ra. Edición en español, Pág. 435, 436, 492, 495.
TM
2",
Thomas H. Cormen y otros, "Introduction to Algorithms" ,Mc Graw Hill, 3ra. Edición en
español, Pág 263, 266, 268, 272, 273, 274.