Arbre Binaire [PDF]

Zitiervorschau

Arbre binaire En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé il y a donc un nœud racine. Au niveau directement inférieur, il y a au plus deux nœuds fils. En continuant à descendre aux niveaux inférieurs, on peut en avoir quatre, puis huit, seize, etc. c'est-à-dire la suite des puissances de deux. Un nœud n'ayant aucun fils est appelé feuille. Le nombre de niveaux total, autrement dit la distance entre la feuille la plus éloignée et la racine, est appelé hauteur de l'arbre. Le niveau d'un nœud est appelé profondeur. Les arbres binaires peuvent notamment être utilisés en tant qu'arbre binaire de recherche ou en tant que tas binaire.

Un exemple simple d'arbre binaire

Sommaire    

 



1 Définition dans la théorie des graphes 2 Types d'arbre binaire 3 Méthode pour stocker des arbres binaires 4 Méthode d'itération des arbres binaires o 4.1 Parcours préfixe, infixe et postfixe  4.1.1 Parcours préfixe  4.1.2 Parcours postfixe ou suffixe  4.1.3 Parcours infixe o 4.2 Parcours en profondeur o 4.3 Parcours en largeur 5 Transformation d'un arbre quelconque en un arbre binaire 6 Voir aussi o 6.1 Algorithmes utilisant des arbres binaires o 6.2 Arbres binaires particuliers o 6.3 Autres types d'arbres 7 Notes et références

Définition dans la théorie des graphes La théorie des graphes utilise la définition suivante : un arbre binaire est un graphe connexe acyclique, tel que le degré de chaque nœud (ou vertex) soit au plus 3.

La racine d'un arbre binaire est le nœud d'un graphe de degré maximum 2. Avec une racine ainsi choisie, chaque nœud aura un unique parent défini et deux fils ; toutefois, ces informations sont insuffisantes pour distinguer un fils droit d'un fils gauche. Si nous négligeons cette condition de connexité, et qu'il y a de multiples éléments connectés, on appellera cette structure une forêt.

Types d'arbre binaire 

Un arbre binaire (ou binaire-unaire) est un arbre avec racine dans lequel chaque nœud a au plus deux fils.



Un arbre binaire entier est un arbre dont tous les nœuds possèdent zéro ou deux fils.



Un arbre binaire parfait est un arbre binaire entier dans lequel toutes les feuilles (nœuds n'ayant aucun fils) sont à la même distance de la racine.

L'arbre binaire parfait est parfois nommé arbre binaire complet. Cependant certains définissent un arbre binaire complet comme étant un arbre binaire entier dans lequel les feuilles ont pour profondeur n ou n-1 pour un n donné.

Méthode pour stocker des arbres binaires Les arbres binaires peuvent être construits à partir de primitives d'un langage de programmation de différentes manières. Dans un langage avec structures et pointeurs (ou références), les arbres binaires peuvent être conçus en ayant une structure à trois nœuds qui contiennent quelques données et pointeurs vers son fils droit et son fils gauche. L'ordre que cela impose aux nœuds enfants est parfois utile, en particulier pour les parcours infixes. Parfois, il contient également un pointeur vers son unique parent. Si un nœud possède moins de deux fils, l'un des deux pointeurs peut être affecté de la valeur spéciale nulle ; il peut également pointer vers un nœud sentinelle. Les arbres binaires peuvent aussi être rangés dans des tableaux, et si l'arbre est un arbre binaire complet, cette méthode ne gaspille pas de place, et la donnée structurée résultante est appelée un tas. Dans cet arrangement compact, un nœud a un indice i, et (le tableau étant basé sur des zéros) ses fils se trouvent aux indices 2i+1 et 2i+2, tandis que son père se trouve (s'il existe) à l'indice floor((i-1)/2). Cette méthode permet de bénéficier d'un encombrement moindre, et d'un meilleur référençage, en particulier durant un parcours préfixe. Toutefois, elle requiert une mémoire contigüe, elle est coûteuse s'il s'agit d'étendre l'arbre et l'espace perdu (dans le cas d'un arbre binaire non complet) est proportionnel à 2h - n pour un arbre de profondeur h avec n nœuds.

Dans les langages à union étiquetée comme ML, un nœud est souvent une union taguée de deux types de nœud, l'un étant un triplet contenant des données et ses fils droits et gauches, et l'autre un nœud vide, qui ne contient ni donnée ni fonction, ressemblant à la valeur nulle des langages avec pointeurs.

Méthode d'itération des arbres binaires Souvent, il est souhaitable de visiter chacun des nœuds dans un arbre et d'y examiner la valeur. Il existe plusieurs ordres dans lesquels les nœuds peuvent être visités, et chacun a des propriétés utiles qui sont exploitées par les algorithmes basés sur les arbres binaires.

Parcours préfixe, infixe et postfixe (parfois appelés préordre, inordre et postordre) Soit une structure Arbre dont la racine est A et une référence gauche et droite à ses deux fils. Nous pouvons écrire les fonctions suivantes : Parcours préfixe visiterPréfixe(Arbre A) : visiter(A) Si nonVide(gauche(A)) visiterPréfixe(gauche(A)) Si nonVide(droite(A)) visiterPréfixe(droite(A))

Ceci affiche les valeurs de l'arbre en ordre préfixe. Dans cet ordre, chaque nœud est visité ainsi que chacun de ses fils. Parcours postfixe ou suffixe visiterPostfixe(Arbre A) : Si nonVide(gauche(A)) visiterPostfixe(gauche(A)) Si nonVide(droite(A)) visiterPostfixe(droite(A)) visiter(A)

Dans un parcours postfixe ou suffixe, on affiche chaque nœud après avoir affiché chacun de ses fils. Parcours infixe visiterInfixe(Arbre A) : Si nonVide(gauche(A)) visiterInfixe(gauche(A)) visiter(A) Si nonVide(droite(A)) visiterInfixe(droite(A))

Un parcours infixe, comme ci-dessus, visite chaque nœud entre les nœuds de son sous-arbre de gauche et les nœuds de son sous-arbre de droite. C'est une manière assez commune de parcourir un arbre binaire de recherche, car il donne les valeurs dans l'ordre croissant. Pour comprendre pourquoi cela est le cas, si n est un nœud dans un arbre binaire de recherche, alors tous les éléments dans le sous-arbre de gauche du nœud n seront inférieurs à n et ceux dans le sous-arbre de droite seront supérieurs ou égaux à n. Ainsi, si nous visitons le sous-arbre de gauche dans l'ordre, de manière récursive, puis que nous visitons n, et que nous visitons le sous-arbre de droite, nous aurons visité l'ensemble du sous-arbre enraciné en n dans l'ordre.

Dans cet arbre binaire,   

Rendu du parcours infixe : 4, 2, 7, 5, 8, 1, 3, 9, 6 Rendu du parcours postfixe : 4, 7, 8, 5, 2, 9, 6, 3, 1 Rendu du parcours préfixe : 1, 2, 4, 5, 7, 8, 3, 6, 9

Nous pouvons effectuer ces parcours avec un langage fonctionnel comme Haskell avec le code suivant : data Tree a = Leaf | Node(a, Tree a, Tree a) preorder Leaf = [] preorder (Node (x, left,right)) = [x] ++ (preorder left) ++ (preorder right) postorder Leaf = [] postorder (Node (x, left,right)) = (postorder left) ++ (postorder right) ++ [x] inorder Leaf = [] inorder (Node (x, left,right)) = (inorder left) ++ [x] ++ (inorder right)

Tous ces algorithmes récursifs utilisent une pile mémoire proportionnelle à la profondeur des arbres. Si nous rajoutons dans chaque nœud une référence à son parent, alors nous pouvons implémenter tous ces parcours en utilisant des espaces mémoires uniquement constants et un algorithme itératif. La référence au parent occupe cependant beaucoup d'espace ; elle n'est réellement utile que si elle est par ailleurs nécessitée ou si la pile mémoire est particulièrement limitée. Voici par exemple, l'algorithme itératif pour le parcours infixe : VisiterInfixeIteratif(racine) precedent := null actuel := racine suivant := null Tant que (actuel != null) Faire Si (precedent == pere(actuel)) Alors precedent := actuel suivant := gauche(actuel) FinSi Si (suivant == null OU precedent == gauche(actuel)) Alors Visiter(actuel) precedent := actuel suivant := droite(actuel) FinSi Si (suivant == null OU precedent == droite(actuel)) Alors precedent := actuel suivant := pere(actuel) FinSi actuel := suivant FinTantQue

Parcours en profondeur

Avec ce parcours, nous tentons toujours de visiter le nœud le plus éloigné de la racine que nous pouvons, à la condition qu'il soit le fils d'un nœud que nous avons déjà visité. À l'opposé des parcours en profondeur sur les graphes, il n'est pas nécessaire de connaître les nœuds déjà visités, car un arbre ne contient pas de cycles. Les parcours préfixe, infixe et postfixe sont des cas particuliers de ce type de parcours. Pour effectuer ce parcours, il est nécessaire de conserver une liste des éléments en attente de traitement. Dans le cas du parcours en profondeur, il faut que cette liste ait une structure de pile (de type LIFO, Last In, First Out autrement dit: « dernier entré, premier sorti »). Dans cette implémentation, on choisira également d'ajouter les fils d'un nœud de droite à gauche. ParcoursProfondeur(Arbre A) { S = Pilevide ajouter(Racine(A), S) Tant que (S != Pilevide) { nœud = premier(S) retirer(S) Visiter(nœud) //On choisit de faire une opération Si (droite(nœud) != null) Alors ajouter(droite(nœud), S) Si (gauche(nœud) != null) Alors ajouter(gauche(nœud), S) } }

Parcours en largeur Contrairement au précédent, ce parcours essaie toujours de visiter le nœud le plus proche de la racine qui n'a pas déjà été visité. En suivant ce parcours, on va d'abord visiter la racine, puis les nœuds à la profondeur 1, puis 2, etc. D'où le nom parcours en largeur. L'implémentation est quasiment identique à celle du parcours en profondeur à ce détail près qu'on doit cette fois utiliser une structure de file d'attente (de type FIFO, First in, first out autrement dit « premier entré, premier sorti »), ce qui induit que l'ordre de sortie n'est pas le même (i.e. on permute gauche et droite dans notre traitement). ParcoursLargeur(Arbre A) { f = FileVide enfiler(Racine(A), f) Tant que (f != FileVide) { nœud = defiler(f) Visiter(nœud) Si (gauche(nœud) != null) enfiler(gauche(nœud), Si (droite(nœud) != null) enfiler(droite(nœud), } }

//On choisit de faire une opération Alors f) Alors f)

Transformation d'un arbre quelconque en un arbre binaire Il existe une injection entre les arbres triés généraux et les arbres binaires, qui est spécialement utilisée par Lisp pour représenter les arbres triés généraux en tant qu'arbres binaires. Chaque nœud N dans l'arbre trié correspond au nœud N' dans l'arbre binaire ; le fils gauche de N' est le nœud correspondant au premier fils de N, et le fils droit de N' est le nœud correspondant au prochain frère de N - qui est le nœud suivant dans l'ordre parmi les enfants du père de N. Une manière de se représenter ceci est de penser que chaque fils d'un nœud est dans une liste liée, mutuellement liés par leurs champs droits, et que le nœud possède seulement un pointeur vers le début de la liste, jusqu'à son champ gauche.

Par exemple, dans l'arbre de gauche, A a 6 fils : {B, C, D, E, F, G}. Il peut être converti en arbre binaire (comme celui de droite).

Cet arbre binaire peut être considéré comme l'arbre original incliné en longueur, avec les côtés noirs de gauche représentant les premiers fils et les côtés bleus de droite représentant ses prochains frères. La part de l'arbre de gauche pourrait être codée en Lisp comme ceci : (((M N) H I) C D ((O) (P)) F (L)) qui pourrait être implémentée en mémoire comme l'arbre binaire de droite, sans les lettres de ce nœud qui ont un fils gauche.

Voir aussi Sur les autres projets Wikimedia : 

Arbre binaire, sur Wikiversity



Nombre de Strahler

Algorithmes utilisant des arbres binaires  

Codage de Huffman Algorithme des nœuds chapeaux

Arbres binaires particuliers    

Arbre binaire de recherche Arbre AVL Arbre bicolore (arbre rouge-noir) Arbre cousu

Arbre binaire de recherche

Exemple représentant un arbre binaire de recherche

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous-arbre gauche ait une clé inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci — selon la mise en œuvre de l'ABR, on pourra interdire ou non des clés de valeur égale. Les nœuds que l'on ajoute deviennent des feuilles de l'arbre.

Opérations Recherche La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même si la clé de la racine est strictement supérieure à la clé recherchée la recherche continue sur le sous-arbre droit. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun nœud. On peut la comparer avec la recherche par dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens. Cette opération requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chaînée.

Insertion L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à gauche ; sinon il sera à droite. La complexité est la même que pour la recherche : O(log n) dans le cas moyen et O(n) dans le cas critique.

Suppression Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :  

Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils. Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.



Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N (le nœud de valeur 7 dans le graphique ci-dessous). On échange le nœud N avec son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit - ci-dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche - ci-dessous, le nœud de valeur 6). Cela permet de garder une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

Pour une implémentation efficace, il est déconseillé d'utiliser uniquement le successeur ou le prédécesseur car cela contribue à déséquilibrer l'arbre. Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut n dans le pire des cas, d'où une complexité maximale en O(n).

Parcours ordonné On peut facilement récupérer les éléments d'un arbre binaire de recherche dans l'ordre de leurs clés en parcourant récursivement le sous-arbre gauche, puis en ajoutant la racine, puis en parcourant récursivement le sous-arbre droit. On peut évidemment le faire dans l'ordre inverse en commençant par le sous-arbre droit. Le parcours de l'arbre se fait en O(n), puisqu'il doit passer par chaque nœud.

Tri On peut dès lors implémenter un algorithme de tri simple mais peu efficace, en insérant toutes les clés que l'on veut trier dans un nouvel arbre binaire de recherche, puis en parcourant de manière ordonnée cet arbre comme ci-dessus. Le pire temps d'exécution est en O(n²), obtenu lorsque les clés sont déjà ordonnées : on obtient alors une liste chaînée. Par exemple, si on donne dans cet ordre les clés 1, 2, 3, 4, 5, on obtient l'arbre (Vide, 1, (Vide, 2, (Vide, 3, (Vide, 4, (Vide, 5, Vide))))). Il y a de nombreuses façons d'éviter ce problème, la plus commune étant l'arbre équilibré. On peut alors arriver à un pire cas en O(n ln n).

Types d'arbres binaires de recherche Il existe de nombreux types d'arbres binaires de recherche. Les arbres AVL et les arbres rouge-noir sont deux types d'arbres équilibrés. Un arbre splay est un arbre binaire de recherche qui rapproche automatiquement de la racine les éléments utilisés fréquemment. Dans un treap, chaque nœud possède aussi une priorité supérieure à chacun de ses fils.