Binary Search Tree
Árbol binario donde el hijo izquierdo es menor que el padre y el derecho es mayor.
¿Qué es un Binary Search Tree?
Es un árbol binario con una regla especial: todos los valores del subárbol izquierdo de un nodo son menores que el nodo, y todos los del subárbol derecho son mayores.
Esto permite realizar operaciones de búsqueda, inserción y eliminación de forma eficiente si el árbol está balanceado.
Analogía del Mundo Real
Piensa en una agenda telefónica ordenada alfabéticamente. Si buscas un nombre, puedes ir directamente hacia la mitad y decidir si ir hacia arriba o hacia abajo según la letra inicial. Esa eficiencia es justo lo que ofrece un BST.
Cómo Funciona Internamente un BST
- Cada nodo tiene como máximo dos hijos: izquierdo y derecho.
- Los valores en el hijo izquierdo son menores que el valor del nodo actual.
- Los valores en el hijo derecho son mayores.
- Esta propiedad se mantiene recursivamente en todos los nodos.
- Se puede recorrer el árbol in-order para obtener los valores ordenados.
Ejemplos de Código
// Binary Search Tree in JavaScript
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return;
}
current = current.right;
}
}
}
}Explicación Visual (🚧 En progreso)
Estamos trabajando en un video para explicar esta estructura de datos
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(log n) | O(n) |
| Búsqueda | O(log n) | O(n) |
| Inserción | O(log n) | O(n) |
| Eliminación | O(log n) | O(n) |
Donde n es el número de nodos.
En el peor caso (árbol desbalanceado), la complejidad puede degradarse a O(n).
Operaciones Comunes
- insert(value)Agrega un nodo manteniendo la propiedad del BST
- search(value)Verifica si el valor existe en el árbol
- inOrder(node)Recorre los valores en orden ascendente
- min()Obtiene el valor más pequeño
- max()Obtiene el valor más grande