====== Arbres ====== Il s'agit d'un structure de données **hiérarchique**. //Par opposition aux structures linéaires que sont les tableaux, listes, piles et files// {{ nsi:terminales:arbres:arbre_1.png?nolink&400 |}} ===== Définitions ===== ==== Nœud ==== Élément constitutif de l'arbre. Les nœuds sont liés les uns aux autres par un lien de parenté. En général, un nœud à des enfants et **un** parent. * On peut parler de **descendants** pour l'ensemble des enfants d'un nœud, des enfants des enfants, etc. * On peut également parler d'**ancêtres** d'un nœud. ==== Arbre ==== Un arbre peut-être **vide**. Sinon il contient des nœuds. L'un de ces nœuds est la **racine** de l'arbre, il n'a pas de parent. Tous les autres nœuds ont exactement **un** parent. ==== Racine ==== C'est un nœud sans parent. Il doit y avoir exactement une racine dans un arbre non vide. //Dans l'exemple, la racine est le nœud A// ==== Feuille ==== C'est un nœud sans enfant. La feuille est au bout d'une branche d'arbre. //Dans l'exemple, les nœuds D, E, C sont des feuilles// ==== Profondeur d'un nœud ==== Pour un nœud donné, c'est le nombre de liens le séparant de la racine. Dans l'exemple, * A a une profondeur de 0 ; * B une profondeur de 1 ; * D une profondeur de 2 On trouve des définitions contradictoires sur internet. Certains comptent une profondeur de 1 pour la racine et d'autres 0... Rien de grave, au besoin on précisera toujours quelle définition on choisit. ==== Hauteur d'un arbre ==== profondeur maximale dans l'arbre. //L'arbre ci-dessus a une hauteur de 2.// Là encore, on pourra trouver des définitions qui donnent à cet arbre une hauteur de 3. ==== Sous arbre ==== arbre formé en prenant un certain nœud comme racine et en ne conservant que ses descendants Par exemple, considérons l'arbre formé par un système de fichier : {{ nsi:terminales:arbres:arbre_3.png?direct&600 |}} On peut considérer le sous arbre issu de ''%%Users\%%'' : {{ nsi:terminales:arbres:arbre_5.png?nolink&400 |}} ===== Exemples d'arbres ===== Les arbres sont courants en informatique et ailleurs. En mathématique on connaît les arbres de probabilités et on pense bien sûr aux arbres généalogiques. un arbre généalogique est un exemple qui peut être trompeur. Pour que l'arbre généalogique soit un arbre au sens qui m'intéresse, il faut que les racine soit moi et que mes nœuds enfants soient mes parents... ==== Adresse dans une rue ==== {{ nsi:terminales:arbres:arbre_2.png?direct&600 |}} ==== arborescence du système de fichier ==== {{ nsi:terminales:arbres:arbre_3.png?direct&600 |}} ==== dom d'une page html ==== [[https://developer.mozilla.org/fr/docs/Web/API/Document_Object_Model/Introduction|dom]] du [[nsi:langages:html:start|html]] avec [[nsi:langages:js:start|javascript]] Page exemple

Premier paragraphe

Deuxième paragraphe avec mot en gras

Deuxième bloc.
Cette page **html** a une structure hiérarchique. Remarquez l'indentation -- non obligatoire -- qui permet de bien voir cette hiérarchie. Le script **javascript** qui s'exécute après chargement de la page utilise la variable ''document'' pour ajouter un enfant -- ''appendChild'' -- à l'élément ''document.body''. ==== successions de coups possibles au échecs ==== {{ nsi:terminales:arbres:arbre_4.png?nolink&600 |}} ===== Arbres binaires ===== Dans un arbre binaire, chaque nœud ne peut avoir que **0, 1 ou 2 enfants**. Exemple : {{ nsi:terminales:arbres:arbre_1.png?nolink&400 |}} On pourra alors parler d'enfant gauche et enfant droit, de sous-arbre gauche sous-arbre droit : * L'enfant gauche de A est B, l'enfant droit de A est C * Les sous-arbres gauche et droit de A sont : {{ nsi:terminales:arbres:arbre_6.png?nolink&400 |}} ===== Arbre binaire de recherche (ABR) ===== On définit un critère d'ordre entre les nœuds. On peut dire qu'un nœud a une valeur supérieur à celle d'un autre selon ce critère. Dans un ABR, pour un nœud donné, tous les nœuds du sous-arbre gauche ont une valeur inférieure et tous les nœuds du sous-arbre droit ont une valeur supérieure. {{ nsi:terminales:arbres:arbre_7.png?direct |}} Par exemple, ici, les nœuds contiennent des doublets ''%%(nom, numéro)%%''. Il faudra donc préciser comment on choisit de trier. ==== Recherche d'un nœud ==== L'arbre est trié selon l'ordre alphabétique du nom. L'organisation de l'ABR facilite la recherche d'un nom. **Exemple :** On cherche le numéro de ''%%"Malefoy Drago"%%''. La simplicité de cet exemple peut tromper : Nous voyons sur la figure la totalité de l'arbre et nous voyons instantanément où se trouve //Drago Malefoy//. Il peut nous sembler inutile de chercher une organisation particulière. Mais gardez à l'esprit qu'en situation réelle, nous aurions un annuaire contenant des centaines de milliers de noms ! Aucun nom n'apparaîtra instantanément, il faudra chercher et il vaudrait mieux que l'on s'y prenne de façon efficace. * On commence par la racine, ''%%"Harry Potter"%%''. * Puisque ''%%"Malefoy Drago"%%'' est situé avant ''%%"Harry Potter"%%'' dans l'ordre alphabétique, on sait que l'on doit chercher dans le sous-arbre gauche. * On arrive à ''%%"Granger Hermione"%%''. Elle est inférieure à ''%%"Malefoy Drago"%%'' dans l'ordre alphabétique, on continue vers le sous arbre droit de ''%%"Granger Hermione"%%''. * On arrive à ''%%"Lovegood Luna"%%''. Elle est inférieure à ''%%"Malefoy Drago"%%'' dans l'ordre alphabétique, on continue vers le sous arbre droit de ''%%"Lovegood Luna"%%''. * On a trouvé le nœud de ''%%"Malefoy Drago"%%''. ==== Insertion d'un nœud ==== On cherche à insérer un nouvel item. * On crée un nœud contenant l'item, * on cherche l'endroit approprié pour inséré ce nouveau nœud, * on insère le nœud à l'emplacement trouvé. Par exemple, supposons que l'on veuille insérer ''%%"Patil Parvati", "07.85.41.19.77"%%'', * On crée le nœud contenant le doublet, * on cherche un point d'insertion : ''%%"Patil Parvati"%%'' est * à gauche de ''%%"Potter Harry"%%'', * à droite de ''%%"Granger Hermione"%%'', * à droite de ''%%"Lovegood Luna"%%'', * à droite de ''%%"Malefoy Drago"%%'', * mais ''%%"Malefoy Drago"%%'' n'a pas d'enfant droit, donc on peut insérer ''%%"Patil Parvati"%%'' comme enfant droit de ''%%"Malefoy Drago"%%''. {{ nsi:terminales:arbres:arbre_9.png?direct |}} Suivant l'ordre d'insertion, l'arbre n'aura pas la même structure. Ce serait par exemple une mauvaise idée que d'insérer les noms par ordre alphabétique. En effet, un ABR est intéressant si la plupart des nœuds ont deux enfants. On pourrait imaginer un algorithme visant à réorganiser un arbre mal structuré mais on ne le fera pas ici. ===== Définition plus générale ? ===== Nous avons donné ici une première définition des arbres. Certains (informatique théorique, mathématique...) utilisent parfois une version plus générale : Ils disent qu'un arbre est un [[..:graphes:cours|Graphe]] connexe et sans cycle. Comme en mathématiques, les définitions peuvent être adaptées selon le besoin. Dans le cadre de la NSI, nous utilisons la définition plus simple qui a été donnée dans ce cours.