Leçon 12 : Arbres et arbres binaires de recherche
Pense à un arbre généalogique, ou à des dossiers dans des dossiers : il y a un « sommet » d'où se ramifient des éléments « en dessous ». C'est un « arbre » — chaque point est un « nœud » (node). Dans un « arbre binaire de recherche » (BST), chaque nœud a des valeurs plus petites à sa gauche et plus
Un BST, c'est comme chercher un mot dans un dictionnaire : on ouvre au milieu, et si le mot vient « avant », on saute d'un coup toute la moitié droite. Chaque comparaison économise la moitié du travail — mais seulement si les pages sont réparties également.
- classe (class)
- Un modèle pour une petite boîte avec des champs. class TreeNode définit une boîte à trois champs : val (la valeur) et left/right (les enfants). TreeNode(5) crée une telle boîte, et self signifie simplement « cette boîte » (même idée que dans la leçon sur les listes chaînées).
- arbre binaire de recherche
- Un arbre binaire où, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont plus petites et toutes celles du sous-arbre droit sont plus grandes.
- parcours d'arbre
- Visiter chaque nœud d'un arbre selon un ordre défini. Le parcours inorder (gauche, nœud, droite) sur un BST donne les valeurs triées.
- arbre équilibré
- Un arbre dont la hauteur est d'environ log n, donc la recherche prend O(log n). Un arbre déséquilibré (skewed) perd cet avantage et atteint O(n).
