Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript

Curso de Estructuras de Datos con JavaScript

Contenido del curso

Introducción a las estructuras de datos

Arrays y strings

Hash Table

Linked List

Stacks

Queues

Trees

20
Estructuras de Datos: Árboles Binarios y Búsqueda en JavaScript
06:15 min
21
Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript
Viendo ahora

Graphs

Cierre

25
Estructuras de Datos con JavaScript: Práctica y Aplicación
03:14 min

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0019:36

Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript

Curso de Estructuras de Datos con JavaScript

Clase 21 de 25

Clase 21 / 25

Recursos

Construir un árbol binario de búsqueda en JavaScript es más sencillo cuando dominas la regla central: en un binary search tree, los valores menores van siempre al lado izquierdo y los mayores al lado derecho. Aquí verás cómo detectar errores lógicos, modelar nodos y programar el método de insert con validaciones claras.

¿Qué corrige la lógica de un binary search tree?

La confusión inicial surge cuando alguna rama rompe la regla de orden. Si un nodo que debería aumentar aparece a la izquierda o uno que debería disminuir aparece a la derecha, el árbol queda mal formado. La lógica debe aplicarse a todas las ramas, no solo a nivel inmediato del root.

Si los nodos a la derecha no incrementan, la estructura es incorrecta.
Si los nodos a la izquierda no disminuyen, la estructura es incorrecta.
La validación debe repetirse en cada nivel del árbol.

¿Qué árbol de ejemplo vamos a formar?

Se construye un árbol con root 10; hijos 4 y 20; y, en niveles siguientes, 2, 8, 17 y 170. La forma correcta respeta el orden:

Izquierda del 10: 4, y a su vez 2 y 8.
Derecha del 10: 20, y a su vez 17 y 170.
Así, los valores a la derecha siempre aumentan y a la izquierda siempre disminuyen.

¿Cómo se modela el nodo y el árbol en JavaScript?

Cada nodo tiene tres propiedades: left, right y value. El árbol mantiene una referencia al root para iniciar recorridos e inserciones.

// Nodo: left, right, value
class Node {
  constructor(value) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

// Árbol: referencia a root e inserción de valores
class BinarySearchTree {
  constructor() {
    this.root = null; // inicia sin root
  }

  insert(value) {
    const newNode = new Node(value);

    // Caso 1: árbol vacío → newNode es root
    if (this.root === null) {
      this.root = newNode;
      return this; // importante para romper el flujo
    }

    // Caso 2: árbol con elementos → recorrer
    let currentNode = this.root; // *current node*
    while (true) { // *loop* iterativo
      if (value < currentNode.value) {
        // Ir a la izquierda
        if (!currentNode.left) {
          currentNode.left = newNode;
          return this;
        }
        currentNode = currentNode.left;
      } else {
        // Ir a la derecha
        if (!currentNode.right) {
          currentNode.right = newNode;
          return this;
        }
        currentNode = currentNode.right;
      }
    }
  }
}

Se usa una class para el árbol y otra para el nodo.
El constructor del árbol inicia con this.root = null.
El insert crea un new Node(value) y valida si el árbol está vacío.
El recorrido usa un while (true) y rompe con return this al insertar.
La decisión izquierda/derecha depende de value < currentNode.value.

¿Cómo funciona el método insert y el recorrido con while?

El método de insert cubre dos escenarios: crear el root y, si ya existe, recorrer la estructura hasta encontrar el hueco correcto. El recorrido es totalmente guiado por comparaciones menor/mayor.

Menor que el nodo actual: ir a left. Si left es null, insertar ahí.
Mayor o igual que el nodo actual: ir a right. Si right es null, insertar ahí.
En ambos casos, si existe un hijo, mover el current node y continuar el loop.

¿Cómo probar la inserción y validar la estructura?

Prueba rápida en JS creando una instancia del árbol y agregando valores en orden.

const tree = new BinarySearchTree();

tree.insert(10); // root

tree.insert(4);
tree.insert(20);

tree.insert(2);
tree.insert(8);
tree.insert(17);
tree.insert(170);

Resultados esperados al inspeccionar:

root.value es 10.
root.left.value es 4 y sus hijos son 2 y 8.
root.right.value es 20 y sus hijos son 17 y 170.

¿Qué habilidades y conceptos refuerzas con este ejercicio?

Invariantes de estructura en un binary search tree.
Modelado con class y constructor en JavaScript.
Recorrido iterativo con while y control de flujo con return.
Comparaciones y asignación condicional para izquierda/derecha.
Manejo de null y uso de variables temporales como current node.

¿Qué sigue con el método search?

El siguiente paso es programar search: recibe un número y devuelve el nodo completo donde se encuentra (incluyendo sus hijos). La lógica de recorrido es muy similar a la de insert, solo que aquí no insertas: comparas y avanzas hasta encontrar o no el valor.

¿Te animas a implementar search? Compártelo en comentarios para que todos veamos tu enfoque y podamos aprender juntos.

Jairo Campos Ruiz

Hace 4 años

Veo en los ejemplos muchas funciones resueltas con recursividad lo que las hace más sencillas de entender pero tienen un gran problema de rendimiento por consumo de memoria y pueden pueden llenar el call stack de JavaScript. Por ello en producción no suelen usarse funciones recursivas.

Dejo un ejemplo que he desarrollado del delete y el search sin recursividad para que no tenga problemas de rendimiento.

class Node<T> {
  public left: Node<T> | null = null;
  public right: Node<T> | null = null;

  constructor(
    public value: T,
  ) {
  }
}

export class BinarySearchTree<T> {
  private root: Node<T> | null = null;

  constructor() {
  }

  insert(value: T): void {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    let currentNode = this.root;
    while (true) {
      if (value < currentNode.value) {
        if (currentNode.left === null) {
          currentNode.left = newNode;
          return;
        }
        currentNode = currentNode.left;
      } else {
        if (currentNode.right === null) {
          currentNode.right = newNode;
          return;
        }
        currentNode = currentNode.right;
      }
    }
  }

  search(value: T): Node<T> | null {
    if (this.root === null) {
      return null;
    }
    let currentNode = this.root;
    while (currentNode !== null) {
      if (value < currentNode.value) {
        if (currentNode.left === null) {
          return null;
        }
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        if (currentNode.right === null) {
          return null;
        }
        currentNode = currentNode.right;
      } else {
        return currentNode;
      }
    }
    return null;
  }

  delete(value: T): Node<T> | null {
    if (this.root === null) { // tree is empty
      return null;
    }

    let currentNode = this.root;
    let currentNodePosition: 'right' | 'left';
    let parentNode = null;

    while (currentNode !== null) { //Empezamos a buscar el nodo y su padre
      if (value < currentNode.value) {
        if (currentNode.left === null) { // No encontramos retornamos null
          return null;
        }
        parentNode = currentNode;
        currentNode = currentNode.left;
        currentNodePosition = 'left';
      } else if (value > currentNode.value) {
        if (currentNode.right === null) { // No encontramos retornamos null
          return null;
        }
        parentNode = currentNode;
        currentNode = currentNode.right;
        currentNodePosition = 'right';
      } else { //A partir de aquí hemos encontrado el nodo a eliminar
        if (parentNode === null) { // El nodo a eliminar es el root
          if (currentNode.left === null && currentNode.right === null) { //No tiene hijos
            this.root = null;
            return currentNode;
          } else if (currentNode.left && currentNode.right) { //Tiene ambos hijos
            const nodeToChange = this.searchLeafToChange();
            nodeToChange.right = currentNode.right;
            nodeToChange.left = currentNode.left;
            this.root = nodeToChange;
            return currentNode;
          } else if (currentNode.left !== null) { //Solo tiene hijo a la izquierda
            this.root = currentNode.left;
            return currentNode;
          } else { //Solo tiene hijo a la derecha
            this.root = currentNode.right;
            return currentNode;
          }

        } else if (currentNode.left === null && currentNode.right === null) { //El nodo a eliminar es una hoja
          parentNode[currentNodePosition!] = null;
          return currentNode;

        } else if (currentNode.left && currentNode.right) { //El nodo a eliminar es intermedio y tiene ambos hijos
          const nodeToChange = this.searchLeafToChange();
          nodeToChange.left = currentNode.left;
          nodeToChange.right = currentNode.right;
          parentNode[currentNodePosition!] = nodeToChange;
          return currentNode;

        } else if (currentNode.left !== null) { //El nodo a eliminar es intermedio y solo tiene hijo a la izquierda
          parentNode[currentNodePosition!] = currentNode.left;
          return currentNode;
        } else { //El nodo a eliminar es intermedio y solo tiene hijo a la derecha
          parentNode[currentNodePosition!] = currentNode.right;
          return currentNode;
        }
      }
    }
    return currentNode;
  }

  //Busca el nodo más pequeño de la parte derecha del root, lo elimina y lo devuelve.
  private searchLeafToChange(): Node<T> {
    if (!this.root?.right) {
      return this.root!;
    }
    let currentNode = this.root.right;
    let parentNode = this.root;

    while (true) {
      if (currentNode.left !== null) { //Buscamos el nodo más pequeño
        parentNode = currentNode;
        currentNode = currentNode.left;
      } else if (currentNode.right === null) { //No tiene hijos estamos en una hoja
        parentNode.left = null;
        return currentNode;
      } else { //Tiene hijo a la derecha
        parentNode.left = currentNode.right;
        return currentNode;
      }
    }
  }
}

const tree = new BinarySearchTree<number>();

tree.insert(10);
//        10
tree.insert(4);
//        10
//     /
//   4
tree.insert(20);
//        10
//     /      \
//   4         20
tree.insert(2);
//        10
//     /      \
//   4         20
//  /
// 2
tree.insert(8);
//        10
//     /      \
//   4         20
//  /  \
// 2    8
tree.insert(17);
//        10
//     /      \
//   4         20
//  /  \      /
// 2    8   17
tree.insert(170);
//        10
//     /      \
//   4         20
//  /  \      /  \
// 2    8   17    170

// console.log(tree);

//Probando a borrar una hoja el número 8
// console.log('search value 8: ', tree.search(8));
// console.log('search value 4: ', tree.search(4));
// console.log('delete 8: ', tree.delete(8));
// console.log('search value 4: ', tree.search(4));
//        10
//     /      \
//   4         20
//  /         /  \
// 2        17    170

//Probando a borrar el root
// console.log(tree);
// console.log('delete root 10: ', tree.delete(10));
// console.log(tree);
//        17
//     /      \
//   4         20
//  /  \         \
// 2    8         170

//Probando a eliminar un nodo intermedio con ambos hijos el 20
// console.log('search root 10: ', tree.search(10));
// console.log('search value 20: ', tree.search(20));
// console.log('delete 20: ', tree.delete(20));
// console.log('search root 10: ', tree.search(10));
//        10
//     /      \
//   4         17
//  /  \         \
// 2    8         170

Se suele tardar un poco más en implementar pero aumenta mucho el rendimiento.

Comentarios (262)262 comentarios

Carlos Eduardo Gomez García

Hace 6 años

David Granados

Jimmy Buriticá Londoño

Juan David Sánchez

Ángel David Roque Ayala

Emi Jin | EmiLaJaponesa.com

Hace 5 años

Francisco Serrato Jiménez

Esteban Bustos

Hace 3 años

Juan Manuel Fallo

Usuario anónimo

User

Hector Miguel Salazar Doroteo

Karen Paola Torres Archbold

Jhean Pacheco

Agustina Corvo

Cristian Vargas Ari

Luis Blas

Jose Funez

Hector Rodriguez

Hace un año

Alexander Gonzalez

Guido Modarelli

Alejandro Ibarra Rodriguez

Jose Anibal Garcia Giraldo

Antony Jose Cabeza Rauseo

Juan Esteban Galvis

Daniel Omar Hernández Muñoz

Introducción a las estructuras de datos

Estructuras de Datos en JavaScript para Desarrolladores

Estructuras de Datos: Conceptos Básicos y Aplicaciones Prácticas

Almacenamiento de Datos en Memoria con JavaScript

Arrays y strings

Cómo funcionan arrays en memoria de JavaScript

Construcción de Arrays con Clases en JavaScript

Métodos pop y delete en arrays

Inmutabilidad de Strings y Almacenamiento en Memoria

Hash Table

Conceptos y Construcción de Hash Tables en JavaScript

Implementación de Hash Table en JavaScript: Método Set

Implementación del método get en hash table JavaScript

Linked List

Estructuras de Datos: Listas Enlazadas en JavaScript

Estructura y Creación de una Lista Enlazada Simple en JavaScript

Métodos para Manipular Nodos en Listas Enlazadas

Inserta nodos intermedios sin romper enlaces en JavaScript

Doubly Linked List con punteros bidireccionales

Stacks

Stacks: Concepto y Operaciones Básicas en JavaScript

Implementación de Stacks en JavaScript: Métodos Push y Peek

Queues

Qué es queue y cómo funciona FIFO

Implementación del método enqueue en JavaScript

Trees

Estructuras de Datos: Árboles Binarios y Búsqueda en JavaScript

Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript

Graphs

Conceptos básicos de grafos: tipos y aplicaciones prácticas

Representación visual de grafos en JavaScript

Construcción de Grafos: Método Lista de Adyacencia en JavaScript

Cierre

Estructuras de Datos con JavaScript: Práctica y Aplicación

Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript