My IT Utilities

Árbol binario de búsqueda (BST)

Parte de un árbol binario de búsqueda aleatorio e inserta, busca o borra valores paso a paso, con su forma en array y el código C++ resaltado.

Todo se simula en este navegador; no se envía nada a ningún servidor.

Sin pasos

Sin pasos

Árbol binario de búsqueda

Índice en el array

60[0]45[1]85[2]68[5]21[3]55[4]32[8]

Forma en array

Los hijos del índice i están en 2i+1 y 2i+2.

  • Sin relación
  • Ya recorrido
  • En comparación
  • Encontrado
  • Nuevo
  • A borrar
  • Sucesor

Sin pasos

Código

#include <iostream>
using namespace std;
class Node { // Un nodo guarda su valor y los punteros a sus dos hijos
private: // Atributos privados: solo se tocan con los métodos
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // Inserta v en el árbol de búsqueda y devuelve la raíz
if (root == nullptr) // Hueco vacío: aquí va el nodo nuevo
return new Node(v); // Crea el nodo nuevo
if (v < root->getValue()) // Los menores van a la izquierda y los mayores a la derecha
root->setLeft(insert(root->getLeft(), v)); // Baja por el subárbol izquierdo
else
root->setRight(insert(root->getRight(), v)); // Baja por el subárbol derecho
return root;
}
int main() {
Node* root = buildTree(); // El árbol mostrado, ya construido
root = insert(root, v); // Primera llamada, desde main
return 0; // Fin de la operación
}

Esta herramienta parte de un árbol binario de búsqueda (BST) aleatorio y te deja modificarlo a mano: escribes un valor del 1 al 99 y pulsas Insertar, Buscar o Borrar. Cada operación se anima paso a paso sobre el árbol, con los nodos coloreados según su papel: en comparación, ya recorrido, nuevo, a borrar o sucesor. Debajo se ve el mismo árbol como array, con los hijos del índice i en 2i+1 y 2i+2, y el código C++ resalta la línea que se ejecuta. Puedes cambiar el tamaño de 3 a 15 nodos, generar otro árbol y retroceder a cualquier paso. Todo se simula en tu navegador.

Cómo se usa

  1. Ajusta el tamaño del árbol con el deslizante o pulsa Generar árbol nuevo para cambiar el punto de partida.
  2. Escribe un valor del 1 al 99 y pulsa Insertar, Buscar o Borrar; la animación empieza sola.
  3. Avanza o retrocede con los botones de paso anterior y siguiente, o pulsa Reproducir y cambia la velocidad.
  4. Observa los nodos coloreados, la forma en array del árbol y la línea resaltada del código C++.

Preguntas frecuentes

¿Qué es un árbol binario de búsqueda y qué propiedad cumple?
Es un árbol binario en el que cada nodo tiene como máximo dos hijos y se cumple que todos los valores del subárbol izquierdo son menores que el del nodo y todos los del derecho, mayores. Gracias a esa propiedad se puede descartar la mitad del camino en cada comparación.
¿Cómo funcionan insertar y buscar en un BST y cuánto cuestan?
Ambas empiezan en la raíz y comparan el valor con cada nodo: si es menor bajan por la izquierda y si es mayor, por la derecha. Buscar termina al encontrar el valor o al llegar a nullptr; insertar crea el nodo nuevo en ese hueco. Su coste es proporcional a la altura del árbol: logarítmico si está equilibrado y lineal si es una cadena.
¿Cuáles son los tres casos de borrar y por qué se usa el sucesor inorden?
Si el nodo es una hoja se quita sin más; si tiene un hijo, ese hijo ocupa su lugar; si tiene dos, se copia en él el valor del sucesor inorden, que es el menor del subárbol derecho, y se borra el nodo del sucesor. El sucesor es el valor que sigue en el orden, así que cabe en ese sitio sin romper la propiedad del BST, y como no tiene hijo izquierdo su borrado es de los casos sencillos.
¿Cómo se guarda un árbol en un array y por qué quedan huecos?
En formato de montículo: la raíz va en el índice 0 y los hijos del índice i, en 2i+1 y 2i+2. Si un nodo no tiene un hijo, esa posición queda vacía, y cuanto más desequilibrado es el árbol más huecos aparecen, porque los índices crecen con la profundidad.

Herramientas relacionadas