Binary Tree
MediaPrioritaria
Árbol donde cada nodo tiene como máximo dos hijos.
¿Qué es un Binary Tree?
Un Binary Tree (árbol binario) es una estructura en la que cada nodo tiene un valor y referencias a un máximo de dos nodos hijos: uno izquierdo y uno derecho. Se usa ampliamente en informática por su capacidad de representar relaciones jerárquicas.
Analogía del Mundo Real
Imagina un árbol genealógico donde cada persona puede tener hasta dos hijos. O un árbol de decisiones donde en cada punto tomas una elección que te lleva a otro nodo. Así funciona un árbol binario.
Cómo Funciona Internamente un Binary Tree
- Cada nodo contiene un valor, un hijo izquierdo y un hijo derecho.
- El nodo raíz es el punto de entrada al árbol.
- Los subárboles izquierdo y derecho pueden ser a su vez otros árboles binarios.
- Se puede recorrer en diferentes órdenes: in-order, pre-order y post-order.
- Se utiliza recursión o una pila para recorrerlo o manipularlo.
Ejemplos de Código
// Binary Tree Node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Binary Tree class
class BinaryTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return;
}
const queue = [this.root];
while (queue.length) {
const current = queue.shift();
if (!current.left) {
current.left = newNode;
return;
} else {
queue.push(current.left);
}
if (!current.right) {
current.right = newNode;
return;
} else {
queue.push(current.right);
}
}
}
}Explicación Visual (🚧 En progreso)
Pronto disponible
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 árbol.
El peor caso ocurre cuando el árbol está desbalanceado y se convierte en una lista enlazada.
Operaciones Comunes
- insert(value)Agrega un nodo en la primera posición libre
- inOrder(node)Recorre el árbol en orden (izquierda, raíz, derecha)
- preOrder(node)Recorre el árbol en preorden (raíz, izquierda, derecha)
- postOrder(node)Recorre el árbol en postorden (izquierda, derecha, raíz)
Practica
Aplica lo que has aprendido