Presentacion rojos y negros

Universidad Latina de Costa Rica
Facultad de Tecnologías de la Información y Comunicaciones
Escuela de Ingeniería en Sistemas Informáticos









Arboles Rojo Negro
Organización de Archivos y Estructuras de Datos
Grupo 3 V-S

San José, 17 de diciembre de 2011
Tabla de Contenidos

Introducción

La estructura original fue creada por Rudolf Bayer, profesor eméritode Informática en la Universidad Técnica de Munich, que le dio el nombre de “árboles-B binarios simétricos”, es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica; hacemos referencia a lo que se conoce como “Un árbol rojo- negro”.
El propósito principal de este proyecto es investigar a profundidad, el funcionamiento del árbol binariode búsqueda citado anteriormente, una estructura de datos utilizada en informática y ciencias de la computación. Explicaremos su estructura, características fundamentales, reglas por las que rige su funcionamiento, ventajas y desventajas en rendimiento, algoritmos de inserción, consulta y eliminación en un lenguaje de programación, entre otras cosas.
Para facilitar este aprendizaje aportaremosejemplos de los procedimientos a los que debe someterse la estructura al momento de realizar una operación, acompañado de apoyo visual con el fin de alcanzar el entendimiento correcto y una comprensión ideal del tema en cuestión.

Árbol Rojo-Negro

Un árbol rojo-negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado

Como se puede observar en la imagen,cada nodo almacena un bit adicional de información que podemos llamar “color”, el cual puede ser rojo o negro. Sobre este atributo color se aplican restricciones que resultan en un árbol en el que ningún camino de la raíz a una hoja es más de dos veces más largo que cualquier otro, lo cual significa que el árbol es balanceado. Cada nodo debe contener como atributos: color, información contenida(como por ejemplo números), hijo izquierdo, hijo derecho y padre. Los nodos distintos a las hojas (Nulos) son denominados nodos internos del árbol, y las hojas y el padre de la raíz son conocidos como nodos externos.
En este tipo de estructura las hojas no son relevantes y no contienen datos, al momento de implementarse a un lenguaje de programación, para ahorrar memoria, un único nodo hace denodo hoja para todas las ramas, a este nodo se le conoce como “Nodo Centinela”, el cual veremos más adelante.

Todo árbol rojo-negro debe satisfacer las siguientes propiedades:
1. Todo nodo es o bien rojo o bien negro.
2. La raíz siempre debe ser negra
3. Todas las hojas son negras (hijos nulos)
4. Los hijos de todo nodo rojo son negros (también llamada “Propiedad del rojo”)
5.Para cada nodo, todas las rutas de un nodo a las hojas contienen el mismo número (también llamada “Propiedad del camino”), al número de nodos negros de cada camino se le denomina “Altura negra del árbol”.

La distancia que hay desde la raíz hasta las hojas (nodos NULL) del nodo con número “1” es 2, que es exactamente igual a la distancia que hay desde el nodo con número “8” hasta las hojas delnodo con número “6”, y así para cada nodo de la estructura
La distancia que hay desde la raíz hasta las hojas (nodos NULL) del nodo con número “1” es 2, que es exactamente igual a la distancia que hay desde el nodo con número “8” hasta las hojas del nodo con número “6”, y así para cada nodo de la estructura

Dado que las operaciones básicas como insertar, borrar y encontrar valores tienen unpeor tiempo de búsqueda proporcional a la altura del árbol, esta cota superior de la altura permite a los árboles rojo-negro ser eficientes en el peor caso, de forma contraria a lo que sucede en los árboles binarios de búsqueda.

Usos y ventajas
Como anteriormente fue citado, los árboles rojo-negro ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda. No es...