• Author / Uploaded
• Jois Villacis Freire

• Categories
• Datos informáticos
• Algoritmos y estructuras de datos
• TI/Ciencias de la Computación
• Ciencia
• Informática y tecnología de la información

Citation preview

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

I.

PORTADA UNIVERSIDAD TÉCNICA DE AMBATO Facultad de Ingeniería en Sistemas, Electrónica e Industrial

Título: Carrera: Área Académica: Línea de Investigación: Nivel y Paralelo: Alumnos participantes:

Módulo y Docente: II. 1. 2.

Tipo de Arbol Rojo - Negro Ingeniería en Sistemas Computacionales Nombre del Área Académica Línea de la Carrera Tercero “A” Chasi Christian Paul Pintag Marco Villacís Johanna Carolina Estructura de Datos PhD. Félix Oscar Fernández Peña

INFORME DEL PROYECTO PP YY

2.1 Título Tipo de Arbol Rojo - Negro 2.2 Objetivos

Identificar aspectos fundamentales del árbol rojo - negro Determinar las características que abarcan el árbol rojo - negro 2.3 Resumen La investigación y el análisis de diversas formas del tipo de árbol binario dentro de la estructura de datos se llevarán a cabo gracias a las diversas distribuciones que nos facilitan a gran escala la identificación de una manera más eficaz del tema tratado en el presente informe. 2.4 Palabras clave: (Palabra1, palabra2, palabra3…..) -Arbol -Rojo -Negro -Binario 2.5 Introducción El presente trabajo pretende dar a conocer los resultados obtenidos tras la investigación cualitativa del tipo de árbol binario rojo - negro dentro de la estructura de datos de TDA. Como primer punto se realizó la investigación del tema tratado en el presente trabajo poniendo en marcha la aplicación del primer objetivo de este trabajo cumpliendo así el análisis de las diferentes especificaciones del árbol y así obtener un análisis más minucioso en representación al tema.

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

2.6 Materiales y Metodología

Árboles coloreados. Red black. Si las claves siempre ingresan ordenadas en forma aleatoria, puede emplearse un árbol binario de búsqueda. Sin embargo si por momentos se producen ingresos de claves en orden, debe escogerse una estructura que pueda rebalancear dinámicamente el árbol. El árbol coloreado, como se verá, tiene un criterio de balance un tanto más relajado que un AVL. Por esta razón, si los datos ingresan preponderantemente ordenados el árbol AVL tiene un mejor comportamiento que el red-black, ya que tiene una altura menor. Si los datos son accesados mayormente en forma secuencial, el árbol desplegado, splay, tiene un mejor comportamiento que los anteriores. [1]

2.6.1. Propiedades de los árboles coloreados. Se agrega a cada nodo un dato que indica su color. Existen reglas que deben cumplirse para asignar el color a cada nodo, de tal modo que una trayectoria cualquiera desde un nodo a una hoja no sea mayor que el doble del largo de cualquier otra. Esto asegura que el árbol coloreado se mantenga más o menos balanceado, asegurando un costo logarítmico para las operaciones en peor caso.

Propiedades: 1. Cualquier nodo es rojo o negro. 2. Cualquier descendiente de hoja se considera negro. (Los nodos externos, son negros; éstos no son nodos con información.) La raíz debe ser negra. 3. Si un nodo es rojo, sus hijos son negros. No hay dos rojos adyacentes. 4. Cualquier trayecto desde un nodo hacia una hoja contiene el mismo número de nodos negros. La Figura 1 muestra los nodos con valores 4, 7, 12 y 20 de color rojo. La estructura cumple las propiedades anteriores.

9 4 2

15 5

12

20

7

Figura 1 Árbol de búsqueda binaria coloreado.

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

Una buena interpretación de los nodos rojos en un árbol coloreado, es dibujarlos en un nivel horizontal, de este modo se refleja que no alteran las alturas negras de los nodos. Esto se muestra en la Figura 2, para el árbol coloreado de la Figura 1. En la representación con rojos en nivel horizontal, debe cuidarse que cada nodo tenga dos hijos, para que el árbol sea binario.

También puede verse, con esta representación, que en un árbol coloreado todas las hojas tienen la misma altura. El árbol coloreado es un caso particular de un B-Tree, en los cuales los nodos pueden almacenar varias claves.

4 2

9 5

7

12

15

20

Figura 1a Árbol coloreado con rojos horizontales. Debido a la presencia de nodos rojos, al menos la mitad de los nodos de un trayecto de un nodo hasta las hojas deben ser negros. La trayectoria más larga, una que alterna entre nodos rojos y negros, es sólo el doble del largo de la trayectoria más corta, la formada sólo por nodos negros.

Figura 2 Trayectos en peor caso.

Luego de insertar desde el 1 hasta el 14, que es un peor caso de árbol binario de búsqueda, en el árbol coloreado que se muestra en la Figura 2, el trayecto más largo es de 6 nodos por la vía más larga y de tres nodos por la más corta.

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

En la Figura 2, puede comprobarse que las alturas negras de todos los nodos son iguales, y que no hay dos rojos adyacentes; además la raíz es negra, cumpliendo todas las propiedades. [2]

2.6.2. Complejidad en árboles coloreados.

En un árbol coloreado, con n nodos internos, debe cumplirse que la altura h es a lo más:

h 2log( n 1)

Se define la función altura negra de un nodo x, bh(x), como el número de nodos negros de cualquier trayectoria desde x hasta una hoja, no contando el nodo x.

Se desea probar, mediante inducción, que un subárbol, que parte en el nodo x, contiene bh(x) a lo menos 2 -1 nodos internos.

Si x es un nodo externo, entonces bh(x) = 0, y el número de nodos internos es: 20-1=0. Si x es una hoja, entonces bh(x) = 1, y el número de nodos internos es: 21-1=1. Si x tiene alto h, los nodos hijos de x, tienen altura (h-1). Si el hijo es rojo tiene altura negra: bh(x), igual a la del padre Si el hijo es negro tiene altura negra: bh(x)-1, ya que no se cuenta el nodo negro.

Considerando verdadera la proposición para el número de nodos internos del subárbol que comienza en x; los subárboles de los hijos de x, deben entonces tener a lo menos: 2bh(x)-1-1 nodos internos.

Para obtener el número de nodos internos del subárbol que comienza en x, sumamos los nodos internos de los subárboles hijos, más el nodo interno x, se obtiene:

n >= (2bh(x)-1-1) + (2bh(x)-1-1) + 1 = 2(2bh(x)-1) - 1=2bh(x)-1

Lo cual demuestra la proposición inicial.

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

Pero en un árbol coloreado al menos la mitad de los nodos de un trayecto de un nodo hasta las hojas deben ser negros, entonces si h es la altura de un árbol, que comienza en x, se tiene que:

h bh (x) 2

Entonces, reemplazando en la expresión de n, en función de bh(x), la cota para bh(x), se obtiene:

n 2bh ( x ) 1

2h

/2

1

Despejando h, se logra:

h 2log( n 1)

(log( n))

Debe notarse que ésta es la complejidad de peor caso.

Al insertar o descartar nodos en un árbol coloreado, pueden violarse las propiedades que los definen; y para mantenerlo coloreado, como se verá más adelante, deben cambiarse los colores de algunos nodos y también posiblemente efectuar rotaciones. Esto se refleja en un costo adicional para las funciones de inserción y descarte en un árbol binario de búsqueda.

Para un árbol AVL, la cota para la altura resulta menor que en árbol coloreado:

hAVL 1, 4404 log( n ) (log( n))

La Figura 2a, muestra la complejidad del árbol coloreado, respecto del AVL, y puede observarse que son muy similares. Pero las operaciones se realizan en menor tiempo, en un árbol coloreado. En un árbol binario de búsqueda, en promedio, si las claves llegan aleatoriamente, se tiene la altura: hBST 1, 3863 log( n ) (log( n)) . Pero ésta se incrementa hasta n, en el peor caso.

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

coloreado AVL

Bst promedio

balanceado

Figura 2a. Comparación de complejidades. Red-Black, AVL, Balanceado. [3]

2.6.3 Inserción. La codificación resulta sencilla detallando de los diferentes casos.. Se pasa por referencia el árbol. pnodo insertar(pnodo *tree, pnodo nuevo) { pnodo y=NULL; pnodo x=*tree; if (nuevo==NULL) {Error(1,0); return (NULL);}

//malloc no pudo crear nodo

//Busca posición para insertar. while(x!=NULL) { y = x; if (nuevo->clave < x->clave) x=x->left; else if (nuevo->clave > x->clave) x=x->right; else {Error(2, nuevo->clave); return(NULL);}

//clave duplicada

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

} //y apunta al padre del lugar de inserción.

nuevo->padre=y; if (y == NULL) {*tree=nuevo; nuevo->color=BLACK; return(nuevo);} else if (nuevo->clave < y->clave) y->left=nuevo; else y->right=nuevo;

/*Código adicional para preservar las propiedades de árbol coloreado*/ x=nuevo; while ( (x->padre!=NULL) && ( x->padre->color==RED) ) //doble rojo { if ( x->padre==x->padre->padre->left) //como la raíz es negra, existe el abuelo de x //si x es descendiente izquierdo del abuelo. { y=x->padre->padre->right; // y apunta al tío

if ((y!=NULL)&&(y->color==RED)) // solo recoloración. { x->padre->color=BLACK; y->color=BLACK; //pinta NEGRO al tío y al padre x->padre>padre->color=RED; //el abuelo que era negro, cambia de color x=x->padre->padre; //debe seguir revisando ascendentemente } else //Debe reestructurarse mediante rotaciones. Si y es nulo o y apunta a negro. { if (x==x->padre->right) { x= x->padre; lrot(tree,x);} x->padre->color=BLACK; x>padre->padre->color=RED; rrot(tree, x->padre->padre); }

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

}

else //Código especular. Si x es descendiente derecho del abuelo. { y=x->padre->padre->left; // y apunta al tío if ((y!=NULL)&& (y->color==RED)) // solo recoloración. { x->padre->color=BLACK; y->color=BLACK; //pinta al tío x->padre->padre->color=RED; //el abuelo que era negro, cambia de color x=x->padre->padre; //debe seguir revisando } else //Debe reestructurarse mediante rotaciones { if (x==x->padre->left) { x= x->padre; rrot(tree,x);} x->padre->color=BLACK; x>padre->padre->color=RED; lrot(tree, x->padre->padre); } } } (*tree)->color=BLACK; //pinta la raíz negra return (nuevo); }

2.6.4 Descarte.

Para marcar con x la raíz de un subárbol, que disminuyó su altura negra, se emplea un nodo externo, de color negro, para almacenar un puntero al padre de éste, cuando el nodo que debe ser descartado es negro y es una hoja. Se pasa como argumento, a la función que restaura las propiedades de un árbol coloreado, en caso de descartar un nodo negro, si el nodo x es un centinela (nodo externo); de esta forma antes de modificar el puntero x, se podrá escribir el valor nulo en el padre de x.

/* Descarta nodo z, liberando el espacio*/ //z no debe ser NULL

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

void descarta(pnodo *rootp, pnodo z) { nodo externo; int centinela=0; pnodo x, y; if(z==NULL) Error(3,0); if (z->left == NULL || z->right == NULL) y=z; //un hijo u hoja else y=sucesor(z);

//Si hay hijo rojo, lo pega; si es hoja: y->right es nulo, y también x. if (y->left != NULL) x=y->left; else x=y->right;

if(y->color==BLACK) { //y es negro. if (x==NULL) {centinela=1; x=&externo; x->color=BLACK;}/y es hoja; x es nodo externo. x->padre = y->padre; //si y tiene hijo rojo, o si y es hoja }

if (y->padre == NULL) { if(centinela) *rootp=NULL; else *rootp=x;} else if (y==y->padre->left) y>padre->left = x; else y->padre->right = x;

if (y!=z) { z->clave =y->clave; }

if (y->color == BLACK) delete_fix(rootp, x, centinela);

free(y); }

/* Reestablece propiedades árbol coloreado luego de un descarte */ void delete_fix(pnodo *rootp, pnodo x, int esexterno)

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

{ pnodo w;

while (x!=*rootp && x->color==BLACK) { if (x==x->padre->left) //x es descendiente izquierdo { w=x->padre->right; //w es el hermano if (w->color==RED) { w->color=BLACK; x>padre->color=RED; lrot(rootp, x->padre); w=x->padre->right; } //ahora el hermano es negro. if ( (w->left==NULL || w->left->color==BLACK) //nodo externo o interno && (w->right==NULL || w->right->color==BLACK) ) { w->color=RED;//ambos sobrinos negros if(esexterno) {x->padre->left=NULL; esexterno=0;} x=x->padre; //cambia x. Asciende un nivel y sigue balanceando. } else {//uno o ambos sobrinos son rojos if (w->right==NULL || w->right->color == BLACK) //externo o interno

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

{//sobrino derecho negro w->left->color=BLACK; w->color=RED; rrot(rootp, w); w=x>padre->right; } //ahora el sobrino derecho es rojo w->color=x->padre>color; x->padre->color = BLACK; w->right->color = BLACK; lrot(rootp, x->padre); if(esexterno) {x->padre->left=NULL; esexterno=0;} x=*rootp; //lleva x a la raiz, se sale del lazo } } else //código especular del if { //x es descendiente derecho. w=x->padre->left; if (w->color==RED) {w->color=BLACK; x->padre->color=RED; rrot(rootp, x->padre); w=x->padre->left; } if ( (w->right==NULL || w->right->color==BLACK) && (w->left==NULL || w->left->color==BLACK))

{ w->color=RED; if(esexterno)

{x->padre->right=NULL; esexterno=0;} x=x->padre; } else {

UNIVERSIDAD TÉCNICA DE AMBATO FACULTAD DE INGENIERÍA EN SISTEMAS, ELECTRÓNICA E INDUSTRIAL CARRERA DE INGENIERÍA EN SISTEMAS COMPUTACIONALES E INFORMÁTICOS PERÍODO ACADÉMICO: MARZO 2017 / SEPTIEMBRE 2017

if (w->left==NULL || w->left->color == BLACK) { w->right->color=BLACK; w->color=RED; lrot(rootp, w); w=x>padre->left; } w->color=x->padre->color; x->padre->color = BLACK;

w->left->color = BLACK; rrot(rootp, x>padre); if(esexterno) {x->padre->right=NULL; esexterno=0;} x=*rootp; } } } //Al salir del while: x es la raíz o es rojo. Si es la raíz la pinta negra. x->color=BLACK; //corrige caso con un solo hijo rojo } 2.7 Referencias bibliográficas

Bibliografía [1] R.Bayer, Symmetric binary B-trees, -: Acta Informatica, 1972. [2] ESTRUCTURASITE, «Estructura de datos ll,» WORDPRESS, 10 04 2016. [En línea]. Available: https://estructurasite.wordpress.com/arbol-avl/. [Último acceso: 2017 06 17]. [3] U. Alicante, DLSI, [En línea]. Available: https://rua.ua.es/dspace/bitstream/10045/16037/7/ped-09_10-tema3_5.pdf.