Arbre binaire dans la structure de données (EXEMPLE)
Sarah Chen
Qu'est-ce qu'un arbre binaire ?
Le mot binaire signifie deux. Dans la structure de données arborescente « Arbre Binaire », désigne un arbre où chaque nœud peut avoir un maximum de deux nœuds enfants (nœuds gauche et droit). C'est un simple arbre binaire.
Cependant, il existe un autre arbre binaire qui est le plus fréquemment utilisé et qui présente plusieurs cas d'utilisation. C'est ce qu'on appelle l'arbre de recherche binaire (BST). Cet arbre peut rendre l'algorithme de recherche beaucoup plus rapide, en enregistrant précisément la complexité temporelle. Dans la structure de données, n signifie le nombre de nœuds dans l'arbre binaire.
Quelles sont les différences entre l’arbre binaire et l’arbre de recherche binaire ?
La différence entre le BST et l'arbre binaire normal réside dans le fait que le nœud gauche BST a une valeur inférieure à celle du nœud racine et que le nœud droit a une valeur plus grande que le nœud racine. Ainsi, le sous-arbre de gauche contiendra toujours une valeur plus petite que la racine, et le sous-arbre de droite contiendra toujours une valeur plus grande que la racine.
Exemple d'arbres de recherche binaires
Prenons l'exemple suivant pour démontrer les concepts de l'arbre de recherche binaire.
Ici, vous pouvez tous les nœuds suivre la discipline donnée. Il existe une formule pour le nombre maximum de nœuds dans l'arborescence de recherche binaire. Si nous observons l'arbre ci-dessus, nous pouvons voir que chaque nœud a deux enfants à l'exception de tous les nœuds feuilles. Et la hauteur (h) de l'arbre binaire donné est 4. La formule est 2h au 1 Février. Cela donne donc 15.
L'image donnée ci-dessus n'est pas un arbre binaire complet ou un arbre binaire équilibré, elle est appelée arbre binaire complet ou arbre binaire équilibré. Il existe une autre structure de données appelée AVL (un autre type d'arbre binaire) qui optimise la hauteur de l'arbre binaire et effectue une recherche plus rapide du BST, comme dans la figure 3.
Essayez de calculer le parcours dans l'ordre de l'arbre binaire donné ci-dessus. Vous constaterez qu'il donnera un tableau trié non décroissant et que les algorithmes de Traversal seront les mêmes que ceux de l'arbre binaire.
Types d'arbre binaire
Voici quelques types importants d’arbre binaire :
- Arbre binaire complet : Chaque nœud peut avoir 0 ou 2 nœuds enfants dans cet arbre binaire. Un seul nœud enfant n'est pas autorisé dans ce type d'arbre binaire. Ainsi, à l’exception du nœud feuille, tous les nœuds auront 2 enfants.
- Arbre binaire complet : Chaque nœud peut avoir 0 ou 2 nœuds. Cela ressemble à l'arbre binaire complet, mais tous les éléments feuilles se penchent vers le sous-arbre gauche, alors que dans l'arbre binaire complet, le nœud peut être dans le sous-arbre droit ou gauche.
- Arbre binaire parfait : Tous les nœuds doivent avoir 0 ou 2 nœuds, et tous les nœuds feuilles doivent être au même niveau ou hauteur. L'exemple ci-dessus d'une structure arborescente binaire complète n'est pas un arbre binaire parfait car le nœud 6 et le nœud 1,2,3 ne sont pas à la même hauteur. Mais l’exemple de l’arbre binaire complet est un arbre binaire parfait.
- Arbre binaire dégénéré : Chaque nœud ne peut avoir qu'un seul enfant. Toutes les opérations telles que la recherche, l'insertion et la suppression prennent un temps O(N).
- Arbre binaire équilibré : Ici, dans cet arbre binaire, la différence de hauteur entre les sous-arbres gauche et droit est d'au plus 1. Ainsi, lors de l'ajout ou de la suppression d'un nœud, nous devons à nouveau équilibrer la hauteur de l'arbre. Ce type d'arbre binaire auto-équilibré est appelé Arborescence AVL.
Il existe trois opérations de base de BST. Ceux-ci sont discutés en détail ci-dessous.
Implémentation de l'arbre binaire en C et 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);
}
Sortie :
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
Implémentation de l'arbre binaire dans 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)
Sortie :
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
Application de l'arbre binaire
Voici quelques applications courantes de l’arbre binaire :
- Organisation des données de nœud dans un ordre trié
- Utilisé dans la carte et définir les objets de nœud dans les bibliothèques de langage de programmation.
- Recherche d'éléments dans les structures de données
» Découvrez notre prochain tutoriel sur Algorithme de combinaison
