Diferencias y Funcionamiento de Árboles Binarios, AVL y Estructuras B

Estructura y Funcionamiento de los Árboles Binarios de Búsqueda (ABB)

Un ABB se compone de nodos, donde cada uno contiene tres elementos: su valor, el puntero al hijo izquierdo y el puntero al hijo derecho. Además, se cumple la regla fundamental del ABB: todos los valores en el subárbol izquierdo son menores que el valor del nodo, y todos los valores en el subárbol derecho son mayores.

Operaciones en ABB

• Inserción: Se realiza una búsqueda recursiva desde la raíz del árbol siguiendo la regla establecida; cuando se encuentra el lugar adecuado, se inserta el nodo como hoja.
• Eliminación:
  • Si es hoja, se elimina directamente.
  • Si el nodo tiene un único hijo, se intercambia su posición con el hijo y luego se elimina.
  • Si el nodo tiene dos hijos, se busca el menor valor en el subárbol derecho (o el mayor valor del subárbol izquierdo), se reemplaza el nodo a eliminar por ese valor y luego se elimina dicho nodo.

Árboles AVL: Equilibrio y Rendimiento

En un AVL, aunque se mantienen los mismos elementos que en el ABB, cada nodo incluye un factor de equilibrio, que indica la diferencia de altura entre el subárbol izquierdo y el derecho. El equilibrio se mantiene si el valor absoluto de todos los factores de equilibrio es menor que 2.

Las operaciones de búsqueda y eliminación se realizan igual que en un ABB, con la diferencia de que se debe recalcular el factor de equilibrio en cada nodo a medida que ascendemos por el árbol y realizar las reestructuraciones necesarias (rotaciones simples o compuestas).

Árboles B y B+: Optimización para Almacenamiento

Los árboles B y B+ se componen de páginas (internas y hojas), unidad a la que se accede en bloque. Estas almacenan punteros a sus hijos (más de dos), las claves almacenadas en cada página y el número de espacios ocupados.

Ventajas y Diferencias

• Árbol B: Al maximizar el número de nodos hijo de cada nodo, su altura decrece y se optimiza el uso del espacio en disco, lo que mejora la velocidad de las operaciones de búsqueda, inserción y eliminación. Sin embargo, las operaciones de subdivisión o unificación de nodos pueden requerir más accesos a disco.
• Árbol B+: Todas las claves se encuentran en las hojas, lo que puede resultar en su duplicación en la raíz y nodos interiores, ya que se utilizan únicamente como índices. Esto aumenta el uso de memoria, pero evita la reorganización constante del árbol, la cual resulta costosa en los árboles B tradicionales.