Insertar en un BST
Construya un árbol binario de búsqueda
Insertar en un BST es una lección gratuita de C Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
La regla de ordenación de los BST
Un árbol binario de búsqueda (BST) es un árbol binario con una regla adicional: para cada nodo, todos los valores de su subárbol izquierdo son menores y todos los valores de su subárbol derecho son mayores.
Esta ordenación permite buscar, insertar y eliminar en un tiempo proporcional a la altura del árbol.
Dónde pertenece un valor
Para insertar, comenzamos en la raíz y comparamos. Si el nuevo valor es menor, vamos a la izquierda; si es mayor, vamos a la derecha.
Repetimos el proceso hasta llegar a una posición vacía (NULL), que es exactamente donde pertenece el nuevo nodo.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/El helper create_node
La inserción crea nuevos nodos hoja, así que reutilizamos un constructor que asigna e inicializa un nodo.
Ambos hijos comienzan como NULL porque un nodo recién insertado siempre es una hoja.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Inserción recursiva
La forma más clara de insertar es mediante recursividad y devolviendo la raíz del subárbol, que puede ser nueva.
Si el subárbol está vacío, devolvemos un nodo nuevo. En caso contrario, recurrimos a la izquierda o a la derecha, volvemos a enlazar el resultado y devolvemos la raíz sin cambios.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}Por qué devolver la raíz
Devolver la raíz del subárbol permite al padre volver a enlazar el vínculo en una sola línea: root->left = insert(root->left, v).
Si el subárbol estaba vacío, el nuevo nodo devuelto se convierte en el hijo. Si no lo estaba, se devuelve la misma raíz y el vínculo no cambia.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);Gestionar los duplicados
Los BST reales deben decidir qué hacer con los valores iguales. Una opción habitual es ignorar los duplicados, como hace nuestro insert, que no tiene ninguna rama para el caso de igualdad.
Otras alternativas son mantener un contador por nodo o enviar siempre los duplicados a un mismo lado.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */Construir un BST
Insertar una secuencia de valores produce un árbol cuya forma depende del orden de inserción.
Aquí insertamos varios números e imprimimos los hijos inmediatos de la raíz para confirmar que se cumple la regla de ordenación.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return create_node(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}Una inserción iterativa
También puede insertar sin recursividad. Descendemos con un puntero y recordamos el padre hasta encontrar una posición vacía.
Después enlazamos el nuevo nodo en el lado correcto de ese padre.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}El orden de inserción da forma al árbol
Insertar 1,2,3,4,5 en orden ascendente produce un árbol degenerado que parece una lista enlazada, con una altura igual a la cantidad de elementos.
Insertar en un orden equilibrado mantiene la altura cerca de log(n). El equilibrio afecta directamente a la velocidad de búsqueda.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Coste de la inserción
Cada inserción recorre un camino desde la raíz hasta una hoja, por lo que realiza un trabajo proporcional a la altura del árbol.
En un árbol equilibrado, son aproximadamente log(n) comparaciones; en un árbol degenerado, pueden ser n. Por eso existen los árboles autoequilibrados.
Demostración completa de inserción
Este programa inserta valores y después cuenta los nodos para confirmar que se almacenaron cinco valores distintos y que se ignoró un duplicado.
El duplicado 10 no incrementa el recuento porque insert descarta los valores iguales.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}Comprobación rápida
Analice el comportamiento de la inserción.
Resumen
La inserción en un BST compara el nuevo valor con cada nodo: avanza a la izquierda si es menor y a la derecha si es mayor, hasta encontrar un espacio vacío.
La forma recursiva devuelve la raíz del subárbol para que el nodo padre pueda volver a enlazar los punteros correctamente. El coste de la inserción depende de la altura del árbol, por lo que el orden de inserción es importante.
Preguntas frecuentes
¿La lección «Insertar en un BST» es gratis?
Sí — el texto completo de «Insertar en un BST» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Insertar en un BST»?
Construya un árbol binario de búsqueda Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar C Academy?
No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Insertar en un BST»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de C Academy?
Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Nodos y estructura de árboles
- Insertar en un BST
- Recorridos
- Buscar y liberar