Arbre binaire dans la structure de données (EXEMPLE)

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, avec précision log(n) time complexité. 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.

Les différences entre l'arbre binaire et l'arbre de recherche binaire

Exemple d'arbres de recherche binaires

Faisons le suiviwing exemple pour démontrer les concepts de l'arbre de recherche binaire.

Exemple d'arbres de recherche binaires

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 - 1. Cela donne donc 15.

Exemple d'arbres de recherche binaires

Exemple d'arbres de recherche binaires

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.

Types d'arbre binaire

  • 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.

Types d'arbre binaire

  • 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).

Types d'arbre binaire

  • 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.

Types d'arbre binaire

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 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)

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