Árvore binária na estrutura de dados (EXEMPLO)
Sarah Chen
O que é uma árvore binária?
A palavra binário significa dois. Na estrutura de dados em árvore, “Árvore Binária” significa uma árvore onde cada nó pode ter no máximo dois nós filhos (nós esquerdo e direito). É uma árvore binária simples.
No entanto, há outra árvore binária que é usada com mais frequência e possui vários casos de uso. É chamada de Árvore de Pesquisa Binária (BST). Essa árvore pode tornar o algoritmo de busca muito mais rápido, precisamente log(n) de complexidade de tempo. Na estrutura de dados, n significa o número de nós na árvore binária.
Quais são as diferenças entre a árvore binária e a árvore de pesquisa binária?
A diferença entre o BST e a árvore binária normal é que o nó esquerdo do BST tem um valor menor que o nó raiz, e o nó direito tem um valor maior que o nó raiz. Portanto, a subárvore esquerda sempre conterá um valor menor que a raiz, e a subárvore direita sempre conterá um valor maior que a raiz.
Exemplo de árvores de pesquisa binária
Vejamos o exemplo a seguir para demonstrar os conceitos da Árvore de Pesquisa Binária.
Aqui você pode todos os nós seguirem a disciplina dada. Existe uma fórmula para o número máximo de nós na árvore de pesquisa binária. Se observarmos a árvore acima, podemos ver que cada nó tem dois filhos, exceto todos os nós folha. E a altura (h) da árvore binária fornecida é 4. A fórmula é 2h - 1. Então, dá 15.
A imagem fornecida acima não é uma árvore binária completa ou árvore binária balanceada, é chamada de árvore binária completa ou árvore binária balanceada. Existe outra Estrutura de Dados chamada AVL (outro tipo de Árvore Binária) que otimiza a altura da Árvore Binária e realiza a busca mais rápida pelo BST como na Figura 3.
Tente calcular o percurso em ordem da árvore binária fornecida acima. Você descobrirá que isso fornecerá uma matriz classificada não decrescente e os algoritmos Traversal serão iguais aos da Árvore Binária.
Tipos de árvore binária
Aqui estão alguns tipos importantes de árvore binária:
- Árvore binária completa: Cada nó pode ter 0 ou 2 nós filhos nesta árvore binária. Apenas um nó filho não é permitido neste tipo de árvore binária. Portanto, exceto o nó folha, todos os nós terão 2 filhos.
- Árvore binária completa: Cada nó pode ter 0 ou 2 nós. Parece a árvore binária completa, mas todos os elementos folha estão inclinados para a subárvore esquerda, enquanto na árvore binária completa o nó pode estar na subárvore direita ou esquerda.
- Árvore binária perfeita: Todos os nós devem ter 0 ou 2 nós e todos os nós folha devem estar no mesmo nível ou altura. O exemplo acima de uma estrutura de árvore binária completa não é uma árvore binária perfeita porque o nó 6 e o nó 1,2,3 não estão na mesma altura. Mas o exemplo da Árvore Binária Completa é uma árvore binária perfeita.
- Árvore binária degenerada: Cada nó pode ter apenas um único filho. Todas as operações como pesquisar, inserir e excluir levam tempo O(N).
- Árvore binária balanceada: Aqui nesta árvore binária, a diferença de altura das subárvores esquerda e direita é no máximo 1. Portanto, ao adicionar ou excluir um nó, precisamos equilibrar a altura da árvore novamente. Este tipo de árvore binária auto-equilibrada é chamada de Árvore AVL.
Existem três operações básicas do BST. Eles são discutidos em detalhes abaixo.
Implementação de árvore binária em C e 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);
}
Saída:
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
Implementação de árvore binária em 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)
Saída:
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
Aplicação de Árvore Binária
Aqui estão algumas aplicações comuns da árvore binária:
- Organizando dados do nó em ordem classificada
- Usado no mapa e no conjunto de objetos em bibliotecas de linguagens de programação.
- Procurando por elementos nas estruturas de dados
» Aprenda nosso próximo tutorial sobre Algoritmo de Combinação
