Fundamentos de la Eliminación en Árboles B
La operación de eliminación en un Árbol B presenta desafíos estructurales únicos en comparación con la inserción. Mientras que la inserción se centra en el límite superior de claves por nodo ($2t-1$) y requiere divisiones (splits) cuando se excede, la eliminación se enfoca estrictamente en el límite inferior ($t-1$). Si un nodo cae por debajo de este umbral tras una extracción, la estructura pierde su equilibrio, obligando a realizar operaciones de redistribución (préstamo) o fusión (merge) de nodos para mantener la propiedad fundamental del árbol.
Escenarios Base de Extracción
Dependiendo de la ubicación del elemento objetivo, la estrategia inicial varía:
- Nodos Hoja: Si el elemento a eliminar reside en una hoja y el nodo posee más de $t-1$ elementos, la extracción es directa y no requiere ajustes adicionales.
- Nodos Internos: Si el elemento está en un nodo interno, no se puede eliminar directamente sin violar la propiedad de que un nodo con $k$ hijos debe tener exactamente $k-1$ claves. La solución estándar es reemplazar la clave objetivo con su predecesor (el elemento más grande en el subárbol izquierdo) o su sucesor, y luego eliminar recursivamente ese elemento de reemplazo en la hoja correspondiente.
Mantenimiento Proactivo del Equilibrio
Para evitar retrocesos (backtracking) complejos y costosos durante la recursión, se aplica una estrategia de expansión preventiva. Al descender por el árbol en busca del nodo objetivo, si se encuentra un nodo con exactamente $t-1$ elementos, se debe expandir antes de continuar. Esto garantiza que, al llegar a la hoja, siempre haya suficiente margen para realizar la eliminación sin romper las invariantes del árbol.
Mecanismos de Reequilibrio
La expansión de un nodo en el límite mínimo se logra mediante tres mecanismos, evaluados en orden de preferencia:
- Rotación desde el hermano izquierdo: Si el hermano izquierdo existe y tiene más de $t-1$ elementos, se toma su elemento más a la derecha, se sube al nodo padre, y el elemento correspondiente del padre baja al nodo actual.
- Rotación desde el hermano derecho: Aálogo al anterior, pero tomando el elemento más a la izquierda del hermano derecho y ajustando los punteros de los hijos en nodos internos.
- Fusión de nodos (Merge): Si ambos hermanos tienen exactamente $t-1$ elementos, no es posible realizar préstamos. En su lugar, el nodo actual, un elemento del padre y un hermano adyacente se fusionan en un solo nodo, reduciendo la cantidad de claves del padre.
Extracción de Valores Extremos
La eliminación del valor mínimo o máximo sigue una ruta determinista hacia la izquierda o derecha, respectivamente. Durante este descenso, se aplican las mismas reglas de expansión preventiva descritas anteriormente para asegurar que los nodos visitados mantengan el umbral mínimo de elementos.
Implementación en C#
A continuación se presenta la implementación reetsructurada de la lógica de extracción. Se ha modificado la nomenclatura y la organización interna para mejorar la claridad del flujo de reequilibrio.
internal enum ExtractionMode
{
SpecificKey,
AbsoluteMinimum,
AbsoluteMaximum
}
public sealed class BTreeMap<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
{
public bool Extract([NotNull] TKey targetKey, out TValue? extractedValue)
{
ArgumentNullException.ThrowIfNull(targetKey);
return ExecuteExtraction(targetKey, ExtractionMode.SpecificKey, out extractedValue);
}
public bool ExtractMaximum(out TValue? maxValue) => ExecuteExtraction(default, ExtractionMode.AbsoluteMaximum, out maxValue);
public bool ExtractMinimum(out TValue? minValue) => ExecuteExtraction(default, ExtractionMode.AbsoluteMinimum, out minValue);
private bool ExecuteExtraction(TKey? key, ExtractionMode mode, out TValue? result)
{
if (_rootNode == null || _rootNode.HasNoKeys)
{
result = default;
return false;
}
bool success = _rootNode.Extract(key, mode, out var extractedItem);
// Si la raíz se queda vacía y no es hoja, la altura del árbol disminuye
if (_rootNode.HasNoKeys && !_rootNode.IsLeafNode)
{
_rootNode = _rootNode.FetchChild(0);
}
if (success)
{
_totalElements--;
result = extractedItem!.Payload;
return true;
}
result = default;
return false;
}
}
La lógica central de navegación y reequilibrio se encapsula en la clase del nodo:
internal class BTreeNode<TKey, TValue>
{
public bool Extract(TKey? target, ExtractionMode mode, [MaybeNullWhen(false)] out DataItem<TKey, TValue?> output)
{
int childPointer = 0;
bool keyLocated = false;
if (mode == ExtractionMode.AbsoluteMaximum)
{
if (IsLeafNode)
{
output = HasNoKeys ? default : KeyStore.ExtractLast();
return HasKeys;
}
childPointer = KeyCount;
}
else if (mode == ExtractionMode.AbsoluteMinimum)
{
if (IsLeafNode)
{
output = HasNoKeys ? default : KeyStore.ExtractFirst();
return HasKeys;
}
childPointer = 0;
}
else // SpecificKey
{
keyLocated = KeyStore.LocateKey(target!, out childPointer);
if (IsLeafNode)
{
output = keyLocated ? KeyStore.ExtractAt(childPointer) : default;
return keyLocated;
}
}
// Preparar el nodo hijo para la extracción si está en el límite mínimo
if (ChildNodes[childPointer].KeyCount <= MinimumKeysThreshold)
{
return RebalanceAndExtract(childPointer, target!, mode, out output);
}
var targetChild = ChildNodes[childPointer];
if (keyLocated)
{
// Reemplazar con el predecesor (máximo del subárbol izquierdo)
output = KeyStore[childPointer];
targetChild.Extract(default!, ExtractionMode.AbsoluteMaximum, out var predecessor);
KeyStore[childPointer] = predecessor;
return true;
}
return targetChild.Extract(target!, mode, out output);
}
private bool RebalanceAndExtract(int idx, TKey key, ExtractionMode mode, [MaybeNullWhen(false)] out DataItem<TKey, TValue?> result)
{
// Intentar rotación desde la izquierda
if (idx > 0 && ChildNodes[idx - 1].KeyCount > MinimumKeysThreshold)
{
var current = ChildNodes[idx];
var leftSibling = ChildNodes[idx - 1];
var borrowedKey = leftSibling.KeyStore.ExtractLast();
current.KeyStore.InsertAt(0, KeyStore[idx - 1]);
KeyStore[idx - 1] = borrowedKey;
if (!leftSibling.IsLeafNode)
{
current.ChildNodes.InsertAt(0, leftSibling.ChildNodes.ExtractLast());
}
}
// Intentar rotación desde la derecha
else if (idx < ChildCount - 1 && ChildNodes[idx + 1].KeyCount > MinimumKeysThreshold)
{
var current = ChildNodes[idx];
var rightSibling = ChildNodes[idx + 1];
var borrowedKey = rightSibling.KeyStore.ExtractFirst();
current.KeyStore.Add(KeyStore[idx]);
KeyStore[idx] = borrowedKey;
if (!rightSibling.IsLeafNode)
{
current.AppendChild(rightSibling.ChildNodes.ExtractFirst());
}
}
// Fusión (Merge)
else
{
int mergeIdx = idx >= KeyCount ? idx - 1 : idx;
var leftNode = ChildNodes[mergeIdx];
var parentKey = KeyStore.ExtractAt(mergeIdx);
var rightNode = ChildNodes.ExtractAt(mergeIdx + 1);
leftNode.KeyStore.Add(parentKey);
leftNode.KeyStore.AddRange(rightNode.KeyStore);
leftNode.ChildNodes.AddRange(rightNode.ChildNodes);
}
return Extract(key, mode, out result);
}
}
Análisis de Rendimiento (Benchmarking)
Dado que el Árbol B implementado soporta reglas de ordenamiento personalizadas y la extracción de valores extremos, es válido evaluar su viabilidad como cola de prioridad (Priority Queue). A continuación, se comparan las métricas de inserción y extracción frente a la implementación nativa de PriorityQueue en .NET.
[MemoryDiagnoser]
public class TreeVsQueueInsertionBenchmark
{
[Params(1000, 10000, 100000)] public int ElementCount;
[Params(2, 4, 8, 16)] public int TreeOrder;
private int[] _payload;
[GlobalSetup]
public void InitializeData()
{
_payload = new int[ElementCount];
var rng = new Random(42);
for (int i = 0; i < ElementCount; i++) _payload[i] = rng.Next();
}
[Benchmark]
public void BTreeMap_Insertion()
{
var tree = new BTreeMap<int, int>(TreeOrder);
foreach (var val in _payload) tree.Insert(val, val);
}
[Benchmark]
public void PriorityQueue_Insertion()
{
var queue = new PriorityQueue<int, int>(ElementCount);
foreach (var val in _payload) queue.Enqueue(val, val);
}
}
[MemoryDiagnoser]
public class TreeVsQueueExtractionBenchmark
{
[Params(1000, 10000, 100000)] public int ElementCount;
[Params(2, 4, 8, 16)] public int TreeOrder;
private BTreeMap<int, int> _treeInstance;
private PriorityQueue<int, int> _queueInstance;
[IterationSetup]
public void PrepareStructures()
{
var rng = new Random(42);
_treeInstance = new BTreeMap<int, int>(TreeOrder);
_queueInstance = new PriorityQueue<int, int>(ElementCount);
for (int i = 0; i < ElementCount; i++)
{
int val = rng.Next();
_treeInstance.Insert(val, val);
_queueInstance.Enqueue(val, val);
}
}
[Benchmark]
public void BTreeMap_Extraction()
{
while (_treeInstance.Count > 0) _treeInstance.ExtractMinimum(out _);
}
[Benchmark]
public void PriorityQueue_Extraction()
{
while (_queueInstance.Count > 0) _queueInstance.Dequeue();
}
}
Los resultados de las pruebas de rendimiento indican que, aunque el Árbol B presenta una sobrecarga inicial en las operaciones de inserción en comparación con PriorityQueue debido a la gestión de nodos y el reequilibrio, su rendimiento en la extracción de elementos es superior cuando el volumen de datos y el orden del árbol son elevados. Esto se debe a que la menor altura del árbol reduce la profundidad de las operaciones recursivas, validando su viabilidad como estructura de datos para colas de prioridad en escenarios de lectura y extracción intensiva.