Estructuras de árbol avanzadas
Después de dominar las estructuras de árbol básicas como el árbol binario y el árbol binario de búsqueda, estamos a punto de entrar en un campo más amplio y eficiente: las estructuras de árbol avanzadas.
Si los árboles básicos son carreteras ordinarias en el mundo de las estructuras de datos, las estructuras de árbol avanzadas son autopistas e intercambiadores cuidadosamente diseñados. Mediante ingeniosas reglas de equilibrio y estrategias de almacenamiento, garantizan un rendimiento excelente incluso cuando el volumen de datos es enorme o las operaciones son frecuentes.
En este capítulo se presentaránÁrbol AVL、Árbol rojo-negro、Árbol ByÁrbol B+Estas cuatro estructuras clásicas de árbol avanzado.
¿Por qué se necesitan estructuras de árbol avanzadas?
Antes de profundizar, hagámonos una pregunta: si ya tenemos el eficiente árbol binario de búsqueda (BST), ¿por qué necesitamos árboles más complejos?
Imagina que tienes una biblioteca y utilizas un BST para almacenar los libros ordenados por título. Si insertas los libros uno a uno en orden alfabético (por ejemplo:A..., B..., C...), el árbol degenerará en una cadena (similar a una lista enlazada). En ese caso, el tiempo de búsqueda de un libro pasará del idealO(log n)a degradarse al peorO(n), lo cual es extremadamente ineficiente.
Figura: diagrama que muestra cómo un árbol binario de búsqueda degenera en una lista enlazada al insertar datos ordenados, lo que provoca una caída del rendimiento de búsqueda.
Las estructuras de árbol avanzadas (árboles autobalanceados) nacieron precisamente para resolver este problema.Al insertar o eliminar nodos, ajustan automáticamente la forma del árbol para mantener su equilibrio, asegurando así que la complejidad temporal de operaciones como búsqueda, inserción y eliminación se mantenga siempre enO(log n)nivel.
Árbol AVL: el guardián del equilibrio de altura
El árbol AVL fue el primer árbol binario de búsqueda autobalanceado inventado, y lleva el nombre de sus inventores, Adelson-Velsky y Landis.
La idea central del árbol AVL es muy sencilla:Para cualquier nodo del árbol, la diferencia de altura entre su subárbol izquierdo y su subárbol derecho no puede superar 1.。
Concepto central: factor de equilibrio
Cada nodo tiene unfactor de equilibrio, cuya fórmula de cálculo es:Factor de equilibrio = altura del subárbol izquierdo - altura del subárbol derechoEn un árbol AVL, el factor de equilibrio de cada nodo solo puede ser -1, 0 o 1.
Desequilibrio y ajuste por rotación
Cuando tras insertar o eliminar un nodo, el factor de equilibrio de algún nodo pasa a ser 2 o -2, el árbol se desequilibra. Para restaurar el equilibrio, el árbol AVL utiliza cuatro operaciones derotaciónpara ajustarlo:
- Rotación a la izquierda: maneja el caso de desequilibrio "derecha-derecha".
- Rotación a la derecha: maneja el caso de desequilibrio "izquierda-izquierda".
- Rotación izquierda-derecha: primero rota a la izquierda y luego a la derecha, maneja el caso de desequilibrio "izquierda-derecha".
- Rotación derecha-izquierda: primero rota a la derecha y luego a la izquierda, maneja el caso de desequilibrio "derecha-izquierda".
Ejemplo
def __init__(self, key):
self.key = key
self.height = 1 # Altura del nodo, inicialmente 1
self.left = None
self.right = None
def get_height(node):
"""Obtiene la altura del nodo (maneja nodos vacíos)"""
return node.height if node else 0
def get_balance_factor(node):
"""Calcula el factor de equilibrio del nodo"""
if not node:
return 0
return get_height(node.left) - get_height(node.right)
def right_rotate(y):
"""
Realiza una rotación a la derecha sobre el subárbol con raíz en y
y x
/ \ / \
x T4 Rotación a la derecha (y) z y
/ \ - - - - - - - -> / \ / \
z T3 T1 T2 T3 T4
/ \
T1 T2
"""
x = y.left
T3 = x.right
# Ejecuta la rotación
x.right = y
y.left = T3
# Actualiza las alturas (primero debe actualizarse la altura de y, luego la de x)
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
# Devuelve el nuevo nodo raíz
return x
# La función de rotación a la izquierda es simétrica a la de la derecha; aquí se omite la implementación detallada
def left_rotate(x):
"""Realiza una rotación a la izquierda sobre el subárbol con raíz en x (la lógica es simétrica a la rotación a la derecha)"""
pass
Resumen de las características del árbol AVL
| Característica | Descripción |
|---|---|
| Equilibrio estricto | La condición de equilibrio es estricta (diferencia de altura ≤ 1), la altura del árbol es la más cercana a log n y el rendimiento de búsqueda es excelente. |
| Ajustes frecuentes | Tras una inserción/eliminación, pueden ser necesarias múltiples rotaciones de abajo hacia arriba para restaurar el equilibrio. |
| Escenarios de aplicación | Adecuado paraescenarios con muchas consultas y pocas inserciones/eliminaciones, como la capa intermedia de los índices de bases de datos o las tablas de búsqueda en memoria. |
Árbol rojo-negro: el rey de la práctica en ingeniería
El árbol rojo-negro es otro árbol binario de búsqueda autobalanceado que sobre la base del árbol AVL hace algunas "concesiones". No busca el equilibrio absoluto como el árbol AVL, sino que garantiza un equilibrio aproximado mediante un conjunto de reglas más flexibles, reduciendo así el número de rotaciones durante la inserción/eliminación y logrando un mejor efecto de práctica de ingeniería en el rendimiento general. El de JavaTreeMap、TreeSety el de C++ STLmap、setambos usan árboles rojo-negros en su implementación subyacente.
Las cinco reglas fundamentales del árbol rojo-negro
El árbol rojo-negro mantiene el equilibrio asignando a cada nodo un atributo de color (rojo o negro) y cumpliendo las siguientes reglas:
- Cada nodo es rojo o negro.
- El nodo raíz es negro.。
- Todos los nodos hoja (nodos vacíos NIL) son negros.
- Los dos hijos de un nodo rojo deben ser negros.(es decir, no puede haber nodos rojos consecutivos).
- Todos los caminos desde un nodo dado hasta cada uno de sus nodos hoja contienenel mismo númerode nodos negros.
Las reglas 4 y 5 son clave para el equilibrio del árbol rojo-negro. La regla 5 garantiza que ningún camino sea más del doble de largo que otro, logrando así un equilibrio aproximado.
Estrategia de ajuste tras la inserción
Al insertar un nuevo nodo, siempre lo coloreamos primero derojo(para evitar violar la regla 5). Si esto causa un conflicto (principalmente violación de la regla 2 o la regla 4), es necesario ajustarlo mediantecambio de coloryy rotación.La idea central del ajuste es "subir" el conflicto (rojo) continuamente hacia la raíz del árbol hasta que pueda resolverse mediante cambio de color o rotación.
Ejemplo
RED = "RED"
BLACK = "BLACK"
def __init__(self, key):
self.key = key
self.color = self.RED # El nuevo nodo se inicializa en rojo
self.left = None
self.right = None
self.parent = None # El árbol rojo-negro necesita un puntero al nodo padre
def insert_fixup(tree, node):
"""Repara las propiedades del árbol rojo-negro después de la inserción (descripción lógica simplificada)"""
while node.parent and node.parent.color == RBNode.RED:
# Caso 1: el nodo tío es rojo -> recolorear
# Casos 2 y 3: el nodo tío es negro -> resolver mediante rotación y recoloreado
# ... (la implementación concreta implica muchas operaciones con punteros; aquí es una descripción lógica)
pass
tree.root.color = RBNode.BLACK # Asegurar que el nodo raíz sea negro
Árbol rojo-negro vs. árbol AVL
| Propiedad | Árbol AVL | Árbol rojo-negro |
|---|---|---|
| Estándar de equilibrio | Estricto (diferencia de altura ≤ 1) | Flexible (garantiza un equilibrio aproximado mediante reglas de color) |
| Rendimiento de búsqueda | Mejor(el árbol está más equilibrado) | Ligeramente inferior, pero sigue siendo O(log n) |
| Inserción/eliminación | Puede requerirmás rotaciones | Menos rotaciones,mayor eficiencia |
| Escenarios de aplicación | Escenarios que requieren búsquedas frecuentes | Escenarios con altos requisitos de rendimiento integral, como las bibliotecas estándar de lenguajes y los sistemas de archivos |
Árbol B y árbol B+: el motor del almacenamiento en disco
Cuando el volumen de datos es demasiado grande para caber todo en la memoria, debe almacenarse en el disco. La velocidad de E/S (lectura/escritura) del disco es mucho más lenta que el acceso a memoria. Los árboles B y B+ están diseñadospara reducir el número de E/S de discoy sonárboles de búsqueda multiramal balanceados.Se utilizan ampliamente en los índices de bases de datos y sistemas de archivos.
Árbol B: árbol de búsqueda multiramal balanceado
Un árbol B ya no tiene un solo dato y dos punteros por nodo. Unárbol B de orden mtiene las siguientes características:
- Cada nodo tiene como máximom hijos.。
- Cada nodo que no sea raíz ni hoja tiene al menos⌈m/2⌉ hijos.。
- El nodo raíz tiene al menos 2 hijos (a menos que sea un nodo hoja).
- Todos los nodos hoja están en el mismo nivel.
- Si un nodo no hoja tiene k hijos, contienek-1 claves,que dividen los rangos de valores de los subárboles.
Figura: diagrama de la estructura de un nodo de árbol B de orden 3. Contiene dos claves y tres punteros, que dividen el rango de datos en tres intervalos.
Ventajas del árbol BRadica en la forma de árbol baja y ancha. Dado que un nodo puede almacenar varias claves y tener varios nodos hijos, la altura del árbol se reduce considerablemente. Al buscar un dato, se necesitan cargar menos páginas de disco (nodos), lo que mejora la eficiencia.
Árbol B+: la versión mejorada del árbol B
El árbol B+ realiza mejoras clave sobre la base del árbol B; es elestándar de facto。
Diferencias clave entre el árbol B+ y el árbol B:
- Ubicación de almacenamiento de datos: En el árbol B+,todos los registros de datos (o punteros a registros) se almacenan solo en los nodos hojaLos nodos internos (no hoja) solo almacenan claves, para el enrutamiento.
- Lista enlazada de nodos hoja: Todos los nodos hoja se conectan mediante punteros formando unalista doblemente enlazada ordenada。
Figura: Diagrama del árbol B+. Observe que los datos solo están en los nodos hoja, y que los nodos hoja forman una lista enlazada ordenada.
La gran ventaja del árbol B+
| Ventaja | Explicación |
|---|---|
| Eficiencia de consulta más estable | Cualquier búsqueda debe llegar a los nodos hoja, la longitud de la ruta es la misma, el rendimiento es estable. |
| Mayor utilización del espacio | Los nodos internos no almacenan datos, pueden contener más claves, el árbol es más bajo y hay menos E/S. |
| Potente consulta por rango | Mediante la lista enlazada de los nodos hoja, se pueden realizar eficientementeWHERE age BETWEEN 20 AND 30este tipo de consultas por rango, mientras que el árbol B requiere un complejo recorrido en orden. |
| Más adecuado para la lectura anticipada del disco | El disco se lee y escribe por páginas (bloques). Los nodos del árbol B+ suelen diseñarse para que tengan exactamente el tamaño de una página, de modo que una sola E/S puede cargar más claves, reduciendo aún más la E/S. |
Resumen
Repasemos estas cuatro estructuras de árbol avanzadas con una tabla:
| Estructura de árbol | Objetivo principal | Característica clave | Aplicaciones típicas |
|---|---|---|---|
| Árbol AVL | Velocidad de consulta extrema | Equilibrio estricto de altura, ajustes de rotación frecuentes | Escenarios en memoria que requieren búsqueda rápida |
| Árbol rojo-negro | Equilibrio de rendimiento general | Equilibrado aproximadamente mediante reglas de color, alta eficiencia en inserción y eliminación | Bibliotecas estándar de lenguajes (Map/Set), planificación de procesos |
| Árbol B | Reducir E/S de disco | Equilibrio de múltiples vías, los datos pueden almacenarse en nodos internos | Primeros sistemas de archivos, algunos índices de bases de datos |
| Árbol B+ | Optimizar índices de bases de datos | Los datos se almacenan solo en las hojas, las hojas forman una lista enlazada, consultas por rango potentes | Índices de bases de datos relacionales modernas (MySQL, PostgreSQL) |