En informatique, un arbre binaire correspond à un moyen de structurer des données pour en faciliter l'accès. Chaque nœud présente ainsi une valeur et peut présenter un sous-arbre gauche et un sous-arbre droit.
Un dictionnaire se compose d'entrées elles-mêmes constituées de clés qui sont liées à des données. Par exemple, un dictionnaire de langues comporte des mots (entrées) associés à des définitions (données).
La méthode dichotomique consiste littéralement à « couper en deux ». On prend une moitié du jeu de valeurs et on regarde si la valeur qui nous intéresse est dedans. Une fois cela fait, on prend de nouveau une moitié de cette moitié, et ainsi de suite jusqu'à trouver notre valeur.
En effet, le parcours infixe d'un arbre binaire de recherche donne toujours des valeurs croissantes. Ainsi, la valeur d'un nœud est toujours plus grande que celle présente dans son fils gauche et plus petite que celle présente dans son fils droit.
Un parcours infixe va effectivement passer par chaque nœud, en allant du sous-arbre gauche vers le sous-arbre droit.
Un parcours infixe a pour but de donner les valeurs de l'arbre en le balayant de gauche à droite. Dans le cas d'un arbre binaire de recherche, ces valeurs seront croissantes.
Plus un arbre est haut plus on a besoin d'opérations pour le traverser. Ainsi, un arbre court est bien plus efficace, car plus rapide à traverser.
En effet, un arbre en peigne se dirige dans une seule et unique direction, par exemple toujours vers le sous-arbre gauche.
Dans un arbre en peigne, on ne peut pas diviser la recherche en deux, ainsi, si on prend l'exemple d'une recherche parmi 100 valeurs, il faudra 100 étapes. A l'inverse, l'arbre complet se divise en deux à chaque nœud, et on aura alors besoin de beaucoup moins d'étapes.
9
Félicitations pour le score parfait !Encore un petit effort !
Retente ta chance, tu peux faire mieux.
Pour suivre tes progrès, crée ton compte Lumni, c’est gratuit !
Je crée mon compteAimé à 100% par nos utilisateurs
Joue à ce quiz et gagne facilement jusqu'à 80 Lumniz en te connectant !
Il n’y a pas de Lumniz à gagner car tu as déjà vu ce contenu. Ne t’inquiète pas, il y a plein d’autres vidéos, jeux, quiz ou articles intéressants à explorer et toujours plus de Lumniz à remporter.
Les arbres binaires
En informatique, on utilise souvent des arbres binaires de recherche. Ces outils permettent de structurer les données afin de retrouver plus facilement et rapidement une information. Avec ce quiz, testez vos connaissances sur les principes d'un arbre de recherche et ses applications.