Albero binario nella struttura dei dati (ESEMPIO)
Sara Chen
Cos'è un albero binario?
La parola binario significa due. Nella struttura dati dell'albero “Albero Binario”, significa un albero in cui ogni nodo può avere un massimo di due nodi figli (nodi sinistro e destro). È un semplice albero binario.
Tuttavia, c'è un altro albero binario che viene usato più frequentemente e ha diversi casi d'uso. Si chiama Binary Search Tree (BST). Questo albero può rendere l'algoritmo di ricerca molto più veloce, precisamente log(n) di complessità temporale. Nella struttura dati, n indica il numero di nodi nell'albero binario.
Quali sono le differenze tra albero binario e albero di ricerca binario?
La differenza tra il BST e l'albero binario regolare è che il nodo sinistro del BST ha un valore inferiore rispetto al nodo radice e il nodo destro ha un valore maggiore rispetto al nodo radice. Pertanto, il sottoalbero di sinistra conterrà sempre un valore inferiore alla radice e il sottoalbero di destra conterrà sempre un valore maggiore della radice.
Esempio di alberi di ricerca binari
Per dimostrare i concetti dell'albero binario di ricerca, facciamo il seguente esempio.
Qui puoi tutti i nodi seguire la disciplina data. Esiste una formula per il numero massimo di nodi nell'albero di ricerca binaria. Se osserviamo l'albero sopra, possiamo vedere che ogni nodo ha due figli tranne tutti i nodi foglia. E l'altezza (h) del dato albero binario è 4. La formula è 2h - 1. Quindi dà 15.
L'immagine sopra fornita non è un albero binario completo o un albero binario bilanciato, è chiamata albero binario completo o albero binario bilanciato. Esiste un'altra struttura dati chiamata AVL (un altro tipo di albero binario) che ottimizza l'altezza dell'albero binario ed esegue la ricerca più veloce per il BST come in Fig 3.
Prova a calcolare l'attraversamento in ordine dell'albero binario sopra indicato. Scoprirai che fornirà un array ordinato non decrescente e gli algoritmi di attraversamento saranno gli stessi dell'albero binario.
Tipi di albero binario
Ecco alcuni tipi importanti di albero binario:
- Albero binario completo: Ogni nodo può avere 0 o 2 nodi figli in questo albero binario. In questo tipo di albero binario non è consentito un solo nodo figlio. Quindi, ad eccezione del nodo foglia, tutti i nodi avranno 2 figli.
- Albero binario completo: Ogni nodo può avere 0 o 2 nodi. Sembra l'albero binario completo, ma tutti gli elementi foglia sono appoggiati al sottoalbero sinistro, mentre nell'albero binario completo il nodo può trovarsi nel sottoalbero destro o sinistro.
- Albero binario perfetto: Tutti i nodi devono avere 0 o 2 nodi e tutti i nodi foglia devono essere allo stesso livello o altezza. L'esempio sopra di una struttura ad albero binario completa non è un albero binario perfetto perché il nodo 6 e il nodo 1,2,3 non hanno la stessa altezza. Ma l’esempio dell’albero binario completo è un albero binario perfetto.
- Albero binario degenerato: Ogni nodo può avere un solo figlio. Tutte le operazioni come ricerca, inserimento ed eliminazione richiedono tempo O(N).
- Albero binario bilanciato: In questo albero binario, la differenza di altezza del sottoalbero sinistro e destro è al massimo 1. Quindi, mentre aggiungiamo o eliminiamo un nodo, dobbiamo bilanciare nuovamente l'altezza dell'albero. Questo tipo di albero binario autobilanciato è chiamato Albero AVL.
Ci sono tre operazioni base della BST. Questi sono discussi in dettaglio di seguito.
Implementazione dell'albero binario in 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);
}
Produzione:
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
Implementazione dell'albero binario in 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)
Produzione:
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
Applicazione dell'albero binario
Ecco alcune applicazioni comuni di Binary Tree:
- Organizzazione dei dati del nodo in ordine ordinato
- Utilizzato nella mappa e imposta gli oggetti nodo nelle librerie dei linguaggi di programmazione.
- Ricerca di elementi nelle strutture dati
» Scopri il nostro prossimo tutorial su Algoritmo di combinazione
