logo

TechCodeview

Introducción al árbol rojo-negro

Árboles de búsqueda binaria son fundamentales estructura de datos, pero su rendimiento puede verse afectado si el árbol se desequilibra. árboles negros rojos son un tipo de árbol de búsqueda binario equilibrado que utilizan un conjunto de reglas para mantener el equilibrio, asegurando una complejidad de tiempo logarítmica para operaciones como inserción, eliminación y búsqueda , independientemente de la forma inicial del árbol. árboles negros rojos son autoequilibrados y utilizan un esquema simple de codificación de colores para ajustar el árbol después de cada modificación.

Árbol rojo-negro



Tabla de contenidos

¿Qué es un árbol rojo-negro?

A Árbol rojo-negro es un autoequilibrio árbol de búsqueda binaria donde cada nodo tiene un atributo adicional: un color, que puede ser rojo o negro . El objetivo principal de estos árboles es mantener el equilibrio durante las inserciones y eliminaciones, asegurando una recuperación y manipulación eficiente de los datos.

Propiedades de los árboles rojo-negros

A Árbol rojo-negro tener las siguientes propiedades:



  1. Color de nodo : Cada nodo es rojo o negro .
  2. Propiedad raíz : La raíz del árbol es siempre negro .
  3. Propiedad roja : Los nodos rojos no pueden tener hijos rojos (no hay dos nodos rojos consecutivos en ninguna ruta).
  4. Propiedad negra : Cada camino desde un nodo hasta sus nodos nulos descendientes (hojas) tiene el mismo número de negro nodos.
  5. Propiedad de la hoja : Todas las hojas (nodos NIL) son negro .

Estas propiedades garantizan que el camino más largo desde la raíz hasta cualquier hoja no sea más del doble que el camino más corto, manteniendo el equilibrio y el rendimiento eficiente del árbol.

Ejemplo de árbol rojo-negro

El Árbol rojo-negro correcto La imagen de arriba garantiza que cada ruta desde la raíz hasta un nodo hoja tenga la misma cantidad de nodos negros. En este caso, hay uno (excluyendo el nodo raíz).



matriz de cadenas en programación c

El Árbol negro rojo incorrecto no sigue las propiedades rojo-negro como dos nodos rojos son adyacentes entre sí. Otro problema es que una de las rutas a un nodo hoja tiene cero nodos negros, mientras que las otras dos contienen un nodo negro.

¿Por qué árboles rojo-negros?

La mayoría de las operaciones BST (por ejemplo, buscar, máximo, mínimo, insertar, eliminar, etc.) toman Oh) tiempo donde h es la altura del hora estándar del este . El costo de estas operaciones puede llegar a ser En) por un sesgado Árbol binario. Si nos aseguramos de que la altura del árbol se mantenga O(log n) después de cada inserción y eliminación, entonces podemos garantizar un límite superior de O(log n) para todas estas operaciones. La altura de un árbol Rojo-Negro es siempre O(log n) donde n es el número de nodos del árbol.

Sr. No.AlgoritmoComplejidad del tiempo
1.BuscarO(log n)
2.InsertarO(log n)
3.BorrarO(log n)

Comparar con Árbol AVL :

Los árboles AVL están más equilibrados en comparación con los árboles Rojo-Negro, pero pueden provocar más rotaciones durante la inserción y eliminación. Entonces, si su aplicación implica inserciones y eliminaciones frecuentes, entonces se deben preferir los árboles Rojo-Negro. Y si las inserciones y eliminaciones son menos frecuentes y la búsqueda es una operación más frecuente, entonces árbol AVL debe preferirse al árbol rojo-negro.

¿Cómo garantiza el equilibrio un árbol rojo-negro?

Un ejemplo sencillo para entender el equilibrio es que no es posible una cadena de 3 nodos en el árbol Rojo-Negro. Podemos probar cualquier combinación de colores y ver si todos violan la propiedad del árbol Rojo-Negro.

Estructura adecuada del árbol rojo-negro de tres nodos.

abstracción en java

Puntos interesantes sobre el Árbol Rojo-Negro:

  • El negro La altura del árbol rojo-negro es el número de nodos negros en un camino desde el nodo raíz hasta un nodo hoja. Los nudos de las hojas también se cuentan como negro nodos. Entonces, un árbol de altura rojo-negro. h tiene altura negro>= h/2 .
  • Altura de un árbol rojo-negro con norte nodos es h<= 2 registro 2 (n+1) .
  • Todas las hojas (NIL) son negro .
  • El negro La profundidad de un nodo se define como la cantidad de nodos negros desde la raíz hasta ese nodo, es decir, la cantidad de ancestros negros.

Operaciones básicas en el árbol rojo-negro:

Las operaciones básicas en un Árbol Rojo-Negro incluyen:

  1. Inserción
  2. Buscar
  3. Supresión
  4. Rotación

1. Inserción

Insertar un nuevo nodo en un árbol Rojo-Negro implica un proceso de dos pasos: realizar un estándar Inserción de árbol de búsqueda binaria (BST) , seguido de la corrección de cualquier infracción de las propiedades Rojo-Negro.

Pasos de inserción

  1. Inserto BST : Inserte el nuevo nodo como en un BST estándar.
  2. Corregir violaciones :
    • Si el padre del nuevo nodo es negro , no se viola ninguna propiedad.
    • Si el padre es rojo , el árbol podría violar la propiedad roja y requerir correcciones.

Corrección de infracciones durante la inserción

Después de insertar el nuevo nodo como rojo nodo, podemos encontrar varios casos dependiendo de los colores del padre y del tío del nodo (el hermano del padre):

  • Caso 1: El tío es rojo : Vuelva a colorear al padre y al tío para negro , y el abuelo a rojo . Luego suba en el árbol para comprobar si hay más infracciones.
  • Caso 2: El tío es negro :
    • Subcaso 2.1: El nodo es un hijo derecho : Realiza una rotación hacia la izquierda en el padre.
    • Subcaso 2.2: El nodo es un hijo izquierdo : Realice una rotación hacia la derecha en el abuelo y cambie el color apropiadamente.

2. Buscando

Buscar un nodo en un árbol rojo-negro es similar a buscar en un árbol estándar Árbol de búsqueda binaria (BST) . La operación de búsqueda sigue un camino sencillo desde el raíz a un hoja , comparando el valor objetivo con el valor del nodo actual y moviéndose hacia la izquierda o hacia la derecha en consecuencia.

Pasos de búsqueda

  1. Comience desde la raíz : comience la búsqueda en el nodo raíz.
  2. Atraviesa el árbol :
    • Si el valor objetivo es igual al valor del nodo actual, se encuentra el nodo.
    • Si el valor objetivo es menor que el valor del nodo actual, muévase al hijo izquierdo.
    • Si el valor objetivo es mayor que el valor del nodo actual, pase al hijo derecho.
  3. Repetir : Continúe este proceso hasta que se encuentre el valor objetivo o se alcance un nodo NIL (lo que indica que el valor no está presente en el árbol).

3. Supresión

Eliminar un nodo de un árbol rojo-negro también implica un proceso de dos pasos: realizar la eliminación de BST y luego corregir cualquier infracción que surja.

Pasos de eliminación

  1. Eliminación de BST : elimine el nodo utilizando las reglas estándar de BST.
  2. Arreglar doble negro :
    • Si se elimina un nodo negro, puede surgir una condición de doble negro, que requiere soluciones específicas.

Corregir infracciones durante la eliminación

Cuando se elimina un nodo negro, manejamos el problema del doble negro según el color del hermano y los colores de sus hijos:

  • Caso 1: El hermano es rojo : Gire el padre y cambie el color del hermano y del padre.
  • Caso 2: El hermano es negro :
    • Subcaso 2.1: Los hijos de un hermano son negros : Vuelva a colorear al hermano y propague el doble negro hacia arriba.
    • Subcaso 2.2: Al menos uno de los hijos del hermano es rojo :
      • Si el hijo lejano del hermano es rojo : Realice una rotación en el padre y el hermano, y cambie el color apropiadamente.
      • Si el hijo cercano del hermano es rojo : Gire al hermano y a su hijo, luego maneje como se indica arriba.

4. Rotación

Las rotaciones son operaciones fundamentales para mantener la estructura equilibrada de un árbol rojo-negro (RBT). Ayudan a preservar las propiedades del árbol, asegurando que el camino más largo desde la raíz hasta cualquier hoja no sea más del doble de la longitud del camino más corto. Las rotaciones son de dos tipos: rotaciones a la izquierda y rotaciones a la derecha.

1. Rotación a la izquierda

Una rotación hacia la izquierda en el nodo 𝑥 X se mueve 𝑥 X hacia abajo a la izquierda y su hijo derecho 𝑦 y hasta tomar 𝑥 X El lugar.

Visualización de rotación izquierda 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Pasos de rotación hacia la izquierda:

  1. Colocar y ser el hijo adecuado de X .
  2. Mover y el subárbol izquierdo a X El subárbol derecho.
  3. Actualizar el padre de X y y .
  4. Actualizar X el padre para señalar y en lugar de X .
  5. Colocar y El niño dejado para X .
  6. Actualizar X el padre de y .

Pseudocódigo de rotación a la izquierda:

Rotación izquierda 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->bien;  x->derecha = y->izquierda;  if (y->izquierda! = NIL) { y->izquierda->padre = x;  } y->padre = x->padre;  if (x->parent == nullptr) { raíz = y;  } else if (x == x->padre->izquierda) { x->padre->izquierda = y;  } else { x->padre->derecha = y;  } y->izquierda = x;  x->padre = y; }>

2. Rotación a la derecha

Una rotación hacia la derecha en el nodo 𝑥 X se mueve 𝑥 X hacia abajo a la derecha y su hijo izquierdo 𝑦 y hasta tomar 𝑥 X El lugar.

Visualización de la rotación a la derecha: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Pasos de rotación a la derecha:

  1. Colocar y ser el hijo izquierdo de X .
  2. Mover y el subárbol derecho a X El subárbol izquierdo.
  3. Actualizar el padre de X y y .
  4. Actualizar X el padre para señalar y en lugar de X .
  5. Colocar y El hijo adecuado para X .
  6. Actualizar X el padre de y .

Pseudocódigo de rotación a la derecha:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->izquierda;  x->izquierda = y->derecha;  if (y->derecha! = NIL) { y->derecha->padre = x;  } y->padre = x->padre;  if (x->parent == nullptr) { raíz = y;  } else if (x == x->padre->derecha) { x->padre->derecha = y;  } else { x->padre->izquierda = y;  } y->derecha = x;  x->padre = y; }>

¿Cuándo realizar rotaciones?

Las rotaciones en árboles rojo-negro generalmente se realizan durante las inserciones y eliminaciones para mantener las propiedades del árbol. A continuación se detallan los escenarios para las rotaciones:

1. Corregir infracciones después de la inserción

Cuando se inserta un nuevo nodo, siempre aparece en color rojo. Esto puede crear violaciones de las propiedades del Árbol Rojo-Negro, específicamente:

  • La raíz debe ser negro .
  • Rojo los nodos no pueden tener rojo niños.

Análisis de caso para la fijación de inserciones:

  • Caso 1: Recoloración y propagación hacia arriba
    • Si el padre y el tío del nuevo nodo son ambos rojo , cambia el color del padre y del tío para negro , y el abuelo a rojo . Luego, aplique recursivamente la corrección al abuelo.
  • Caso 2: Rotación y Recoloración
    • Si el tío del nuevo nodo es negro y el nuevo nodo es el hijo derecho de un hijo izquierdo (o viceversa), realice una rotación para mover el nuevo nodo hacia arriba y alinearlo.
    • Si el tío del nuevo nodo es negro y el nuevo nodo es el hijo izquierdo de un hijo izquierdo (o el derecho de un hijo derecho), realice una rotación y cambie el color del padre y del abuelo para corregir la infracción.

2. Corregir infracciones después de la eliminación

Después de la eliminación, es posible que sea necesario arreglar el árbol para restaurar las propiedades:

  • Cuando se elimina un nodo negro o se reemplaza un nodo rojo por un nodo negro, puede surgir una situación de doble negro.

Análisis de casos para corregir eliminaciones:

  • Caso 1: El hermano es rojo
    • Vuelva a colorear al hermano y al padre y realice una rotación.
  • Caso 2: Hermano es negro y tiene hijos negros
    • Vuelva a colorear al hermano a rojo y pase el problema al padre.
  • Caso 3: El hermano es negro y tiene al menos un hijo rojo
    • Gire y cambie el color para solucionar el problema del doble negro.

Implementación del árbol rojo-negro:

A continuación se muestra una implementación detallada de un árbol rojo-negro que incluye funciones de inserción, búsqueda y rotación:

C++ 
#include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->bien;  x->derecha = y->izquierda;  if (y->izquierda! = NIL) { y->izquierda->padre = x;  } y->padre = x->padre;  if (x->parent == nullptr) { raíz = y;  } else if (x == x->padre->izquierda) { x->padre->izquierda = y;  } else { x->padre->derecha = y;  } y->izquierda = x;  x->padre = y;  } // Función de utilidad para realizar la rotación a la derecha void rightRotate(Node* x) { Node* y = x->left;  x->izquierda = y->derecha;  if (y->derecha! = NIL) { y->derecha->padre = x;  } y->padre = x->padre;  if (x->parent == nullptr) { raíz = y;  } else if (x == x->padre->derecha) { x->padre->derecha = y;  } else { x->padre->izquierda = y;  } y->derecha = x;  x->padre = y;  } // Función para arreglar las propiedades del árbol Rojo-Negro después de // inserción void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->padre == k->padre->padre->izquierda) { Nodo* u = k->padre->padre->derecha; // tío if (u->color == 'RED') { k->parent->color = 'BLACK';  u->color = 'NEGRO';  k->padre->padre->color = 'RED';  k = k->padre->padre;  } else { if (k == k->padre->derecha) { k = k->padre;  Rotación izquierda(k);  } k->padre->color = 'NEGRO';  k->padre->padre->color = 'RED';  rightRotate(k->padre->padre);  } } else { Nodo* u = k->padre->padre->izquierda; // tío if (u->color == 'RED') { k->parent->color = 'BLACK';  u->color = 'NEGRO';  k->padre->padre->color = 'RED';  k = k->padre->padre;  } else { if (k == k->padre->izquierda) { k = k->padre;  rotación derecha(k);  } k->padre->color = 'NEGRO';  k->padre->padre->color = 'RED';  leftRotate(k->padre->padre);  } } } raíz->color = 'NEGRO';  } // Función auxiliar de recorrido en orden void inorderHelper(Nodo* nodo) { if (nodo!= NIL) { inorderHelper(nodo->izquierda);  corte<< node->datos<< ' ';  inorderHelper(node->bien);  } } // Función auxiliar de búsqueda Nodo* searchHelper(Nodo* nodo, int datos) { if (nodo == NIL || datos == nodo->datos) { return nodo;  } si (datos< node->datos) { return searchHelper(nodo->izquierda, datos);  } return searchHelper(nodo->derecha, datos);  } public: // Constructor RedBlackTree() { NIL = nuevo Nodo(0);  NULO->color = 'NEGRO';  NULO->izquierda = NULO->derecha = NULO;  raíz = NULO;  } // Insertar función void insert(int data) { Nodo* nuevo_nodo = nuevo Nodo(datos);  nuevo_nodo->izquierda = NIL;  nuevo_nodo->derecha = NIL;  Nodo* padre = nullptr;  Nodo* actual = raíz;  // BST inserta mientras (actual! = NIL) { padre = actual;  si (nuevo_nodo->datos< current->datos) { actual = actual->izquierda;  } else {actual = actual->derecha;  } } nuevo_nodo->padre = padre;  if (padre == nullptr) { raíz = nuevo_nodo;  } más si (nuevo_nodo->datos< parent->datos) { padre->izquierda = nuevo_nodo;  } else { padre->derecho = nuevo_nodo;  } if (nuevo_nodo->padre == nullptr) { nuevo_nodo->color = 'NEGRO';  devolver;  } if (nuevo_nodo->padre->padre == nullptr) { return;  } fixInsert(nuevo_nodo);  } // recorrido en orden void inorder() { inorderHelper(root); } // Función de búsqueda Nodo* búsqueda(int datos) { return searchHelper(raíz, datos);  } }; int principal() { ÁrbolNegroRojo rbt;  // Insertando elementos rbt.insert(10);  rbt.insertar(20);  rbt.insertar(30);  rbt.insertar(15);  // recorrido transversal en orden<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

Ventajas de los árboles rojo-negros:

  • Equilibrado: Los árboles rojo-negro se autoequilibran, lo que significa que mantienen automáticamente un equilibrio entre las alturas de los subárboles izquierdo y derecho. Esto garantiza que las operaciones de búsqueda, inserción y eliminación tomen un tiempo O(log n) en el peor de los casos.
  • Búsqueda, inserción y eliminación eficientes: Debido a su estructura equilibrada, los árboles rojo-negros ofrecen operaciones eficientes. La búsqueda, la inserción y la eliminación toman O(log n) tiempo en el peor de los casos.
  • Sencillo de implementar: Las reglas para mantener las propiedades del Árbol Rojo-Negro son relativamente simples y directas de implementar.
  • Ampliamente utilizado: Los árboles rojo-negro son una opción popular para implementar diversas estructuras de datos, como mapas, conjuntos y colas de prioridad.

Desventajas de los árboles rojo-negros:

  • Más complejo que otros árboles equilibrados: En comparación con árboles equilibrados más simples como los árboles AVL, los árboles Rojo-Negro tienen reglas de inserción y eliminación más complejas.
  • Gastos generales constantes: Mantener las propiedades del árbol rojo-negro agrega una pequeña sobrecarga a cada operación de inserción y eliminación.
  • No es óptimo para todos los casos de uso: Si bien son eficientes para la mayoría de las operaciones, los árboles rojo-negro pueden no ser la mejor opción para aplicaciones donde se requieren inserciones y eliminaciones frecuentes, ya que la sobrecarga constante puede volverse significativa.

Aplicaciones de los árboles rojo-negros:

  • Implementación de mapas y conjuntos: Los árboles rojo-negro se utilizan a menudo para implementar mapas y conjuntos, donde la búsqueda, inserción y eliminación eficientes son cruciales.
  • Colas prioritarias: Los árboles rojo-negro se pueden utilizar para implementar colas de prioridad, donde los elementos se ordenan según su prioridad.
  • Sistemas de archivos: Los árboles rojo-negro se utilizan en algunos sistemas de archivos para administrar estructuras de archivos y directorios.
  • Bases de datos en memoria: Los árboles rojo-negro a veces se utilizan en bases de datos en memoria para almacenar y recuperar datos de manera eficiente.
  • Desarrollo de gráficos y juegos: Los árboles rojo-negro se pueden utilizar en gráficos y juegos. desarrollo para tareas como detección de colisiones y búsqueda de rutas.

Preguntas frecuentes (FAQ) sobre el árbol rojo-negro:

1. ¿Qué es un árbol rojo-negro?

Un árbol rojo-negro es un árbol de búsqueda binario autoequilibrado que mantiene un equilibrio entre las alturas de sus subárboles izquierdo y derecho. Esto garantiza que las operaciones de búsqueda, inserción y eliminación tomen un tiempo O(log n) en el peor de los casos. Los árboles rojo-negro se utilizan ampliamente en diversas aplicaciones donde se requieren estructuras de datos eficientes.

2. ¿Cómo mantiene su equilibrio un Árbol Rojo-Negro?

Los árboles rojo-negro mantienen su equilibrio al imponer reglas específicas sobre los colores de los nodos (ROJO o NEGRO) y las relaciones entre ellos. Estas reglas aseguran que el árbol permanezca equilibrado y que la diferencia de altura entre los subárboles izquierdo y derecho sea como máximo 1.

botón central css

3. ¿Cuáles son las ventajas de utilizar un Árbol Rojo-Negro?

  • Equilibrado: Los árboles rojo-negro se autoequilibran y garantizan operaciones eficientes de búsqueda, inserción y eliminación.
  • Eficiente: Ofrecen una complejidad temporal O (log n) para la mayoría de las operaciones.
  • Sencillo de implementar: Las reglas para mantener las propiedades del Árbol Rojo-Negro son relativamente sencillas.
  • Ampliamente utilizado: Son una opción popular para implementar diversas estructuras de datos y algoritmos.

4. ¿Cuáles son las desventajas de utilizar un Árbol Rojo-Negro?

  • En comparación con árboles equilibrados más simples como los árboles AVL, los árboles Rojo-Negro tienen reglas de inserción y eliminación más complejas.
  • Mantener las propiedades del árbol rojo-negro agrega una pequeña sobrecarga a cada operación de inserción y eliminación.
  • Para aplicaciones con inserciones y eliminaciones frecuentes, otras estructuras de árbol equilibradas podrían ser más adecuadas.

5. ¿Cuáles son algunas aplicaciones comunes de los árboles rojo-negros?

  • Implementación de mapas y conjuntos.
  • Colas prioritarias
  • Sistemas de archivos
  • Bases de datos en memoria
  • Desarrollo de gráficos y juegos (detección de colisiones, búsqueda de rutas)
  • Definición y significado del árbol rojo-negro en DSA
  • Árboles de búsqueda binaria autoequilibrados
  • Árbol Rojo Negro vs Árbol AVL
  • ¿Cuál es la diferencia entre montón y árbol rojo-negro?
  • Inserción en árbol rojo-negro
  • Eliminación en el árbol rojo-negro
  • Árboles rojo-negros | Inserción de arriba hacia abajo