7 - Inserción y eliminación

Este tema profundiza en las operaciones de inserción y eliminación sobre árboles binarios de búsqueda. Ajustaremos la inserción para evitar duplicados cuando sea necesario, analizaremos cada caso de eliminación y cerramos con un ejemplo completo que podrás ejecutar en CLion.

7.1 Recordatorio del modelo

Usaremos la misma estructura de nodo y contenedor del tema anterior. Mantener un modelo consistente reduce errores y simplifica las pruebas.

typedef struct TreeNode {
  int valor;
  struct TreeNode *izquierdo;
  struct TreeNode *derecho;
} TreeNode;

typedef struct {
  TreeNode *raiz;
  unsigned int cantidad;
} ArbolABB;

7.2 Inserción con control de duplicados

Cuando el dominio requiere valores únicos, podemos rechazar la inserción si el dato ya existe. El siguiente helper devuelve el nodo existente o NULL si el valor no se pudo insertar por falta de memoria.

TreeNode *insertarUnico(ArbolABB *arbol, int valor) {
  if (!arbol->raiz) {
    TreeNode *nodo = crearNodo(valor);
    if (!nodo) return NULL;
    arbol->raiz = nodo;
    arbol->cantidad = 1;
    return nodo;
  }

  TreeNode *actual = arbol->raiz;
  TreeNode *anterior = NULL;
  while (actual) {
    if (valor == actual->valor) {
      return actual; /* ya existe */
    }
    anterior = actual;
    actual = (valor < actual->valor) ? actual->izquierdo : actual->derecho;
  }

  TreeNode *nuevo = crearNodo(valor);
  if (!nuevo) return NULL;
  if (valor < anterior->valor) anterior->izquierdo = nuevo;
  else anterior->derecho = nuevo;
  arbol->cantidad++;
  return nuevo;
}

7.3 Casos de eliminación

La eliminación depende de la cantidad de hijos que posea el nodo objetivo:

  1. Hoja: se libera directamente.
  2. Un hijo: se conecta el hijo con el padre y se libera el nodo.
  3. Dos hijos: se reemplaza con el sucesor inorden (mínimo del subárbol derecho) o predecesor.

Implementamos una versión recursiva que resuelve los tres escenarios:

TreeNode *minimo(TreeNode *nodo) {
  while (nodo && nodo->izquierdo) {
    nodo = nodo->izquierdo;
  }
  return nodo;
}

TreeNode *eliminar(TreeNode *raiz, int valor) {
  if (!raiz) return NULL;

  if (valor < raiz->valor) {
    raiz->izquierdo = eliminar(raiz->izquierdo, valor);
  } else if (valor > raiz->valor) {
    raiz->derecho = eliminar(raiz->derecho, valor);
  } else {
    if (!raiz->izquierdo) {
      TreeNode *derecho = raiz->derecho;
      free(raiz);
      return derecho;
    }
    if (!raiz->derecho) {
      TreeNode *izquierdo = raiz->izquierdo;
      free(raiz);
      return izquierdo;
    }
    TreeNode *sucesor = minimo(raiz->derecho);
    raiz->valor = sucesor->valor;
    raiz->derecho = eliminar(raiz->derecho, sucesor->valor);
  }
  return raiz;
}

7.4 Actualizar la cantidad de nodos

Cuando eliminamos un nodo debemos reflejarlo en el contador global. Esto se logra controlando si la eliminación realmente removió un elemento.

TreeNode *buscar(TreeNode *nodo, int valor) {
  while (nodo) {
    if (valor == nodo->valor) return nodo;
    nodo = (valor < nodo->valor) ? nodo->izquierdo : nodo->derecho;
  }
  return NULL;
}

int removerValor(ArbolABB *arbol, int valor) {
  if (!buscar(arbol->raiz, valor)) {
    return 0;
  }
  arbol->raiz = eliminar(arbol->raiz, valor);
  if (arbol->cantidad > 0) {
    arbol->cantidad--;
  }
  return 1;
}

En aplicaciones reales conviene devolver información adicional (por ejemplo, el nodo eliminado) para liberar recursos asociados.

7.5 Validaciones y pruebas

Para garantizar que las operaciones mantengan la propiedad de ABB podemos ejecutar un recorrido inorden tras cada eliminación y verificar que la secuencia permanezca ordenada. Además, conviene probar entradas degeneradas (valores ascendentes, descendentes y repetidos).

7.6 Código completo para CLion

El archivo siguiente demuestra inserciones sin duplicados y distintas eliminaciones. Imprime el inorden antes y después de cada operación.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
  int valor;
  struct TreeNode *izquierdo;
  struct TreeNode *derecho;
} TreeNode;

typedef struct {
  TreeNode *raiz;
  unsigned int cantidad;
} ArbolABB;

TreeNode *crearNodo(int valor) {
  TreeNode *nodo = malloc(sizeof(TreeNode));
  if (!nodo) return NULL;
  nodo->valor = valor;
  nodo->izquierdo = NULL;
  nodo->derecho = NULL;
  return nodo;
}

TreeNode *insertarUnico(ArbolABB *arbol, int valor) {
  if (!arbol->raiz) {
    TreeNode *nodo = crearNodo(valor);
    if (!nodo) return NULL;
    arbol->raiz = nodo;
    arbol->cantidad = 1;
    return nodo;
  }
  TreeNode *actual = arbol->raiz;
  TreeNode *anterior = NULL;
  while (actual) {
    if (valor == actual->valor) return actual;
    anterior = actual;
    actual = (valor < actual->valor) ? actual->izquierdo : actual->derecho;
  }
  TreeNode *nuevo = crearNodo(valor);
  if (!nuevo) return NULL;
  if (valor < anterior->valor) anterior->izquierdo = nuevo;
  else anterior->derecho = nuevo;
  arbol->cantidad++;
  return nuevo;
}

TreeNode *minimo(TreeNode *nodo) {
  while (nodo && nodo->izquierdo) nodo = nodo->izquierdo;
  return nodo;
}

TreeNode *eliminar(TreeNode *raiz, int valor) {
  if (!raiz) return NULL;
  if (valor < raiz->valor) {
    raiz->izquierdo = eliminar(raiz->izquierdo, valor);
  } else if (valor > raiz->valor) {
    raiz->derecho = eliminar(raiz->derecho, valor);
  } else {
    if (!raiz->izquierdo) {
      TreeNode *derecho = raiz->derecho;
      free(raiz);
      return derecho;
    }
    if (!raiz->derecho) {
      TreeNode *izquierdo = raiz->izquierdo;
      free(raiz);
      return izquierdo;
    }
    TreeNode *sucesor = minimo(raiz->derecho);
    raiz->valor = sucesor->valor;
    raiz->derecho = eliminar(raiz->derecho, sucesor->valor);
  }
  return raiz;
}

void imprimirInorden(TreeNode *nodo) {
  if (!nodo) return;
  imprimirInorden(nodo->izquierdo);
  printf("%d ", nodo->valor);
  imprimirInorden(nodo->derecho);
}

void limpiar(TreeNode *nodo) {
  if (!nodo) return;
  limpiar(nodo->izquierdo);
  limpiar(nodo->derecho);
  free(nodo);
}

int main(void) {
  ArbolABB arbol = {0};
  int datos[] = {10, 4, 18, 2, 6, 15, 20};
  unsigned int total = (unsigned int)(sizeof(datos)/sizeof(datos[0]));
  for (unsigned int i = 0; i < total; i++) {
    insertarUnico(&arbol, datos[i]);
  }

  puts("Inorden inicial:");
  imprimirInorden(arbol.raiz);

  arbol.raiz = eliminar(arbol.raiz, 2);
  puts("\nTras eliminar hoja 2:");
  imprimirInorden(arbol.raiz);

  arbol.raiz = eliminar(arbol.raiz, 18);
  puts("\nTras eliminar nodo con un hijo (18):");
  imprimirInorden(arbol.raiz);

  arbol.raiz = eliminar(arbol.raiz, 10);
  puts("\nTras eliminar la raiz (dos hijos):");
  imprimirInorden(arbol.raiz);

  limpiar(arbol.raiz);
  return 0;
}
Retornar