Arborescence de recherche binaire en Java

binary search tree java implementation code examples

Essayez Notre Instrument Pour Éliminer Les Problèmes

Sélectionnez Le Système D'Exploitation Choisissez Un Programme De Projection (Éventuellement)

Décrivez Votre Problème

Ce didacticiel couvre l'arborescence de recherche binaire en Java. Vous apprendrez à créer un BST, insérer, supprimer et rechercher un élément, parcourir et implémenter un BST en Java:

Un arbre de recherche binaire (appelé ci-après BST) est un type d'arbre binaire. Il peut également être défini comme un arbre binaire basé sur des nœuds. BST est également appelé «arbre binaire ordonné». Dans BST, tous les nœuds du sous-arbre de gauche ont des valeurs inférieures à la valeur du nœud racine.

De même, tous les nœuds du sous-arbre droit du BST ont des valeurs supérieures à la valeur du nœud racine. Cet ordre des nœuds doit également être vrai pour les sous-arbres respectifs.

=> Visitez ici pour la série exclusive de didacticiels de formation Java.

Ce que vous apprendrez:

Arborescence de recherche binaire en Java
Conclusion
- lecture recommandée

Un BST n'autorise pas les nœuds en double.

Le diagramme ci-dessous montre une représentation BST:

Ci-dessus, un exemple de BST. Nous voyons que 20 est le nœud racine de cet arbre. Le sous-arbre de gauche a toutes les valeurs de nœud qui sont inférieures à 20. Le sous-arbre de droite a tous les nœuds qui sont supérieurs à 20. Nous pouvons dire que l'arbre ci-dessus remplit les propriétés BST.

La structure de données BST est considérée comme très efficace par rapport aux tableaux et aux listes liées en ce qui concerne l'insertion / la suppression et la recherche d'éléments.

BST prend un temps O (log n) pour rechercher un élément. Au fur et à mesure que les éléments sont ordonnés, la moitié du sous-arbre est supprimée à chaque étape de la recherche d'un élément. Cela devient possible car nous pouvons facilement déterminer l'emplacement approximatif de l'élément à rechercher.

De même, les opérations d'insertion et de suppression sont plus efficaces dans BST. Lorsque nous voulons insérer un nouvel élément, nous savons à peu près dans quel sous-arbre (gauche ou droite) nous allons insérer l'élément.

Création d'un arbre de recherche binaire (BST)

Étant donné un tableau d'éléments, nous devons construire un BST.

Procédons comme indiqué ci-dessous:

Tableau donné: 45, 10, 7, 90, 12, 50, 13, 39, 57

Considérons d'abord l'élément supérieur, c'est-à-dire 45, comme le nœud racine. De là, nous allons continuer à créer le BST en considérant les propriétés déjà discutées.

Pour créer un arbre, nous comparerons chaque élément du tableau avec la racine. Ensuite, nous placerons l'élément à une position appropriée dans l'arbre.

L'ensemble du processus de création pour BST est illustré ci-dessous.

BST terminé

Opérations dans l'arborescence de recherche binaire

BST prend en charge diverses opérations. Le tableau suivant présente les méthodes prises en charge par BST en Java. Nous discuterons chacune de ces méthodes séparément.

Méthode / opération	Description
Insérer	Ajoutez un élément au BST en ne violant pas les propriétés BST.
Effacer	Supprimez un nœud donné du BST. Le nœud peut être le nœud racine, non feuille ou feuille.
Chercher	Recherchez l'emplacement de l'élément donné dans le BST. Cette opération vérifie si l'arborescence contient la clé spécifiée.

Insérer un élément dans BST

Un élément est toujours inséré en tant que nœud feuille dans BST.

Vous trouverez ci-dessous les étapes d'insertion d'un élément.

Commencez par la racine.
Comparez l'élément à insérer avec le nœud racine. S'il est inférieur à la racine, parcourez le sous-arbre de gauche ou le sous-arbre de droite.
Parcourez le sous-arbre jusqu'à la fin du sous-arbre souhaité. Insérez le nœud dans le sous-arbre approprié en tant que nœud feuille.

Voyons une illustration de l’opération d’insertion de BST.

Considérez le BST suivant et insérons l'élément 2 dans l'arborescence.

Figure 1

Figure 2

L'opération d'insertion pour BST est illustrée ci-dessus. Dans la fig (1), nous montrons le chemin que nous traversons pour insérer l'élément 2 dans le BST. Nous avons également montré les conditions qui sont vérifiées à chaque nœud. À la suite de la comparaison récursive, l'élément 2 est inséré en tant qu'enfant droit de 1 comme le montre la figure (2).

Opération de recherche dans BST

Pour rechercher si un élément est présent dans le BST, on recommence à partir de la racine puis on traverse le sous-arbre gauche ou droit selon que l'élément à rechercher est inférieur ou supérieur à la racine.

Vous trouverez ci-dessous les étapes que nous devons suivre.

Comparez l'élément à rechercher avec le nœud racine.
Si la clé (élément à rechercher) = racine, renvoie le nœud racine.
Sinon si clé
Sinon, traverse le sous-arbre droit.
Comparez à plusieurs reprises les éléments de sous-arborescence jusqu'à ce que la clé soit trouvée ou que la fin de l'arbre soit atteinte.

Illustrons l'opération de recherche avec un exemple. Considérez que nous devons rechercher la clé = 12.

Dans la figure ci-dessous, nous allons tracer le chemin que nous suivons pour rechercher cet élément.

Comme le montre la figure ci-dessus, nous comparons d'abord la clé avec la racine. Puisque la clé est supérieure, nous traversons le sous-arbre de droite. Dans le sous-arbre de droite, nous comparons à nouveau la clé avec le premier nœud du sous-arbre de droite.

Nous trouvons que la clé est inférieure à 15. Nous passons donc au sous-arbre gauche du nœud 15. Le nœud gauche immédiat de 15 est 12 qui correspond à la clé. À ce stade, nous arrêtons la recherche et renvoyons le résultat.

Supprimer l'élément du BST

Lorsque nous supprimons un nœud du BST, il existe trois possibilités, comme indiqué ci-dessous:

Le nœud est un nœud feuille

Si un nœud à supprimer est un nœud feuille, alors nous pouvons directement supprimer ce nœud car il n'a pas de nœuds enfants. Ceci est montré dans l'image ci-dessous.

Comme indiqué ci-dessus, le nœud 12 est un nœud feuille et peut être supprimé immédiatement.

Le nœud n'a qu'un seul enfant

Lorsque nous devons supprimer le nœud qui a un enfant, nous copions la valeur de l'enfant dans le nœud, puis supprimons l'enfant.

Dans le diagramme ci-dessus, nous voulons supprimer le nœud 90 qui a un enfant 50. Nous échangeons donc la valeur 50 avec 90 puis supprimons le nœud 90 qui est maintenant un nœud enfant.

Le nœud a deux enfants

Lorsqu'un nœud à supprimer a deux enfants, alors nous remplaçons le nœud par le successeur inorder (gauche-racine-droite) du nœud ou simplement dit le nœud minimum dans le sous-arbre de droite si le sous-arbre droit du nœud n'est pas vide. Nous remplaçons le nœud par ce nœud minimum et supprimons le nœud.

Dans le diagramme ci-dessus, nous voulons supprimer le nœud 45 qui est le nœud racine de BST. Nous constatons que le bon sous-arbre de ce nœud n'est pas vide. Ensuite, nous traversons le sous-arbre de droite et trouvons que le nœud 50 est le nœud minimum ici. Nous remplaçons donc cette valeur à la place de 45, puis supprimons 45.

Si nous vérifions l'arbre, nous voyons qu'il remplit les propriétés d'un BST. Le remplacement du nœud était donc correct.

Implémentation de l'arbre de recherche binaire (BST) en Java

Le programme suivant en Java fournit une démonstration de toutes les opérations BST ci-dessus en utilisant le même arbre utilisé dans l'illustration à titre d'exemple.

meilleur nettoyeur de registre pour windows 7 64 bits

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

Production:

Traversée de l'arbre de recherche binaire (BST) en Java

Un arbre est une structure hiérarchique, nous ne pouvons donc pas le parcourir linéairement comme d'autres structures de données telles que des tableaux. Tout type d'arbre doit être parcouru d'une manière spéciale afin que tous ses sous-arbres et nœuds soient visités au moins une fois.

Selon l'ordre dans lequel le nœud racine, le sous-arbre gauche et le sous-arbre droit sont traversés dans un arbre, il existe certains parcours comme indiqué ci-dessous:

Traversée en ordre
Précommande Traversal
Traversée post-commande

Toutes les traversées ci-dessus utilisent la technique de la profondeur d'abord, c'est-à-dire que l'arbre est traversé en profondeur.

Les arbres utilisent également la technique de la largeur en premier pour la traversée. L'approche utilisant cette technique s'appelle 'Ordre des niveaux' traversée.

Dans cette section, nous montrerons chacune des traversées en utilisant le BST suivant comme exemple.

Avec le BST comme indiqué dans le diagramme ci-dessus, le parcours de l'ordre des niveaux pour l'arbre ci-dessus est:

Traversée de l'ordre des niveaux: 10 6 12 4 8

Traversée en ordre

L'approche de traversée en ordre a traversé le BST dans l'ordre, Sous-arbre gauche => RootNode => Sous-arbre droit . La traversée en ordre fournit une séquence décroissante de nœuds d'un BST.

L'algorithme InOrder (bstTree) pour InOrder Traversal est donné ci-dessous.

Traversez le sous-arbre de gauche en utilisant InOrder (left_subtree)
Visitez le nœud racine.
Traversez le sous-arbre droit en utilisant InOrder (right_subtree)

La traversée en ordre de l'arbre ci-dessus est:

4 6 8 10 12

Comme on le voit, la séquence des nœuds à la suite de la traversée dans l'ordre est dans l'ordre décroissant.

Précommande Traversal

Dans le parcours de précommande, la racine est visitée en premier, suivie du sous-arbre gauche et du sous-arbre droit. Le parcours de précommande crée une copie de l'arborescence. Il peut également être utilisé dans les arborescences d'expression pour obtenir une expression de préfixe.

L'algorithme de parcours PreOrder (bst_tree) est donné ci-dessous:

Visitez le nœud racine
Traversez le sous-arbre gauche avec PreOrder (left_subtree).
Traversez le sous-arbre droit avec PreOrder (right_subtree).

Le parcours de précommande pour le BST donné ci-dessus est:

10 6 4 8 12

Traversée post-commande

Le parcours postOrder parcourt le BST dans l'ordre: Sous-arbre gauche-> Sous-arbre droit-> Nœud racine . Le parcours PostOrder est utilisé pour supprimer l'arborescence ou obtenir l'expression suffixe dans le cas d'arbres d'expression.

L'algorithme de traversée postOrder (bst_tree) est le suivant:

Traversez le sous-arbre gauche avec postOrder (left_subtree).
Traversez le sous-arbre droit avec postOrder (right_subtree).
Visitez le nœud racine

Le parcours postOrder pour l'exemple ci-dessus BST est:

4 8 6 12 10

Ensuite, nous implémenterons ces traversées en utilisant la technique de la profondeur d'abord dans une implémentation Java.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Production:

Questions fréquemment posées

Q # 1) Pourquoi avons-nous besoin d'un arbre de recherche binaire?

Répondre : La façon dont nous recherchons des éléments dans la structure de données linéaire comme des tableaux en utilisant la technique de recherche binaire, l'arbre étant une structure hiérarchique, nous avons besoin d'une structure qui puisse être utilisée pour localiser des éléments dans un arbre.

C'est là que vient l'arbre de recherche binaire qui nous aide dans la recherche efficace des éléments dans l'image.

Q # 2) Quelles sont les propriétés d'un arbre de recherche binaire?

Répondre : Un arbre de recherche binaire qui appartient à la catégorie de l'arborescence binaire a les propriétés suivantes:

Les données stockées dans un arbre de recherche binaire sont uniques. Il n'autorise pas les valeurs en double.
Les nœuds du sous-arbre gauche sont inférieurs au nœud racine.
Les nœuds du sous-arbre droit sont plus grands que le nœud racine.

Q # 3) Quelles sont les applications d'un arbre de recherche binaire?

Répondre : Nous pouvons utiliser des arbres de recherche binaires pour résoudre certaines fonctions continues en mathématiques. La recherche de données dans des structures hiérarchiques devient plus efficace avec les arbres de recherche binaires. À chaque étape, nous réduisons la recherche d'un demi-sous-arbre.

Q # 4) Quelle est la différence entre un arbre binaire et un arbre de recherche binaire?

Répondre: Un arbre binaire est une arborescence hiérarchique dans laquelle chaque nœud connu sous le nom de parent peut avoir au plus deux enfants. Un arbre de recherche binaire remplit toutes les propriétés de l'arbre binaire et a également ses propriétés uniques.

Dans un arbre de recherche binaire, les sous-arbres de gauche contiennent des nœuds inférieurs ou égaux au nœud racine et le sous-arbre de droite a des nœuds supérieurs au nœud racine.

Q # 5) L'arbre de recherche binaire est-il unique?

Répondre : Un arbre de recherche binaire appartient à une catégorie d'arbre binaire. Il est unique en ce sens qu'il n'autorise pas les valeurs en double et que tous ses éléments sont classés selon un ordre spécifique.

Conclusion

Les arbres de recherche binaire font partie de la catégorie des arbres binaires et sont principalement utilisés pour rechercher des données hiérarchiques. Il est également utilisé pour résoudre certains problèmes mathématiques.

Dans ce tutoriel, nous avons vu l'implémentation d'un arbre de recherche binaire. Nous avons également vu diverses opérations effectuées sur BST avec leur illustration et également exploré les traversées pour BST.

=> Regardez la série de formation Java simple ici.

Arborescence de recherche binaire en Java - Exemples d'implémentation et de code