Qu'est-ce qu'un arbre de recherche binaire ?

Un arbre de recherche binaire est l'une des différentes structures de données qui nous aident à organiser et à trier les données. C'est un moyen efficace de stocker des données dans une hiérarchie et est très flexible.

Dans cet article, nous examinerons de plus près son fonctionnement, ainsi que ses propriétés et ses applications.

Qu'est-ce qu'un arbre de recherche binaire ?

Un arbre de recherche binaire est une structure de données composée de nœuds, similaire aux listes chaînées. Il peut y avoir deux types de nœuds: un parent et un enfant. Le nœud racine est le point de départ de la structure qui se divise en deux nœuds enfants, appelés nœud gauche et nœud droit.

Chaque nœud ne peut être référencé que par son parent, et nous pouvons parcourir les nœuds de l'arbre en fonction de la direction. L'arbre de recherche binaire a trois propriétés principales :

1. Le nœud de gauche est plus petit que son parent.
2. Le nœud de droite est supérieur à son parent.
3. Les sous-arbres gauche et droit doivent être des arbres de recherche binaire.

Un arbre de recherche binaire parfait est obtenu lorsque tous les niveaux sont remplis et que chaque nœud a un nœud enfant gauche et droit.

En rapport: Bibliothèques de science des données pour Python que chaque scientifique de données devrait utiliser

Opérations de base d'un arbre de recherche binaire

Maintenant que vous avez une meilleure idée de ce qu'est un arbre de recherche binaire, nous pouvons examiner ses opérations de base ci-dessous.

1. Opération de recherche

La recherche permet de localiser une valeur particulière présente dans l'arbre. Nous pouvons utiliser deux types de recherches: la recherche en largeur d'abord (BFS) et la recherche en profondeur d'abord (DFS). La recherche en largeur d'abord est un algorithme de recherche qui commence au nœud racine et traverse horizontalement, côte à côte, jusqu'à ce que l'objectif soit trouvé. Chaque nœud est visité une fois au cours de cette recherche.

En revanche, la recherche en profondeur parcourt l'arbre verticalement, en partant du nœud racine et en descendant sur une seule branche. Si l'objectif est trouvé, l'opération se termine. Mais sinon, il et recherche les autres nœuds.

2. Opération d'insertion

L'opération d'insertion utilise l'opération de recherche pour déterminer l'emplacement où le nouveau nœud doit être inséré. Le processus commence à partir du nœud racine et la recherche commence jusqu'à ce que la destination soit atteinte. Il y a trois cas à considérer avec l'insertion.

• Cas 1: Lorsqu'aucun nœud n'existe. Le nœud à insérer deviendra le nœud racine.

• Cas 2: Il n'y a pas d'enfants. Dans ce cas, le nœud sera comparé au nœud racine. S'il est plus grand, il deviendra le bon enfant; sinon, il deviendra l'enfant de gauche.

• Cas 3: Lorsque la racine et ses enfants sont présents. Le nouveau nœud sera comparé à chaque nœud sur son chemin pour déterminer quel nœud il visitera ensuite. Si le nœud est plus grand que le nœud racine, il traversera le sous-arbre droit ou bien le gauche. De même, des comparaisons sont faites à chaque niveau pour déterminer s'il ira à droite ou à gauche jusqu'à ce qu'il arrive à destination.

3. Supprimer l'opération

L'opération de suppression est utilisée pour supprimer un nœud particulier dans l'arborescence. La suppression est considérée comme délicate car après avoir supprimé un nœud, l'arbre doit être réorganisé en conséquence. Il y a trois cas principaux à considérer :

• Cas 1: suppression d'un nœud feuille. Un nœud feuille est un nœud sans enfant. C'est le plus facile à supprimer car il n'affecte aucun autre nœud; nous parcourons simplement l'arbre jusqu'à ce que nous l'atteignions et le supprimions.

• Cas 2: suppression d'un nœud avec un enfant. La suppression d'un parent avec un nœud entraînera la prise de position de l'enfant et tous les nœuds suivants monteront d'un niveau. Il n'y aura aucun changement dans la structure des sous-arbres.

• Cas 3: Suppression d'un nœud avec deux enfants. Lorsque nous devons supprimer un nœud avec deux enfants, nous devons d'abord trouver un nœud suivant qui peut prendre sa position. Deux nœuds peuvent remplacer le nœud supprimé, le successeur ou prédécesseur inorder. Le successeur dans l'ordre est l'enfant le plus à gauche du sous-arbre de droite et le prédécesseur dans l'ordre est l'enfant le plus à droite du sous-arbre de gauche. Nous copions le contenu du successeur/prédécesseur sur le nœud et supprimons le successeur/prédécesseur dans l'ordre.

En rapport: Comment créer des structures de données avec les classes JavaScript ES6

Comment parcourir un arbre de recherche binaire

La traversée est le processus par lequel nous naviguons dans un arbre de recherche binaire. Il s'agit de localiser un élément spécifique ou d'imprimer un aperçu de l'arbre. Nous partons toujours du nœud racine et devons suivre les bords pour atteindre les autres nœuds. Chaque nœud doit être considéré comme un sous-arbre et le processus est répété jusqu'à ce que tous les nœuds soient visités.

• Traversée dans l'ordre : La traversée dans l'ordre produira une carte dans l'ordre croissant. Avec cette méthode, nous commençons par le sous-arbre gauche et continuons jusqu'au sous-arbre racine et droit.

• Traversée de précommande : Dans cette méthode, le nœud racine est visité en premier, suivi du sous-arbre gauche et du sous-arbre droit.

• Traversée post-commande : Cette traversée implique de visiter le nœud racine en dernier. Nous commençons par le sous-arbre gauche, puis le sous-arbre droit, puis le nœud racine.

Applications du monde réel

Alors, comment utilisons-nous les algorithmes d'arbre de recherche binaire? Comme on peut le supposer, ils sont extrêmement efficaces pour rechercher et trier. La plus grande force des arbres binaires est leur structure organisée. Il permet d'effectuer des recherches à des vitesses remarquables en réduisant de moitié la quantité de données que nous devons analyser par passe.

Les arbres de recherche binaire nous permettent de maintenir efficacement un ensemble de données changeant dynamiquement sous une forme organisée. Pour les applications dans lesquelles des données sont insérées et supprimées fréquemment, elles sont très utiles. Les moteurs de jeux vidéo utilisent un algorithme basé sur des arbres connus sous le nom de partition d'espace binaire pour aider à rendre les objets ordonnés. Microsoft Excel et la plupart des tableurs utilisent des arbres binaires comme structure de données de base.

Vous pourriez être surpris d'apprendre que le code Morse utilise un arbre de recherche binaire pour coder les données. Une autre raison importante pour laquelle les arbres de recherche binaire sont si utiles est leurs multiples variations. Leur flexibilité a conduit à la création de nombreuses variantes pour résoudre toutes sortes de problèmes. Lorsqu'ils sont utilisés correctement, les arbres de recherche binaire sont un grand atout.

Arbres de recherche binaire: le point de départ parfait

L'un des principaux moyens d'évaluer l'expertise d'un ingénieur est sa connaissance et son application des structures de données. Les structures de données sont utiles et peuvent aider à créer un système plus efficace. Les arbres de recherche binaire sont une excellente introduction aux structures de données pour tout développeur débutant.

15 méthodes de tableau JavaScript que vous devriez maîtriser aujourd'hui

Vous voulez comprendre les tableaux JavaScript mais vous n'arrivez pas à les maîtriser? Consultez nos exemples de tableaux JavaScript pour obtenir des conseils.

Lire la suite

A propos de l'auteur