Implementación del árbol de búsqueda binaria en Javascript

En este artículo, estaríamos implementando la estructura de datos del árbol de búsqueda binaria en Javascript. Un árbol es una colección de Nodes conectados por algunos bordes. Un árbol es una estructura de datos no lineal. Un árbol de búsqueda binaria es un árbol binario en el que los Nodes que tienen un valor menor se almacenan a la izquierda, mientras que los Nodes con un valor más alto se almacenan a la derecha.

Ahora veamos un ejemplo de un Node de árbol de búsqueda binaria:

// Node class
class Node
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

Como en el fragmento de código anterior, definimos una clase de Node que tiene tres datos de propiedad , izquierda y derecha . Izquierda y derecha son punteros al Node izquierdo y derecho en un árbol de búsqueda binaria. Los datos se inicializan con los datos que se pasan cuando se crea el objeto para este Node y la izquierda y la derecha se establecen en nulo.

Ahora veamos un ejemplo de una clase de árbol de búsqueda binaria. 

// Binary Search tree class
class BinarySearchTree
{
    constructor()
    {
        // root of a binary search tree
        this.root = null;
    }
 
    // function to be implemented
    // insert(data)
    // remove(data)
                 
 
    // Helper function
    // findMinNode()
    // getRootNode()
    // inorder(node)
    // preorder(node)              
    // postorder(node)
    // search(node, data)
}

El ejemplo anterior muestra un marco de una clase de árbol de búsqueda binaria, que contiene una raíz de variable privada que contiene la raíz de un árbol, se inicializa en nulo. 

Ahora implementemos cada una de estas funciones: 

1. insert(datos) – Inserta un nuevo Node en un árbol con un valor de datos

// helper method which creates a new node to
// be inserted and calls insertNode
insert(data)
{
    // Creating a node and initialising
    // with data
    var newNode = new Node(data);
                     
    // root is null then node will
    // be added to the tree and made root.
    if(this.root === null)
        this.root = newNode;
    else
 
        // find the correct position in the
        // tree and add the node
        this.insertNode(this.root, newNode);
}
 
// Method to insert a node in a tree
// it moves over the tree to find the location
// to insert a node with a given data
insertNode(node, newNode)
{
    // if the data is less than the node
    // data move left of the tree
    if(newNode.data < node.data)
    {
        // if left is null insert node here
        if(node.left === null)
            node.left = newNode;
        else
 
            // if left is not null recur until
            // null is found
            this.insertNode(node.left, newNode);
    }
 
    // if the data is more than the node
    // data move right of the tree
    else
    {
        // if right is null insert node here
        if(node.right === null)
            node.right = newNode;
        else
 
            // if right is not null recur until
            // null is found
            this.insertNode(node.right,newNode);
    }
}

En el código anterior tenemos dos métodos insert(data) e insertNode(node, newNode) . Vamos a entenderlos uno por uno: – 

• insert (datos) : crea un nuevo Node con un valor de datos, si el árbol está vacío, agrega este Node a un árbol y lo convierte en raíz; de lo contrario, llama a insert (Node, datos) .
• insertar (Node, datos) : compara los datos proporcionados con los datos del Node actual y se mueve hacia la izquierda o hacia la derecha según corresponda y recurre hasta que encuentra un Node correcto con un valor nulo donde se puede agregar un nuevo Node.

2.remove(datos) – Esta función elimina un Node con datos dados.

// helper method that calls the
// removeNode with a given data
remove(data)
{
    // root is re-initialized with
    // root of a modified tree.
    this.root = this.removeNode(this.root, data);
}
 
// Method to remove node with a
// given data
// it recur over the tree to find the
// data and removes it
removeNode(node, key)
{
         
    // if the root is null then tree is
    // empty
    if(node === null)
        return null;
 
    // if data to be delete is less than
    // roots data then move to left subtree
    else if(key < node.data)
    {
        node.left = this.removeNode(node.left, key);
        return node;
    }
 
    // if data to be delete is greater than
    // roots data then move to right subtree
    else if(key > node.data)
    {
        node.right = this.removeNode(node.right, key);
        return node;
    }
 
    // if data is similar to the root's data
    // then delete this node
    else
    {
         // deleting node with no children
        if(node.left === null && node.right === null)
        {
            node = null;
            return node;
        }
 
        // deleting node with one children
        if(node.left === null)
        {
            node = node.right;
            return node;
        }
         
        else if(node.right === null)
        {
            node = node.left;
            return node;
        }
 
        // Deleting node with two children
        // minimum node of the right subtree
        // is stored in aux
        var aux = this.findMinNode(node.right);
        node.data = aux.data;
 
        node.right = this.removeNode(node.right, aux.data);
        return node;
    }
 
}

En el código anterior tenemos dos métodos remove(data) y removeNode(node, data) , entendámoslos uno por uno: 

• eliminar (datos) : son métodos auxiliares que llaman a removeNode pasando el Node raíz y los datos dados y actualiza la raíz del árbol con el valor devuelto por la función
• removeNode (Node, datos) : busca un Node con datos determinados y luego realiza ciertos pasos para eliminarlo.
• Eliminación del Node de hoja : como el Node de hoja no tiene hijos, por lo tanto, se pueden eliminar fácilmente y el valor nulo se devuelve al Node principal.
• Eliminar un Node con un hijo : si un Node tiene un hijo izquierdo, entonces actualizamos el puntero del Node principal al hijo izquierdo del Node que se eliminará y, de manera similar, si un Node tiene un hijo derecho, actualizamos el puntero de el Node principal al hijo derecho del Node que se eliminará
• Eliminación de un Node con dos hijos : para eliminar un Node con dos hijos, buscamos el Node con el valor mínimo en su subárbol derecho y reemplazamos este Node con el Node de valor mínimo y eliminamos el Node de valor mínimo del árbol.

Árbol transversal

Ahora vamos a entender las diferentes formas de atravesar un árbol de búsqueda binaria. 

inorder(Node) – Realiza un recorrido en orden de un árbol a partir de un Node dado  
Algoritmo para inorder:  

Atraviese el subárbol izquierdo, es decir, realice en orden en el subárbol izquierdo Visite la raíz Atraviese el subárbol derecho, es decir, realice en orden en el subárbol derecho

// Performs inorder traversal of a tree
inorder(node)
{
    if(node !== null)
    {
        this.inorder(node.left);
        console.log(node.data);
        this.inorder(node.right);
    }
}

1. preorden(Node) – Realiza un recorrido de preorden de un árbol a partir de un Node dado . 

Algoritmo para preordenar: 

Visite la raízAtraviese el subárbol izquierdo, es decir, realice un pedido anticipado en el subárbol izquierdoAtraviese el subárbol derecho, es decir, realice un pedido anticipado en el subárbol derecho

// Performs preorder traversal of a tree   
preorder(node)
{
    if(node !== null)
    {
        console.log(node.data);
        this.preorder(node.left);
        this.preorder(node.right);
    }
}

2. orden posterior (Node) : realiza el recorrido posterior al orden de un árbol a partir de un Node dado . 

Algoritmo para posorden: 

Atraviese el subárbol izquierdo, es decir, realice un pedido posterior en el subárbol izquierdo. Atraviese el subárbol derecho, es decir, realice un pedido posterior en el subárbol derecho. Visite la raíz.

// Performs postorder traversal of a tree
postorder(node)
{
    if(node !== null)
    {
        this.postorder(node.left);
        this.postorder(node.right);
        console.log(node.data);
    }
}

Métodos auxiliares Declaremos
algún método auxiliar que sea útil al trabajar con el árbol de búsqueda binaria. 

1. findMinNode(Node) : busca un Node con un valor mínimo a partir del Node .

//  finds the minimum node in tree
// searching starts from given node
findMinNode(node)
{
    // if left of a node is null
    // then it must be minimum node
    if(node.left === null)
        return node;
    else
        return this.findMinNode(node.left);
}

Como se ve en el método anterior, comenzamos desde un Node y seguimos moviéndonos hacia el subárbol izquierdo hasta que encontramos un Node cuyo hijo izquierdo es nulo, una vez que encontramos dicho Node, lo devolvemos.

2. getRootNode() : devuelve el Node raíz de un árbol.

// returns root of the tree
getRootNode()
{
    return this.root;
}

3. buscar (datos) : busca el Node con un valor de datos en todo el árbol.

// search for a node with given data
search(node, data)
{
   // if trees is empty return null
    if(node === null)
        return null;
 
    // if data is less than node's data
    // move left
    else if(data < node.data)
        return this.search(node.left, data);
 
    // if data is less than node's data
    // move left
    else if(data > node.data)
        return this.search(node.right, data);
 
    // if data is equal to the node data
    // return node
    else
        return node;
}

Nota: se pueden declarar diferentes métodos auxiliares en la clase BinarySearchTree según el requisito. 

Implementación:
ahora usemos la clase BinarySearchTree y sus diferentes métodos descritos anteriormente.

// create an object for the BinarySearchTree
var BST = new BinarySearchTree();
 
// Inserting nodes to the BinarySearchTree
BST.insert(15);
BST.insert(25);
BST.insert(10);
BST.insert(7);
BST.insert(22);
BST.insert(17);
BST.insert(13);
BST.insert(5);
BST.insert(9);
BST.insert(27);
                         
//          15
//         /  \
//        10   25
//       / \   / \
//      7  13 22  27
//     / \    /
//    5   9  17
 
var root = BST.getRootNode();
             
// prints 5 7 9 10 13 15 17 22 25 27
BST.inorder(root);
             
// Removing node with no children
BST.remove(5);
             
             
//          15
//         /  \
//        10   25
//       / \   / \
//      7  13 22  27
//       \    /
//        9  17
             
                         
var root = BST.getRootNode();
             
// prints 7 9 10 13 15 17 22 25 27
BST.inorder(root);
             
// Removing node with one child
BST.remove(7);
             
//          15
//         /  \
//        10   25
//       / \   / \
//      9  13 22  27
//            /
//           17
             
             
var root = BST.getRootNode();
 
// prints 9 10 13 15 17 22 25 27
BST.inorder(root);
             
// Removing node with two children
BST.remove(15);
     
//          17
//         /  \
//        10   25
//       / \   / \
//      9  13 22  27
 
var root = BST.getRootNode();
console.log("inorder traversal");
 
// prints 9 10 13 17 22 25 27
BST.inorder(root);
             
console.log("postorder traversal");
BST.postorder(root);
console.log("preorder traversal");
BST.preorder(root);

Para obtener más información sobre los árboles binarios, consulte el siguiente artículo: Estructura de datos del árbol binario

Este artículo es una contribución de Sumit Ghosh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.