Árbol Rojo-Negro

Árbol Rojo-Negro

Un árbol es un tipo abstracto de datos que define jerarquías,mediante relaciones entre objetos de tipo nodo este esta compuesto de una raíz, nodos con de tipo padre,hijo o hoja y la unión entre ellos se les llama rama.

Un árbol rojo-negro es una árbol binario de búsqueda que con la característica que sus nodos tienen un atributos que puede ser color negro o rojo, este con el fin de poder optimizar los métodos de lectura y escritura.

Propiedades

Los arboles rojo-negro cumplen las siguientes propiedades:

• Todo nodo es o bien rojo o bien negro.
• La raiz siempre sera negra.
• Todas las hojas nulas son negras.
• Todo los nodo rojo debe tener dos nodos hijos negros.
• Cada camio desde un nodo dado a sus hojas descendientes contiene el mismo numero de nodos negros.

Usos y Ventajas

Este es muy valioso en programación funcional donde son una de las estructuras de datos persistentes mas comunes utilizadas en la construcción de arrays asociativos y conjuntos que pueden retener versiones precias tras mutaciones.

Son isometricos a los arboles 2-3-4. En otras palabras,para cada árbol 2-3-4, existe un árbol correspondiente rojo-negro con los datos en el mismo orden. la inserción y el borrado 2-3-4 son también equivalentes a los cambios de colores y las rotaciones en los arboles rojo y negro. Esto los hace ser una herramienta útil para la comprensión del funcionamiento de los arboles rojo-negro y por eso muchos textos introducidos sobre algoritmos presentan los arboles 2-3-4 justo antes de los arboles rojo-negro, aunque frecuentemente no sean utilizados en la practica.

Rotaciones

Para conservar las propiedades que debe cumplir todo árbol rojo-negro, en ciertos casos de la inserción y la eliminación sera necesario reestructurar el árbol, si bien no debe perderse la ordenación relativa de los nodos. Para ello, se llevan a cabo una o varias rotaciones, que no son mas que re estructuraciones en las relaciones padre-hijo.