Arboles Rojo Negro

12
Estructura de Datos
ARBOL ROJO-NEGRO
MUÑOZ Lorena


INTRODUCCION

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.
Una estructura de datos define la organización e interrelación de éstos y un conjunto de operacionesque se pueden realizar sobre ellos. Las operaciones básicas son:
INSRTAR: adicionar un nuevo valor a la estructura.
ELIMINAR: borrar un valor de la estructura.
BUSCAR: encontrar un determinado valor en la estructura para realizar una operación con este valor.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De estaforma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

En este trabajo vamos a analizar la estructura de Árbol Rojo y negro y sus operaciones básicas (insertar, eliminar y buscar); así también se presentaran ventajas y desventajas de la misma y cuál es el uso que se le da.ARBOL ROJO-NEGRO
Un árbol rojo-negro es un tipo abstracto de datos. Es un tipo de árbol binario de búsqueda que tiene la característica de ser balanceado.
La estructura original fue creada por Rudolf Bayer en1972, que le dio el nombre de “árboles-binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas yRobert Sedgewick realizado en1978.
DEFINICIONES
* Un árbolse considera balaceado si todas las hojas del árbol se encuentran en el mismo nivel o, como máximo, con un nivel de diferencia unas respecto de las otras. Gracias a esta característica el tiempo de las operaciones básicas del árbol rojo-negro es de O(log n) en el peor de los casos, donde  n es el número de elementos del árbol.
* La altura negra de árbol es el número de nodos negros que hay encualquier camino de él a una hoja que desciende del mismo( partiendo de la raíz).
* Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
* Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
* Nodo raíz: nodo que no tiene padre.
* Nodo hola: nodo que no tiene hijos y eneste caso su valor es nulo.
PROPIEDADES
* Todo nodo del árbol es rojo o negro.
* La raíz siempre es negra.
* Toda hoja es negra (La hojas son los hijos que no contienen datos.).
* Los hijos de todo nodo rojo, son negros. No hay dos nodos rojos adyacentes.
* Cualquier camino desde un nodo hacia una hora contiene el mismo número de nodos negros.

Estas propiedades hacen que unárbol rojo y negro sea balaceado

En muchas presentaciones de estructuras de arbol de datos, es posible para un nodo tener solo un hijo y las hojas contienen información. Es posible presentar los árboles rojo-negros en este paradigma, pero cambian algunas de las propiedades y se complican los algoritmos. Por esta razón, generalmente para la representación del árbol Rojo-Negro se utilizan “hojasnulas”, que no contienen información y simplemente sirven para indicar dónde el árbol acaba(los límites del árbol).Para representar las hojas nulas del árbol se utiliza un nodo llamado centinela.

ESTRUCTURA DEL NODO
El nodo de un árbol Rojo negro contiene la siguiente información: hijo izquierdo, hijo derecho, padre, color y elemento. Si un hijo o el padre de un nodo no existen, el apuntadorcorrespondiente contiene el valor NULO. Se considera que todas las hojas nulas son de color es negro.
NodoRb izq; Hijo Izquierda
NodoRb der; Hijo derecho
NodoRb padre
Color, 0: negro 1: rojo
Elemento comprable.

public class NodoRb
{
public NodoRb izq; //Hijo Izquierda
public NodoRb der; //Hijo derecho
public NodoRb padre;
public byte color;// 0: negro 1:rojo...