Árboles rojo-negro

Balancea un BST con colores en los nodos + cuatro reglas. El árbol balanceado que vive dentro de casi todos los mapas de la librería estándar.

Cuatro reglas = un presupuesto de balance

1. Cada nodo es rojo o negro
2. La raíz es negra
3. Nunca dos rojos seguidos
4. Misma altura negra en todo camino de la raíz a una hoja

→ camino más largo ≤ 2× el más corto → altura ≤ 2·log₂(n+1)

Mira a los colores balancearlo

Los nodos nuevos llegan en rojo; se recolorea/reestructura para respetar las reglas. Inserta 1..7 ordenado → balanceado, nunca una cadena.

Balanceado, un toque más alto que AVL

Con 100000: altura RB 22 (cota 33), AVL fue 17, BST simple 100000. 68× más rápido con n=8000.

Por qué las librerías eligen rojo-negro

• Balance más relajado → menos rotaciones por actualización que AVL
• Un poco más alto, pero más barato de mantener bajo lecturas Y escrituras
• Un árbol rojo-negro es un árbol 2-3-4 (un árbol B de orden 4) disfrazado

Para llevar

El árbol balanceado pragmático: O(log n) garantizado, actualizaciones baratas, en todos lados. Sigue: el heap binario — renuncia al orden de búsqueda para agarrar el máximo más rápido.