Árbol Roji-Negro en C
En la categoría de los arboles, como estructura de datos en informática, hay varios tipos de ellos, el árbol
Rojo-Negro se caracteriza por tener los nodos coloreados en rojo y negro, esto para hacer un balanceo (en la operación de insertar)
y asegurarse que ningun camino tiene más del doble de longitud que cualquier otro.
Captura de ejecución del árbol, modo consola:
Utilizando el lenguaje C implementé un árbol roji-negro. El programa lo hice en modo consola, como se ve en la imagen. Lo interesante en este tipo de programas es la necesidad de usar punteros, para poder implementar las características de la estructura. Otro punto importante es el comportamiento de la operación de insercion de nodos en el arbol, cada que se inserta un nodo se debe vigilar que se no se forme un doble rojo, es decir, un nodo rojo hijo de un nodo rojo, si se forma hay que reorganizar el árbol, según sea el caso se puede recolorear el arbol o reestructurarlo.
Casos para remediar un doble rojo (Fuente: apuntes de mi profe de análisis de algorítmos)
- Caso 1, Volver a colorear:
- Caso 2, Volver a colorear:
- Caso 3, Reestructurar:
- Caso 4, Reestructurar:
- Caso 5, Reestructurar -> lleva al caso 3:
- Caso 6, Reestructurar -> lleva al caso 4:
Código fuente del programa:
/* Compilador: Borland c++ 5.02 _ Octubre del 2006 */ #include <stdio.h> #include <conio.h> #include <string.h> // variables globales struct nodo{ // los nodos del arbol int llave; char color; // donde r es rojo y n es negro struct nodo *izquierdo; struct nodo *derecho; struct nodo *padre; char cadena[32]; }; nodo *inicio; // el inicio del arbol // funciones a utilizar void insercion(int key, char cad[32]); // para insertar un numero en el arbol void solucionarRojoRojo(nodo *node, int h); // para solucionar un hijo rojo en un nodo rojo nodo *buscar(int key); // para buscar un numero en el arbolito void ver(nodo *node, int esp, int h); // ver el arbol int menus(int n_opciones, int x, int y); // para manejar menu con las teclas de las flechas void liberar(nodo *node); // para liberar la memoria cuando salir del programa void main(void){ int opcion, numero; nodo *ayudante; char cadenalocal[32]; inicio=NULL; textbackground(15); do{ clrscr(); fflush(stdin); textcolor(16); cprintf(" Arbol rojo negro\n\r"); cprintf(" Insertar un numero\n\r Buscar un numero\n\r Ver el arbol\n\r Terminar"); opcion=menus(4, 2, 2); switch(opcion){ case 1: gotoxy(4,6), cprintf("teclea el numero a insertar "); scanf("%d",&numero); gotoxy(4,7), cprintf("teclea la cadena a insertar "); scanf("%s",cadenalocal); insercion(numero,cadenalocal); gotoxy(6,9), cprintf("presiona una tecla para continuar..."); break; case 2: gotoxy(4,6), cprintf("teclea el numero a buscar "); scanf("%d",&numero); ayudante=buscar(numero); if(ayudante) cprintf(" Se encontro ese numero su cadena es:\n\r %s",ayudante->cadena); else cprintf(" No se encontro ese numero en el arbol"); cprintf("\n\r presiona una tecla para continuar..."); break; case 3: clrscr(); ver(inicio, 0, 0); cprintf("\n\n\r Presiona una tecla para continuar..."); break; } if(opcion!=4) getch(); }while(opcion!=4); liberar(inicio); } void insercion(int key, char cad[32]){ int ladohijo; nodo *hijo; nodo *ayudante; int bandera; if(!inicio){ // el arbol esta vacio cargando como raiz inicio = new nodo; inicio->llave=key; strcpy(inicio->cadena,cad); inicio->padre=NULL; inicio->izquierdo=NULL; inicio->derecho=NULL; inicio->color='n'; } else{ // el arbol no esta vacio buscando su lugar hijo = new nodo; hijo->llave=key; strcpy(hijo->cadena,cad); hijo->padre=NULL; hijo->izquierdo=NULL; hijo->derecho=NULL; hijo->color='r'; ayudante=inicio; do{ hijo->padre=ayudante, bandera=1; if(key<ayudante->llave){ if(ayudante->izquierdo) ayudante=ayudante->izquierdo; else ayudante->izquierdo=hijo, bandera=0, ladohijo=1; } else{ if(ayudante->derecho) ayudante=ayudante->derecho; else ayudante->derecho=hijo, bandera=0, ladohijo=2; } }while(bandera==1); if(ayudante->color=='r') solucionarRojoRojo(ayudante, ladohijo); } } void solucionarRojoRojo(nodo *node, int h){ int ladohijo; nodo *abuelo; // en node traemos al padre, en h 1 si el hijo rojo es el izquierdo 2 si no nodo *tio; nodo *ayudante; abuelo=node->padre; if(abuelo->izquierdo && abuelo->derecho){ if(node==abuelo->izquierdo) tio=abuelo->derecho; else tio=abuelo->izquierdo; if(tio->color=='r'){ // caso uno y dos tio->color='n'; node->color='n'; if(abuelo!=inicio) abuelo->color='r'; if(abuelo->padre){ ayudante=abuelo->padre; if(ayudante->izquierdo==abuelo) ladohijo=1; else ladohijo=2; if(ayudante->color=='r') solucionarRojoRojo(ayudante, ladohijo); } return; } } if(h==1 && abuelo->izquierdo==node){ // caso tres node->color='n', abuelo->color='r'; ayudante=node->derecho, node->derecho=abuelo, node->padre=abuelo->padre; abuelo->padre=node, abuelo->izquierdo=ayudante; if(ayudante) ayudante->padre=abuelo; if(node->padre){ ayudante=node->padre; if(ayudante->izquierdo==node->derecho) ayudante->izquierdo=node; else ayudante->derecho=node; } else inicio=node; } else if(h==2 && abuelo->derecho==node){ // caso cuatro node->color='n', abuelo->color='r'; ayudante=node->izquierdo, node->izquierdo=abuelo, node->padre=abuelo->padre; abuelo->padre=node, abuelo->derecho=ayudante; if(ayudante) ayudante->padre=abuelo; if(node->padre){ ayudante=node->padre; if(ayudante->izquierdo==node->izquierdo) ayudante->izquierdo=node; else ayudante->derecho=node; } else inicio=node; } else if(h==2 && abuelo->izquierdo==node){ // caso cinco tio=node->derecho, ayudante=tio->izquierdo, abuelo->izquierdo=tio; tio->padre=abuelo, tio->izquierdo=node, node->padre=tio; node->derecho=ayudante; if(ayudante) ayudante->padre=node; solucionarRojoRojo(tio, 1); } else if(h==1 && abuelo->derecho==node){ // caso seis tio=node->izquierdo, ayudante=tio->derecho, abuelo->derecho=tio; tio->padre=abuelo, tio->derecho=node, node->padre=tio; node->izquierdo=ayudante; if(ayudante) ayudante->padre=node; solucionarRojoRojo(tio, 2); } } nodo *buscar(int key){ nodo *ayudante; ayudante=inicio; if(!ayudante) return NULL; do{ if(key==ayudante->llave) return ayudante; else if(key<ayudante->llave) ayudante=ayudante->izquierdo; else if(key>ayudante->llave) ayudante=ayudante->derecho; }while(ayudante); return NULL; } void ver(nodo *node, int esp, int h){ int conter=-1; char descripcion[15]; if(!node && node==inicio){ gotoxy(4,6); cprintf("El arbol esta vacio"); return; } textcolor(10); cprintf("\n\r"); if(node==inicio) strcpy(descripcion,"Raiz"); else if(h==1) strcpy(descripcion,"Hijo izquierdo"); else strcpy(descripcion,"Hijo derecho"); while(++conter<esp) cprintf("%c ",179); cprintf("%c ",195); if(node){ if(node->color=='n') textcolor(16); else textcolor(12); } else textcolor(14); if(node) cprintf("Llave=%d cadena=%s [%s]",node->llave,node->cadena,descripcion); else cprintf("[NULL] [%s]",descripcion); if(node && (node->izquierdo || node->derecho)){ ver(node->izquierdo, esp+1, 1); ver(node->derecho, esp+1, 2); } textcolor(16); } int menus(int n_opciones, int x, int y){ int tecla, tecla2, opc; gotoxy(x,y), cprintf("%c",175), opc=1; do{ tecla=getch(); if(tecla==0){ tecla2=getch(); if(tecla2==80){ // abajo gotoxy(x,opc+(y-1)), cprintf("%c",32), gotoxy(x,(opc<n_opciones?opc+y:y)); cprintf("%c",175), opc=(opc<n_opciones?(opc+1):0); } if(tecla2==72){ // arriba gotoxy(x,opc+(y-1)), cprintf("%c",32), gotoxy(x,(opc>1?(opc+(y-2)):(y+n_opciones-1))); cprintf("%c",175), opc=(opc>1?(opc-1):n_opciones); } } }while(tecla!=13); return opc; } void liberar(nodo *node){ if(node){ if(node->izquierdo) liberar(node->izquierdo); if(node->derecho) liberar(node->derecho); delete node; } }
Comentarios
Publicar un comentario