in

Árbol de búsqueda binaria | Conjunto 1 (búsqueda e inserción)

gfg 200x200 min

La siguiente es la definición de árbol de búsqueda binaria (BST) según Wikipedia
El árbol de búsqueda binaria es una estructura de datos de árbol binario basada en nodos que tiene las siguientes propiedades:

  • El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo.
  • El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo.
  • El subárbol izquierdo y derecho también debe ser un árbol de búsqueda binaria.
    No debe haber nodos duplicados.

200px-Binary_search_tree.svg

Las propiedades anteriores del árbol de búsqueda binaria proporcionan un orden entre las claves para que las operaciones como la búsqueda, el mínimo y el máximo se puedan realizar rápidamente. Si no hay ningún pedido, es posible que tengamos que comparar cada clave para buscar una clave determinada.

Buscando una clave
Para buscar un valor, si tuviéramos una matriz ordenada, podríamos haber realizado una búsqueda binaria. Digamos que queremos buscar un número en la matriz, lo que hacemos en la búsqueda binaria es primero definir la lista completa como nuestro espacio de búsqueda, el número solo puede existir dentro del espacio de búsqueda. Ahora comparamos el número a buscar o el elemento a buscar con el elemento medio del espacio de búsqueda o la mediana y si el registro que se busca es menor vamos a buscar en la mitad izquierda de lo contrario vamos a buscar en la mitad derecha, en caso de igualdad hemos encontrado el elemento. En la búsqueda binaria comenzamos con ‘norte’ elementos en el espacio de búsqueda y luego, si el elemento medio no es el elemento que estamos buscando, reducimos el espacio de búsqueda a ‘n / 2’ y seguimos reduciendo el espacio de búsqueda hasta que encontramos el registro que estamos buscando o llegamos a un solo elemento en el espacio de búsqueda y terminamos con toda esta reducción.
La operación de búsqueda en el árbol de búsqueda binaria será muy similar. Digamos que queremos buscar el número, lo que haremos es comenzar en la raíz, y luego compararemos el valor a buscar con el valor de la raíz si es igual, terminamos con la búsqueda si es menos, sabemos que tenemos que ir al subárbol izquierdo porque en un árbol de búsqueda binario todos los elementos del subárbol izquierdo son menores y todos los elementos del subárbol derecho son mayores. La búsqueda de un elemento en el árbol de búsqueda binaria es básicamente este recorrido en el que en cada paso iremos hacia la izquierda o hacia la derecha y, por lo tanto, en cada paso descartamos uno de los subárboles. Si el árbol está equilibrado, llamamos a un árbol equilibrado si para todos los nodos la diferencia entre las alturas de los subárboles izquierdo y derecho no es mayor que uno, comenzaremos con un espacio de búsqueda de ‘norte’nodos y cuando descartemos uno de los subárboles descartaremos ‘n / 2’ nodos, por lo que nuestro espacio de búsqueda se reducirá a ‘n / 2’ y luego, en el siguiente paso, reduciremos el espacio de búsqueda a ‘n / 4’ y seguiremos reduciendo así hasta que encontremos el elemento o hasta que nuestro espacio de búsqueda se reduzca a un solo nodo. La búsqueda aquí también es una búsqueda binaria y por eso el nombre árbol de búsqueda binaria.

C ++

struct node* search(struct node* root, int key)

{

    

    if (root == NULL || root->key == key)

       return root;

   

    

    if (root->key < key)

       return search(root->right, key);

    

    return search(root->left, key);

}

Java

public Node search(Node root, int key)

{

    

    if (root==null || root.key==key)

        return root;

    

    if (root.key < key)

       return search(root.right, key);

    

    return search(root.left, key);

}

Pitón

def search(root,key):

    

    

    if root is None or root.val == key:

        return root

    

    if root.val < key:

        return search(root.right,key)

  

    

    return search(root.left,key)

C#

public Node search(Node root,

                   int key)

{

    

    

    if (root == null ||

        root.key == key)

        return root;

   

    if (root.key < key)

       return search(root.right, key);

    

    return search(root.left, key);

}

Javascript

<script>

function search(root, key)

{

    

    

    if (root == null ||

        root.key == key)

        return root;

   

    if (root.key < key)

       return search(root.right, key);

    

    return search(root.left, key);

}

</script>

Ilustración para buscar 6 en el árbol de abajo:
1. Empiece desde la raíz.
2. Compare el elemento de búsqueda con root, si es menor que root, luego recurse para la izquierda, de lo contrario recurse para la derecha.
3. Si el elemento a buscar se encuentra en alguna parte, devuelve verdadero, de lo contrario devuelve falso.

bstsearch

Inserción de una llave
Siempre se inserta una nueva llave en la hoja. Comenzamos a buscar una clave desde la raíz hasta que llegamos a un nodo hoja. Una vez que se encuentra un nodo hoja, el nuevo nodo se agrega como hijo del nodo hoja.

         100                               100
        /           Insert 40            /    
      20     500    --------->          20     500 
     /                                /    
    10   30                           10   30
                                                 
                                              40

C ++

#include <iostream>

using namespace std;

class BST

{

    int data;

    BST *left, *right;

public:

    

    BST();

    

    BST(int);

    

    BST* Insert(BST*, int);

    

    void Inorder(BST*);

};

BST ::BST()

    : data(0)

    , left(NULL)

    , right(NULL)

{

}

BST ::BST(int value)

{

    data = value;

    left = right = NULL;

}

BST* BST ::Insert(BST* root, int value)

{

    if (!root)

    {

        

        return new BST(value);

    }

    

    if (value > root->data)

    {

        

        

        

        root->right = Insert(root->right, value);

    }

    else

    {

        

        

        

        root->left = Insert(root->left, value);

    }

    

    return root;

}

void BST ::Inorder(BST* root)

{

    if (!root) {

        return;

    }

    Inorder(root->left);

    cout << root->data << endl;

    Inorder(root->right);

}

int main()

{

    BST b, *root = NULL;

    root = b.Insert(root, 50);

    b.Insert(root, 30);

    b.Insert(root, 20);

    b.Insert(root, 40);

    b.Insert(root, 70);

    b.Insert(root, 60);

    b.Insert(root, 80);

    b.Inorder(root);

    return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct node {

    int key;

    struct node *left, *right;

};

struct node* newNode(int item)

{

    struct node* temp

        = (struct node*)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

void inorder(struct node* root)

{

    if (root != NULL) {

        inorder(root->left);

        printf("%d n", root->key);

        inorder(root->right);

    }

}

   

 

struct node* insert(struct node* node, int key)

{

    

    if (node == NULL)

        return newNode(key);

    

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

    

    return node;

}

int main()

{

    

              

           

          

         

       

    struct node* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

    

    inorder(root);

    return 0;

}

Java

class BinarySearchTree {

    

       

     

    class Node

    {

        int key;

        Node left, right;

        public Node(int item)

        {

            key = item;

            left = right = null;

        }

    }

    

    Node root;

    

    BinarySearchTree()

    {

         root = null;

    }

    

    void insert(int key)

    {

         root = insertRec(root, key);

    }

    

       

    Node insertRec(Node root, int key)

    {

        

           

        if (root == null)

        {

            root = new Node(key);

            return root;

        }

        

        if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

        

        return root;

    }

    

    void inorder()

    {

         inorderRec(root);

    }

    

    

    void inorderRec(Node root)

    {

        if (root != null) {

            inorderRec(root.left);

            System.out.println(root.key);

            inorderRec(root.right);

        }

    }

    

    public static void main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

        

              

           

          

         

       

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

        

        tree.inorder();

    }

}

Pitón

class Node:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

def insert(root, key):

    if root is None:

        return Node(key)

    else:

        if root.val == key:

            return root

        elif root.val < key:

            root.right = insert(root.right, key)

        else:

            root.left = insert(root.left, key)

    return root

def inorder(root):

    if root:

        inorder(root.left)

        print(root.val)

        inorder(root.right)

r = Node(50)

r = insert(r, 30)

r = insert(r, 20)

r = insert(r, 40)

r = insert(r, 70)

r = insert(r, 60)

r = insert(r, 80)

inorder(r)

C#

using System;

class BinarySearchTree{

    

public class Node

{

    public int key;

    public Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

Node root;

BinarySearchTree()

{

    root = null;

}

void insert(int key)

{

    root = insertRec(root, key);

}

Node insertRec(Node root, int key)

{

    

    

    

    if (root == null)

    {

        root = new Node(key);

        return root;

    }

    

    if (key < root.key)

        root.left = insertRec(root.left, key);

    else if (key > root.key)

        root.right = insertRec(root.right, key);

    

    return root;

}

void inorder()

{

    inorderRec(root);

}

void inorderRec(Node root)

{

    if (root != null)

    {

        inorderRec(root.left);

        Console.WriteLine(root.key);

        inorderRec(root.right);

    }

}

public static void Main(String[] args)

{

    BinarySearchTree tree = new BinarySearchTree();

    

          

       

      

     

   

    tree.insert(50);

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

apple touch icon@2

Crear cadenas de varias líneas en JavaScript

edit

AHCI vs IDE: diferencia y comparación