Árbol binario en estructura de datos (EJEMPLO)
sarah chen
¿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, con una complejidad temporal de log(n). En la estructura de datos, n significa la cantidad 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.
Ejemplo de árboles de búsqueda binaria
Veamos el siguiente ejemplo para demostrar los conceptos del árbol 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. Entonces da 15.
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 obtendrá una matriz ordenada no decreciente y que los algoritmos de recorrido 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.
- Á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.
- Á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 solo un hijo. Todas las operaciones, como buscar, insertar y eliminar, toman tiempo O(N).
- Á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.
Existen tres operaciones básicas de BST, que se describen 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.
- Búsqueda de elementos en las estructuras de datos
» Conozca nuestro próximo tutorial sobre Algoritmo de combinación
