Qu’est-ce qu’un arbre binaire ?
Vous souvenez-vous des listes chaînées ? Maintenant, imaginez que chaque nœud contienne deux adresses et non pas une. Si vous deviez le représenter par un schéma, cela ressemblerait étrangement à un arbre. C’est ce que nous appelons un arbre binaire.
Comme dans un arbre généalogique, toutes les cellules sont des cellules filles, sauf une qui est la cellule mère. Si l’arbre n’est pas vide, une seule cellule n’a pas de cellule mère, et celle-ci est appelée racine de l’arbre. Toute cellule descend de la racine.
Les arbres binaires sont très largement utilisés en informatique car ils sont considérés comme les structures de données les plus simples et les plus efficaces à utiliser dans la plupart des systèmes logiciels. Ça paraît sûrement encore abstrait pour vous, mais ils sont utilisés par exemple dans :
les jeux vidéo en 3D ;
les routeurs Internet ;
les bases de données ;
les calculatrices.
Comme vous pouvez le voir, les arbres binaires sont omniprésents dans nos logiciels, il est donc important de comprendre leur fonctionnement.
Pourquoi l’appeler arbre binaire ?
Car chaque cellule mère a 0, 1 ou 2 cellules enfants qui elles-mêmes sont liées à d’autres cellules.
Dans la terminologie des arbres, les cellules sont appelées des nœuds ou des sommets. Un nœud n’ayant pas d’enfant s’appelle une feuille.
En d’autres termes, un arbre binaire est une structure analogue à une liste chaînée, sauf que chaque cellule possède jusqu’à deux suivantes. Par convention, on convient d’appeler fils gauche et fils droit les deux fils d’un nœud. Le fils gauche et le fils droit d’un nœud peuvent ne pas exister.
Parcours d’arbres binaires
Pour trouver une information dans un arbre binaire, il vous faut parcourir tous ses nœuds. Comment faire ? Le moyen le plus simple est de réaliser une fonction récursive.
Mais qu’est-ce qu’une fonction récursive ?
La récursivité est un processus qui prend tout son sens lorsque la résolution d'un problème se ramène à celle d'un problème plus petit. On parlera de récursivité lorsqu’une fonction s'appelle elle-même, en boucle, jusqu'à atteindre une condition d'arrêt.
Ne vous inquiétez pas, nous allons avoir un chapitre complet consacré à la récursivité dans la prochaine partie du cours. Vous avez déjà une idée de cette notion.
Il existe de nombreuses manières de parcourir un arbre selon l’ordre dans lequel vous souhaitez examiner les nœuds.
Qu’est-ce qu’un graphe ?
Un graphe est un ensemble de cellules reliées les unes aux autres non plus par un lien d’ascendance, comme dans le cas d’un arbre, mais par une relation. Visuellement, il s’agit d’un ensemble de nœuds ou de sommets reliés par des arêtes.
Un graphe peut représenter un réseau routier, un réseau de transport aérien, un réseau informatique et bien plus encore.
Les graphes sont souvent utilisés par des algorithmes dont le but est de trouver le plus court chemin entre un point A et un point B. Le service que nous connaissons tous qui utilise ce principe est Google Maps. Facebook utilise également les graphes pour trouver les amis de vos amis, et vous les présenter !
Sur Facebook, chaque personne du réseau est représentée par un cercle (appelé sommet). Vos amis sont reliés à vous par des lignes (appelées arcs). Les amis qui pourraient vous intéresser sont ceux qui sont reliés à vos amis par un arc, tout simplement !
En résumé
Un arbre binaire est une structure de données spéciale utilisée à des fins de stockage de données.
Un arbre binaire présente les avantages à la fois d'un tableau ordonné et d'une liste chaînée.
Un arbre binaire est composé de nœuds et d'enfants, chaque nœud pouvant avoir jusqu’à deux enfants.
Un graphe est une représentation d'un ensemble d'objets où certaines paires d'objets sont reliées par des liens.
Les objets interconnectés sont représentés par des points appelés sommets, et les liens qui relient les sommets sont appelés arêtes.
Vous avez appris plein de choses dans cette deuxième partie. Il est maintenant temps de tester vos connaissances à l’aide d’un petit quiz. Bonne chance !
