Árbol binario en estructura de datos (EJEMPLO)

¿Qué es un árbol binario?

La palabra binario significa dos. En la estructura de datos del árbol, "árbol binario" significa un árbol donde cada nodo puede tener un máximo de dos nodos secundarios (nodos izquierdo y derecho). Es un árbol binario simple.

Sin embargo, existe otro árbol binario que se utiliza con mayor frecuencia y tiene varios casos de uso. Se llama árbol de búsqueda binaria (BST). Este árbol puede hacer que el algoritmo de búsqueda sea mucho más rápido, precisamente log(n) tiempo complexidad. En la estructura de datos, n significa el número de nodos en el árbol binario.

¿Cuáles son las diferencias entre el árbol binario y el árbol de búsqueda binaria?

La diferencia entre el BST y el árbol binario normal es que el nodo izquierdo del BST tiene un valor menor que el nodo raíz, y el nodo derecho tiene un valor mayor que el nodo raíz. Entonces, el subárbol izquierdo siempre contendrá un valor menor que la raíz, y el subárbol derecho siempre contendrá un valor mayor que la raíz.

Las diferencias entre el árbol binario y el árbol de búsqueda binaria

Ejemplo de árboles de búsqueda binaria

tengamos el siguientewing ejemplo para demostrar los conceptos del árbol de búsqueda binaria.

Ejemplo de árboles de búsqueda binaria

Aquí puedes todos los nodos seguir la disciplina dada. Existe una fórmula para el número máximo de nodos en el árbol de búsqueda binaria. Si observamos el árbol de arriba, podemos ver que cada nodo tiene dos hijos excepto todos los nodos hoja. Y la altura (h) del árbol binario dado es 4. La fórmula es 2h 1 Mayo. Entonces da 15.

Ejemplo de árboles de búsqueda binaria

Ejemplo de árboles de búsqueda binaria

La imagen dada arriba no es un árbol binario completo o un árbol binario equilibrado, se llama árbol binario completo o árbol binario equilibrado. Hay otra estructura de datos llamada AVL (otro tipo de árbol binario) que optimiza la altura del árbol binario y realiza una búsqueda más rápida del BST como en la figura 3.

Intente calcular el recorrido en orden del árbol binario indicado anteriormente. Descubrirá que proporcionará una matriz ordenada no decreciente y que los algoritmos transversales serán los mismos que los del árbol binario.

Tipos de árbol binario

A continuación se muestran algunos tipos importantes de árbol binario:

  • Árbol binario completo: Cada nodo puede tener 0 o 2 nodos secundarios en este árbol binario. En este tipo de árbol binario no se permite sólo un nodo hijo. Entonces, excepto el nodo hoja, todos los nodos tendrán 2 hijos.

Tipos de árbol binario

  • Árbol binario completo: Cada nodo puede tener 0 o 2 nodos. Parece el árbol binario completo, pero todos los elementos de la hoja están inclinados hacia el subárbol izquierdo, mientras que en el árbol binario completo el nodo puede estar en el subárbol derecho o izquierdo.

Tipos de árbol binario

  • Árbol binario perfecto: Todos los nodos deben tener 0 o 2 nodos, y todos los nodos de las hojas deben estar al mismo nivel o altura. El ejemplo anterior de una estructura de árbol binario completo no es un árbol binario perfecto porque el nodo 6 y el nodo 1,2,3 no están a la misma altura. Pero el ejemplo del árbol binario completo es un árbol binario perfecto.
  • Árbol binario degenerado: Cada nodo puede tener un solo hijo. Todas las operaciones como searching, insertar y eliminar toman O(N) tiempo.

Tipos de árbol binario

  • Árbol binario equilibrado: En este árbol binario, la diferencia de altura del subárbol izquierdo y derecho es como máximo 1. Entonces, al agregar o eliminar un nodo, debemos equilibrar la altura del árbol nuevamente. Este tipo de árbol binario autoequilibrado se llama Árbol AVL.

Tipos de árbol binario

Hay tres operaciones básicas de BST. Estos se analizan en detalle a continuación.

Implementación de árbol binario en C y C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
   int value;
   struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
   struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
   tempNode->value = val;
   tempNode->left = NULL;
   tempNode->right = NULL;
   return tempNode;
}
struct Node *successor(struct Node *node)
{
    struct Node *present = node;
// going to the left most node
    while (present != NULL && present->left != NULL)
    {
       present = present->left;
    }
     return present;
 }
struct Node *insert(struct Node *node, int value)
{
   if (node == NULL)
   {
      return getEmptynode(value);
   }
   if (value < node->value)
   {
      node->left = insert(node->left, value);
   }
   else
   {
      node->right = insert(node->right, value);
   }
      return node;
}
int searchInBST(struct Node *node, int value)
{
   struct Node *current = node;
   while (current->value != value)
    {
    if (current->value > value)
      {
      current = current->left;
      }
    else
     {
     current = current->right;
     }
   if (current == NULL)
     {
    return 0;
     }
   }
return 1;
}
void inorder(struct Node *root)
{
 if (root != NULL)
  {
   inorder(root->left);
   cout << root->value << " ";
   inorder(root->right);
  }
}
struct Node *deleteNode(struct Node *node, int value)
{
 if (node == NULL)
  {
   return node;
  }
 if (value < node->value)
  {
   node->left = deleteNode(node->left, value);
  }
else if (value > node->value)
 {
   node->right = deleteNode(node->right, value);
 }
else
{
if (node->left == NULL)
 {
 struct Node *temp = node->right;
 free(node);
 return temp;
 }
 else if (node->right == NULL)
 {
 struct Node *temp = node->left;
 free(node);
 return temp;
  }
 struct Node *temp = successor(node->right);
 node->value = temp->value;
 node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
 {
  struct Node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 4);
  root = insert(root, 12);
  root = insert(root, 2);
  root = insert(root, 6);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 1);
  root = insert(root, 3);
  root = insert(root, 5);
  root = insert(root, 7);
  root = insert(root, 9);
  root = insert(root, 11);
  root = insert(root, 13);
  root = insert(root, 15);

 cout << "InOrder Traversal after inserting all nodes: " << endl;
 inorder(root);
 root = insert(root, -10);
 cout << "\nInOrder Traversal after inserting -10 : " << endl;
 inorder(root);
 cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
 cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
 root = deleteNode(root,8);
 cout<<"After deleting node 8, inorder traversal: "<<endl;
 inorder(root);
 root = deleteNode(root,-10);
 cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
 inorder(root);
}

Salida:

InOrder Traversal after inserting all nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 :
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: 0
Searching -10 in the BST: 1

After deleting node 8, inorder traversal:
-10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal:
1 2 3 4 5 6 7 9 10 11 12 13 14 15

Implementación del árbol binario en Python

class Node:
def __init__(self,value):
      self.left = None
      self.right = None
      self.value = value
def insert(root,value):
      if root == None:
          return Node(value)
      if value< root.value:
          root.left = insert(root.left,value)
      else:
          root.right = insert(root.right,value)
          return root
  def searchInBST(root,value):
      current = root
  while current.value != value:
  if current.value > value:
      current = current.left
  else:
      current = current.right
  if current == None:
      return "Not found"
      return "Found"
def inorder(root):
    if root != None:
      inorder(root.left)
      print(root.value,end=" ")
      inorder(root.right)
def successor(root):
    present = root
    while present != None and present.left != None:
    present = present.left
      return present
def deleteNode(root,value):
    if root == None:
      return root
    if value < root.value:
        root.left = deleteNode(root.left, value)
    elif value>root.value:
        root.right = deleteNode(root.right, value)
    else:
    if root.left == None:
        temp = root.right
        root = None
        return temp
    elif root.right == None:
        temp = root.left
        root = None
        return temp
        temp = successor(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)
        return root
        root = Node(8)
        root = insert(root, 4)
        root = insert(root, 12)
        root = insert(root, 2)
        root = insert(root, 6)
        root = insert(root, 10)
        root = insert(root, 14)
        root = insert(root, 1)
        root = insert(root, 3)
        root = insert(root, 5)
        root = insert(root, 7)
        root = insert(root, 9)
        root = insert(root, 11)
        root = insert(root, 13)
        root = insert(root, 15)
  print("InOrder Traversal after inserting all nodes: ")
  inorder(root)
  root = insert(root, -10)
  print("\nInOrder Traversal after inserting -10 : ")
  inorder(root)
  print("\nSearching -5 in the BST: ",searchInBST(root, -5))
  print("Searching -5 in the BST: ",searchInBST(root, -10))
  root = deleteNode(root,8)
  print("After deleting node 8, inorder traversal:")
  inorder(root)
  root = deleteNode(root,-10)
  print("\nAfter deleting node -10, inorder traversal:")
  inorder(root)

Salida:

InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Searching -5 in the BST: Not found 

Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

Aplicación del árbol binario

Estas son algunas aplicaciones comunes del árbol binario:

  • Organizar los datos de los nodos en orden
  • Se utiliza en el mapa y establece objetos de nodo en bibliotecas de lenguajes de programación.
  • Searching para elementos en las estructuras de datos

» Conozca nuestro próximo tutorial sobre Algoritmo de combinación