Algoritmos y Estructura de Datos

Temas

Árboles Red Black y principales operaciones


Los árboles rojinegros son una variante de los árboles binarios de búsqueda que se utilizan para mantener el árbol equilibrado y garantizar un rendimiento óptimo en las operaciones de inserción, eliminación y búsqueda. Un árbol rojinegro cumple con las siguientes propiedades:

  • Todos los nodos son rojos o negros.
  • La raíz del árbol es siempre negra.
  • Todos los hijos null de un nodo son siempre negros.
  • Si un nodo es rojo, sus hijos deben ser negros.
  • En cualquier camino desde un nodo hasta un nodo null, el número de nodos negros debe ser el mismo.

    • Para mantener estas propiedades y garantizar que el árbol siempre esté equilibrado, se realizan rotaciones y se cambian los colores de los nodos cuando se insertan o eliminan elementos del árbol. Esto permite que el árbol siempre tenga una altura logarítmica en función del número de nodos, lo que significa que las operaciones de inserción, eliminación y búsqueda tienen una complejidad de O(log n).

                        
      
                        
    1. #include <iostream>
      2. 

    2. 

    3. const bool RED = true;
      4. 

    4. const bool BLACK = false;
      5. 

    5. 

    6. struct Node {
      7. 

    7.   int data;
      8. 

    8.   bool color;
      9. 

    9.   Node *left, *right, *parent;
      10. 

    10. 

    11.   Node(int data) : data(data) {
      12. 

    12.     color = RED;
      13. 

    13.     left = right = parent = nullptr;
      14. 

    14.   }
      15. 

    15. };
      16. 

    16. 

    17. class RedBlackTree {
      18. 

    18. private:
      19. 

    19.   Node *root;
      20. 

    20.   Node *nil;
      21. 

    21. 

    22. public:
      23. 

    23.   RedBlackTree() {
      24. 

    24.     nil = new Node(0);
      25. 

    25.     nil->color = BLACK;
      26. 

    26.     nil->left = nil->right = nil->parent = nil;
      27. 

    27.     root = nil;
      28. 

    28.   }
      29. 

    29. 

    30.   void LeftRotate(Node *&, Node *&);
      31. 

    31.   void RightRotate(Node *&, Node *&);
      32. 

    32.   void InsertFixup(Node *&, Node *&);
      33. 

    33.   void Insert(Node *&, Node *&, int);
      34. 

    34.   void Inorder(Node *&);
      35. 

    35.   void LevelOrder(Node *&);
      36. 

    36. };
      37.
    Inserción:
  • Creamos un nuevo nodo con la clave que queremos insertar y lo insertamos en el árbol como lo haríamos en un árbol binario de búsqueda.
  • Luego, corregimos cualquier violación de las propiedades del árbol rojinegro que pueda haberse producido durante la inserción. Esto implica realizar rotaciones y cambiar los colores de los nodos según sea necesario.

    • Eliminación:
  • Buscamos el nodo que queremos eliminar en el árbol. Si no lo encontramos, no hay nada que eliminar.
  • Eliminamos el nodo del árbol como lo haríamos en un árbol binario de búsqueda.
  • Corregimos cualquier violación de las propiedades del árbol rojinegro que pueda haberse producido durante la eliminación. Esto implica realizar rotaciones y cambiar los colores de los nodos según sea necesario.

    • Búsqueda:
  • Comenzamos en la raíz del árbol y comparamos la clave que estamos buscando con la clave del nodo actual.
  • Si son iguales, hemos encontrado el nodo y devolvemos su dirección.
  • Si la clave que estamos buscando es menor que la clave del nodo actual, buscamos en el hijo izquierdo del nodo. Si es mayor, buscamos en el hijo derecho.
  • Si llegamos a un nodo null sin encontrar la clave, significa que la clave no se encuentra en el árbol y devolvemos null.

    • Link de apoyo

  • Introducción al arbol rojinegro
  • Árbol rojinegro

    • Siguiente tema:

    Sement Tree e Interval Tree >>