Un árbol rojo-negro es un tipo abstracto de datos, es un árbol binario de búsqueda equilibrado, este árbol se utiliza más que todo para organizar información compuesta por datos comparables (como por ejemplo números enteros), en este árbol las hojas (es decir los hijos de los nodos los cuales no tienen dato) no son relevantes y no tienen datos lo que tendrían sería un NULL.
Los arboles rojos-negros intentan mantener su altura o el número de niveles de nodos bajo la raíz tan pequeños como sea posible. Mantener baja la altura se consigue realizando transformaciones en el árbol, con acciones como la rotación y la inserción en el árbol.
Propiedades
Todo árbol rojo-negro debe de tener las siguientes propiedades:
1-Todo nodo debe ser negro o rojo.
2- La raíz es de color negro.
3-Todas las hojas son negras y deben llevar como dato NULL.
4-Todo nodo rojo debe tener dos nodos hijos de color negro.
5- Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros.
En estos árboles las operaciones básicas como lo son buscar, insertar y eliminar son de peor tiempo de ejecución que en los demás arboles de búsqueda.
El uso de este árbol se utiliza para la construcción de bloques en otras estructuras de datos que garantizan un peor caso como por ejemplo estructuras de datos utilizadas en geometría computacional.
Operaciones básicas de los árboles rojos-negros
Búsqueda: La búsqueda en este árbol consiste en acceder a la raíz del árbol si el nodo buscado es igual a la raíz la búsqueda se da por concluida pero si el nodo buscado es menor que la raíz se ira al subárbol izquierdo a buscarlo y en el caso de que el nodo buscado sea mayor a la raíz se ira a él subárbol derecho a buscarlo en el caso en que se llegue a una hoja significa que no se encontró el elemento.
Inserción: La operación de inserción comienza insertando el nodo como se haría en cualquier árbol de búsqueda binaria es decir si el nodo a ingresar es menor que la raíz se ira al subárbol izquierdo y así y si es mayor se ira al subárbol derecho y así hasta encontrar su lugar. Pero al hacer esto la propiedad 4 está amenazada debido a que solo se añade un nodo rojo y la propiedad 5 también está amenazada debido a solo por repintar un nodo negro de color rojo o por una rotación.
Eliminación: Para la eliminación en un árbol rojo-negro se hace igual que los demás buscando el nodo a eliminar en el árbol si es menor que la raíz pasa al subárbol izquierdo y si es mayor que la raíz pasa al subárbol derecho, pero se debe tomar en cuenta que:
Si se va a borrar un nodo rojo simplemente se sustituye con su hijo que debe ser de color negro
Cuando el nodo a borrar es negro y su hijo es rojo en este caso al borrar un nodo negro puede romper varias propiedades, pero si repintamos su hijo de color negro no se rompería ninguna propiedad
Rotación: Las rotaciones que se utilizan en el árbol rojo-negro son las mismas que se utilizan en los árboles de búsqueda las cuales son: rotación simple izquierda, rotación simple derecha, rotación doble izquierda, rotación doble derecha, rotación derecha-izquierda, rotación izquierda-derecha.
Ventajas y desventajas de los árboles rojos-negros
Ventajas
-
Todas las operaciones son O(log n).
-
Se mantienen más balanceados que otras estructuras.
-
Permite organizar un listado de números de manera sencilla.
Desventajas
-
Su costo espacial es mayor que el de otros arboles por el uso de nodos centinelas.
-
Su tiempo de ejecución es peor que el de otros arboles de búsqueda.
Referencias
-
Wha, W. (2016, 31 enero). árbol rojo negro. Slideshare. https://es.slideshare.net/whaleejaa/arbol-rojo-negro
-
Bass, J. (2015, 6 noviembre). árbol rojo y negro. Slideshare. https://es.slideshare.net/juanfrosas/arbol-rojo-y-negro-54823358#:%7E:text=Ventajas%20%EF%83%BCTodas%20las%20operaciones,el%20uso%20de%20nodos%20centinelas
-
Colaboradores de Wikipedia. (2020b, noviembre 21). Árbol rojo-negro. Wikipedia, la enciclopedia libre. https://es.wikipedia.org/wiki/%C3%81rbol_rojo-negro