Tout ce que vous devez savoir sur les structures de données arborescentes

Lorsque vous apprenez à coder pour la première fois, il est courant d’apprendre les tableaux comme  » structure de données principale « .

Éventuellement, vous apprendrez aussi à connaître hash tables. Si vous poursuivez des études en informatique, vous devez suivre un cours sur la structure de données. Vous apprendrez également à connaître linked listsqueues et stacks. Ces structures de données sont appelées structures de données  » linéaires  » parce qu’elles ont toutes un début et une fin logiques.

Lorsque nous commençons à apprendre à propos de trees et graphs, cela peut devenir vraiment confus. Nous ne stockons pas les données de manière linéaire. Les deux structures de données stockent les données d’une manière spécifique.

Ce billet a pour but de vous aider à mieux comprendre la structure de données arborescente et de clarifier toute confusion que vous pourriez avoir à son sujet.

Dans cet article, nous allons apprendre :

• Ce qu’est un arbre
• Des exemples d’arbres
• Sa terminologie et son fonctionnement
• Comment mettre en œuvre des structures arborescentes dans le code.

Commençons ce voyage d’apprentissage. 🙂

Définition

Lorsque l’on débute en programmation, il est courant de mieux comprendre les structures de données linéaires que les structures de données comme les arbres et les graphes.

Les arbres sont bien connus comme étant une structure de données non linéaire. Ils ne stockent pas les données de manière linéaire. Ils organisent les données de manière hiérarchique.

Plongeons-nous dans des exemples concrets !

Qu’est-ce que je veux dire quand je dis de manière hiérarchique ?

Imaginez un arbre généalogique avec des relations de toutes les générations : grands-parents, parents, enfants, frères et sœurs, etc. Nous organisons communément les arbres généalogiques de manière hiérarchique.

Le dessin ci-dessus est est mon arbre généalogique. Tossico, Akikazu, Hitomi, et Takemi sont mes grands-parents.

Toshiaki et Juliana sont mes parents.

TK, Yuji, Bruno, et Kaio sont les enfants de mes parents (moi et mes frères).

La structure d’une organisation est un autre exemple de hiérarchie.

En HTML, le modèle d’objet de document (DOM) fonctionne comme un arbre.

La balise HTML contient d’autres balises. Nous avons une balise head et une balise body. Ces balises contiennent des éléments spécifiques. La balise head comporte les balises meta et title. La balise body comporte des éléments qui apparaissent dans l’interface utilisateur, par exemple, h1ali, etc.

Une définition technique

Une tree est une collection d’entités appelées nodes. Les nœuds sont reliés par edges. Chaque node contient une value ou une data, et elle peut avoir ou non une child node .

La first node de la tree est appelée la root. Si cette root node est reliée par une autre node, la root est alors une parent node et la node connectée est une child.

Toutes les Tree nodes sont reliées par des liens appelés edges. C’est une partie importante de trees, car elle gère la relation entre nodes.

Leaves sont les derniers nodes sur un tree. Ce sont des nœuds sans enfants. Comme de vrais arbres, on a le rootbranches, et enfin le leaves.

Les autres notions importantes à comprendre sont height et depth.

La height d’une tree est la longueur du plus long chemin vers une leaf.

La depth d’une node est la longueur du chemin vers sa root.

Résumé terminologique

• La racine est la node la plus haute de la tree
• La bordure est le lien entre deux nodes

.

• L’enfant est une node qui a une parent node
• Le parent est . une node qui a une edge à une child node.
• La feuille est une node qui ne possède pas de child node dans la tree
• La hauteur est la longueur du chemin le plus long vers une leaf
• La profondeur est la longueur du chemin vers son root

Arbres binaires

Nous allons maintenant aborder un type spécifique de tree. Nous l’appelons lebinary tree.

« En informatique, un arbre binaire est une structure de données arborescente dans laquelle chaque nœud a au plus deux enfants, que l’on appelle l’enfant gauche et l’enfant droit. » – Wikipédia

Voyons donc un exemple d’un binary tree.

Codons un arbre binaire

La première chose que nous devons garder à l’esprit lorsque nous implémentons un binary tree est qu’il s’agit d’une collection de nodes. Chaque node possède trois attributs : valueleft_child, et right_child.

Comment mettre en œuvre une simple binary tree qui s’initialise avec ces trois propriétés ?

Voyons cela.

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None

Voici. Notre classe binary tree.

Lorsque nous instancions un objet, nous passons le value (les données du nœud) en paramètre. Regardez le left_child et le right_child. Les deux sont définis sur None.

Pourquoi ?

Parce que lorsque nous créons notre node, elle n’a pas d’enfants. Nous avons juste le node data.

Testons-le :

tree = BinaryTree('a')print(tree.value) # aprint(tree.left_child) # Noneprint(tree.right_child) # None

C’est tout.

Nous pouvons passer le stringa‘ comme value à notre Binary Tree node. Si nous imprimons les valueleft_child, et right_child, nous pouvons voir les valeurs.

Passons à la partie insertion. Que devons-nous faire ici ?

Nous allons implémenter une méthode pour insérer un nouveau node à la right et à la left.

Voici les règles :

• Si la node actuelle n’a pas de left child, nous créons simplement une nouvelle nodeet la fixons à la left_child du nœud actuel.
• Si elle possède bien la left child, nous créons un nouveau nœud et le mettons à la place de la left child actuelle. Allouez cette left child node à la left child du nouveau nœud.

Dessinons-le. 🙂

Voici le code :

Encore, si le nœud actuel n’a pas de left child, nous créons simplement un nouveau nœud et le définissons sur la left_child du nœud actuel. Ou bien nous créons un nouveau nœud et le mettons à la place de la left child actuelle. Affectons cette left child node à la left child du nouveau nœud.

Et nous faisons la même chose pour insérer une right child node.

Fait. 🙂

Mais pas entièrement. Nous devons encore le tester.

Construisons letree:

Pour résumer l’illustration de cet arbre :

• anode sera la root de notre binary Tree.
• aleft child est bnode.
• a right child est cnode.
• bright child est dnodebnode n’a pas de left child)
• cleft child est enode
• cright child est fnode
• à la fois e et fnodes n’ont pas d’enfants

Voici donc le code pour la tree :

L’insertion est faite.

Maintenant nous devons penser à la traversée de tree.

Nous avons deux options ici : La recherche en profondeur (DFS) et la recherche en largeur (BFS).

• La DFS « est un algorithme de traversée ou de recherche de structure de données en arbre. On commence à la racine et on explore aussi loin que possible le long de chaque branche avant de revenir en arrière. » – Wikipédia
• BFS « est un algorithme de traversée ou de recherche de structure de données en arbre. Il commence à la racine de l’arbre et explore d’abord les nœuds voisins, avant de passer aux voisins du niveau suivant. » – Wikipédia

Par conséquent, plongeons dans chaque type de traversée d’arbre.

Recherche en profondeur (DFS)

DFS explore un chemin jusqu’à une feuille avant de revenir en arrière et d’explorer un autre chemin. Voyons un exemple avec ce type de traversée.

Le résultat pour cet algorithme sera 1-2-3-4-5-6-7.

Pourquoi ?

Décomposons-le.

1. Débutez au root (1). Imprimez-le.

2. Allez à la left child (2). Imprimez-le.

3. Allez ensuite dans la left child (3). Imprimez-la. (Cette node n’a pas d’enfants)

4. Revenez en arrière et allez à la right child (4). Imprimez-la. (Cette node n’a pas d’enfants)

5. Revenez à la rootnode et allez à la right child (5). Imprimez-le.

6. Allez à la left child (6). Imprimez-le. (Cette node n’a pas d’enfants)

7. Revenez en arrière et allez à la right child (7). Imprimez-le. (Ce node n’a pas d’enfants)

8. Fait.

Lorsque nous allons profondément dans la feuille et que nous revenons en arrière, cela s’appelle l’algorithme DFS.

Maintenant que nous sommes familiers avec cet algorithme de traversée, nous allons discuter des types de DFS : pre-orderin-order, et post-order.

Pré-commande

C’est exactement ce que nous avons fait dans l’exemple ci-dessus.

1. Imprimer la valeur de la node.
2. Aller à la left child et l’imprimer. C’est si, et seulement si, il a une left child.
3. Allez à la right child et imprimez-la. Ceci si, et seulement si, il possède une right child.

En ordre

Le résultat de l’algorithme en ordre pour cet tree exemple est 3-2-4-1-6-5-7.

La gauche en premier, le milieu en second et la droite en dernier.

Maintenant, codons-le.

def in_order(self): if self.left_child: self.left_child.in_order() print(self.value) if self.right_child: self.right_child.in_order()

1. Voir la left child et l’imprimer. C’est si, et seulement si, elle a une left child.
2. Imprimer la valeur de la node
3. Aller à la right child et l’imprimer. Ceci si, et seulement si, il possède une right child.

Post-ordre

Le résultat de l’algorithme post order pour cet tree exemple est 3-4-2-6-7-5-1.

La gauche en premier, la droite en second et le milieu en dernier.

Codons cela.

1. Aller dans la left child et l’imprimer. C’est si, et seulement si, il a une left child.
2. Allez à la right child et imprimez-la. Ceci si, et seulement si, il possède une right child.
3. Imprimer la valeur de la node

Recherche en largeur et en premier (BFS)

L’algorithme BFS parcourt la tree niveau par niveau et profondeur par profondeur.

Voici un exemple qui permet de mieux expliquer cet algorithme :

On traverse donc niveau par niveau. Dans cet exemple, le résultat est 1-2-5-3-4-6-7.

• Niveau/profondeur 0 : uniquement node avec la valeur 1
• Niveau/profondeur 1 : nodes avec les valeurs 2 et 5
• Niveau/Profondeur 2 : nodes avec les valeurs 3, 4, 6 et 7

Maintenant, codons-le.

Pour mettre en œuvre un algorithme BFS, nous utilisons la structure de données queue pour nous aider.

Comment cela fonctionne-t-il ?

Voici l’explication.

1. Premièrement, ajoutez la rootnode dans la queue avec la méthode put.
2. Itérez tant que la queue n’est pas vide.
3. Recevoir le premier node dans le queue, puis imprimer sa valeur.
4. Ajouter à la fois left et rightchildren dans la queue (si la node actuelle a children).
5. Fait. Nous allons imprimer la valeur de chaque node, niveau par niveau, avec notre queue aide.

Arbre de recherche binaire

« Un arbre de recherche binaire est parfois appelé arbre binaire ordonné ou trié, et il conserve ses valeurs dans un ordre trié, de sorte que la recherche et d’autres opérations peuvent utiliser le principe de la recherche binaire » – Wikipédia

Une propriété importante d’un Binary Search Tree est que la valeur d’une Binary Search Treenode est plus grande que la valeur de la descendance de sa left child, mais inférieure à la valeur de la descendance de son right child.« 

Voici une décomposition de l’illustration ci-dessus :

• A est inversé. Le subtree 7-5-8-6 doit être à droite, et le subtree 2-1-3 doit être à gauche.
• B est la seule option correcte. Elle satisfait à la propriété Binary Search Tree.
• C a un problème : le node avec la valeur 4. Il doit être à gauche du root car il est plus petit que 5.

Codons un arbre de recherche binaire!

Maintenant il est temps de coder!

Que verrons-nous ici ? Nous allons insérer de nouveaux nœuds, rechercher une valeur, supprimer des nœuds, et le bilan de la tree.

Commençons.

Insertion : ajouter de nouveaux nœuds à notre arbre

Imaginez que nous avons une tree vide et que nous voulons ajouter de nouvelles nodes avec les valeurs suivantes dans cet ordre : 50, 76, 21, 4, 32, 100, 64, 52.

La première chose que nous devons savoir est si 50 est la root de notre arbre.

Nous pouvons maintenant commencer à insérer node par node.

• 76 est supérieur à 50, donc insérer 76 à droite.
• 21 est inférieur à 50, donc insérer 21 à gauche.
• 4 est inférieur à 50. Node avec la valeur 50 a une left child 21. Puisque 4 est plus petit que 21, insérez-le sur le côté gauche de cette node.
• 32 est plus petit que 50. Node avec la valeur 50 a une left child 21. Puisque 32 est supérieur à 21, insérez 32 à droite de cette node.
• 100 est supérieur à 50. Node avec la valeur 50 a une right child 76. Puisque 100 est supérieur à 76, insérez 100 à droite de cette node.
• 64 est supérieur à 50. Node avec la valeur 50 a une right child 76. Puisque 64 est plus petit que 76, insérez 64 sur le côté gauche de cette node.
• 52 est supérieur à 50. Node avec la valeur 50 a une right child 76. Puisque 52 est plus petit que 76, node avec la valeur 76 a une left child 64. 52 est plus petit que 64, donc insérez 54 sur le côté gauche de cette node.

Vous remarquez un modèle ici ?

Décomposons-le.

1. La nouvelle valeur de node est-elle supérieure ou inférieure à la valeur actuelle de node ?
2. Si la valeur de la nouvelle node est supérieure à la node, actuelle, passez à la subtree de droite. Si la node actuelle n’a pas de right child, insérez-la à cet endroit, sinon revenez à l’étape #1.
3. Si la valeur de la nouvelle node est inférieure à celle de la node actuelle, passez à la subtree de gauche. Si la node actuelle n’a pas de left child, insérez-la à cet endroit, sinon revenez à l’étape #1.
4. Nous n’avons pas traité les cas particuliers ici. Lorsque la valeur d’une nouvelle node est égale à la valeur actuelle de la node,, utilisez la règle numéro 3. Pensez à insérer des valeurs égales à gauche du subtree.

Maintenant, codons-le.

Il semble très simple.

La partie puissante de cet algorithme est la partie récursion, qui se trouve à la ligne 9 et à la ligne 13. Les deux lignes de code appellent la méthode insert_node, et l’utilisent pour ses left et rightchildren, respectivement. Les lignes 11 et 15 sont celles qui font l’insertion pour chaque child.

Recherche de la valeur du nœud… Ou pas…

L’algorithme que nous allons construire maintenant consiste à faire des recherches. Pour une valeur donnée (nombre entier), nous allons dire si notre Binary Search Tree possède ou non cette valeur.

Un élément important à noter est la façon dont nous avons défini l’algorithme d’insertion d’arbre. Nous avons d’abord notre rootnode. Toutes les subtreenodes de gauche auront des valeurs plus petites que la rootnode. Et toutes les bonnes subtreenodes auront des valeurs supérieures à la rootnode.

Regardons un exemple.

Imaginez que nous avons cette tree.

Nous voulons maintenant savoir si nous avons un nœud basé sur la valeur 52.

Décomposons.

1. Nous commençons avec la rootnode comme notre node actuelle. La valeur donnée est-elle plus petite que la valeur actuelle de node ? Si oui, alors nous la rechercherons sur la gauche subtree.
2. La valeur donnée est-elle supérieure à la valeur actuelle node ? Si oui, alors nous la chercherons à droite subtree.
3. Si les règles #1 et #2 sont toutes deux fausses, nous pouvons comparer la valeur actuelle node et la valeur donnée si elles sont égales. Si la comparaison renvoie true, alors nous pouvons dire :  » Oui ! Notre tree a la valeur donnée « , sinon, nous disons :  » Nooon, ce n’est pas le cas ! « 

Maintenant, codons-le.

Découpons le code :

• Les lignes 8 et 9 relèvent de la règle n°1.
• Les lignes 10 et 11 relèvent de la règle n°2.
• La ligne 13 relève de la règle n°3.

Comment le tester ?

Créons notre Binary Search Tree en initialisant la rootnode avec la valeur 15.

bst = BinarySearchTree(15)

Et maintenant nous allons insérer plusieurs nouvelles nodes.

Pour chaque node insérée, nous allons tester si notre méthode find_node fonctionne vraiment.

Oui, elle fonctionne pour ces valeurs données ! Testons pour une valeur qui n’existe pas dans notre Binary Search Tree.

print(bst.find_node(0)) # False

Oh oui.

Notre recherche est terminée.

Suppression : enlever et organiser

La suppression est un algorithme plus complexe car nous devons gérer différents cas. Pour une valeur donnée, nous devons supprimer le node avec cette valeur. Imaginons les scénarios suivants pour cette node : elle n’a pas de children, a une seule child, ou a deux children.

• Scénario #1 : Une node sans childrenleafnode).

# |50| |50|# / \ / \# |30| |70| (DELETE 20) ---> |30| |70|# / \ \# |20| |40| |40|

Si la node que nous voulons supprimer n’a pas d’enfants, nous la supprimons simplement. L’algorithme n’a pas besoin de réorganiser le tree.

• Scénario #2 : Une node avec un seul enfant (left ou right enfant).

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |20| |70|# / # |20|

Dans ce cas, notre algorithme doit faire en sorte que le parent de la node pointe vers le nœud child. Si la node est la left child, nous faisons en sorte que le parent de la left child pointe vers la child. Si la node est la right child de son parent, on fait pointer le parent de la right child vers la child.

• Scénario #3 : Une node avec deux enfants.

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |40| |70|# / \ /# |20| |40| |20|

Lorsque la node a 2 enfants, nous devons trouver la node avec la valeur minimale, en partant de la node‘sright child. Nous mettrons cette node à valeur minimale à la place de la node que nous voulons supprimer.

Il est temps de coder.

1. Premièrement : Notez les paramètres value et parent. Nous voulons trouver la nodequi possède cette value , et le parent de la node est important pour la suppression de la node.
2. Deuxièmement : notez la valeur de retour. Notre algorithme renvoie une valeur booléenne. Il renvoie True s’il trouve le node et le supprime. Sinon, il renvoie False.
3. De la ligne 2 à la ligne 9 : Nous commençons à chercher la node qui possède la valueque nous recherchons. Si la value est plus petite que la current nodevalue, on va vers la left subtree, de manière récursive (si, et seulement si, la current node possède une left child). Si la value est supérieure, on passe à la right subtree, de manière récursive.
4. Ligne 10 : On commence à réfléchir à l’algorithme remove.
5. De la ligne 11 à la ligne 13 : Nous couvrons le node sans children , et c’est le left child de son parent. Nous supprimons la node en mettant la parent de la left child en None.
6. Lignes 14 et 15 : Nous recouvrons la node sans children , et c’est la right child de sa parent. Nous supprimons la node en mettant la parent de la right childNone.
7. Méthode Clear node : Je vais montrer le code clear_node ci-dessous. Il définit les nœuds left child , right child, et son value en None.
8. De la ligne 16 à la ligne 18 : Nous couvrons la node avec une seule childleft child), et c’est la left child de sa parent. Nous définissons la parent de la left child sur la node de la left child (le seul enfant qu’elle possède).
9. De la ligne 19 à la ligne 21 : Nous couvrons la node avec une seule childleft child), et c’est la right child de sa parent. Nous fixons la parent de la right child à la node de la left child (le seul enfant qu’elle a).
10. De la ligne 22 à la ligne 24 : Nous couvrons la node avec une seule childright child), et c’est la left child de sa parent. Nous réglons la parent de la left child sur la node de la right child (le seul enfant qu’elle a).
11. De la ligne 25 à la ligne 27 : Nous couvrons la node avec une seule childright child) , et c’est la right child de sa parent. Nous mettons la parent de la right child sur la node de la right child (le seul enfant qu’elle a).
12. De la ligne 28 à la ligne 30 : Nous couvrons la node avec les deux left et rightenfants. On récupère la node avec la plus petite value (le code est indiqué ci-dessous) et on la place sur la value de la current node . Terminez-la en supprimant le plus petit node.
13. Ligne 32 : Si nous trouvons le node que nous cherchons, il doit retourner True. De la ligne 11 à la ligne 31, nous gérons ce cas. Il suffit donc de retourner True et c’est tout.

• Pour utiliser la méthode clear_node : définissez la valeur None sur les trois attributs – (valueleft_child, et right_child)

def clear_node(self): self.value = None self.left_child = None self.right_child = None

• Pour utiliser la méthode find_minimum_value : descendez tout en bas à gauche. Si nous ne trouvons plus de nœuds, nous avons trouvé le plus petit.

def find_minimum_value(self): if self.left_child: return self.left_child.find_minimum_value() else: return self.value

Maintenant, testons-le.

Nous allons utiliser cette tree pour tester notre remove_node algorithme.

# |15|# / \# |10| |20|# / \ / \# |8| |12| |17| |25|# \# |19|

Supprimons la node avec la value 8. C’est une node sans enfant.

print(bst.remove_node(8, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |17| |25|# \# |19|

Maintenant, supprimons la node avec la value 17. C’est une node avec un seul enfant.

print(bst.remove_node(17, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |19| |25|

Enfin, nous allons supprimer une node avec deux enfants. C’est le root de notre tree.

print(bst.remove_node(15, None)) # Truebst.pre_order_traversal()# |19|# / \# |10| |20|# \ \# |12| |25|

Les tests sont maintenant terminés. 🙂

C’est tout pour le moment !

Nous avons beaucoup appris ici.

Félicitations pour avoir terminé ce contenu dense. C’est vraiment difficile de comprendre un concept que l’on ne connaît pas. Mais vous l’avez fait 🙂

C’est un pas de plus dans mon voyage pour apprendre et maîtriser les algorithmes et les structures de données. Vous pouvez voir la documentation de mon parcours complet ici sur ma publication Renaissance Developer.

Amusez-vous bien, continuez à apprendre et à coder.

Mon Twitter & Github. ☺

Ressources supplémentaires

• Introduction à la structure de données des arbres par mycodeschool
• Tree par Wikipedia
• How To Not Be Stumped By Trees par le talentueux Vaidehi Joshi
• Intro to Trees, Lecture par le professeur Jonathan Cohen
• Intro to Trees, Conférence du professeur David Schmidt
• Intro aux arbres, Conférence du professeur Victor Adamchik
• Les arbres avec Gayle Laakmann McDowell
• Mise en œuvre et tests d’arbres binaires par TK
• Coursera Course : Structures de données par l’Université de Californie, San Diego
• Coursera Course : Structures de données et performances par l’Université de Californie, San Diego
• Concepts et mise en œuvre de l’arbre de recherche binaire par Paul Programming
• Mise en œuvre et tests de l’arbre de recherche binaire par TK
• Tree Traversal par Wikipedia

.

• Arbre de recherche binaire : algorithme de suppression des nœuds par GeeksforGeeks
• Arbre de recherche binaire : algorithme de suppression des nœuds par Algolist
• Apprentissage de Python de zéro à héros