Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_fiches_revisions:structure_des_donnees:arbres [2021/01/11 15:24]
clemercier created
+++ les_fiches_revisions:structure_des_donnees:arbres [2023/01/18 16:13] (Version actuelle)
lag [Les arbres]
@@ Ligne 3: / Ligne 3: @@
 Les arbres sont des types abstraits permettant de structurer les données.
-Un arbre binaire un cas particulier d'arbre qui peut se présenter sous la forme :
+Les arbres binaires sont une forme plus précise d'arbre où chacun des nœuds ne peut avoir que 2 fils maximums:
 {{ :les_fiches_revisions:arbre.png?nolink&400 |{{:les_fiches_revisions:arbre.png?nolink&400 |{{ :les_fiches_revisions:arbre.png?nolink&400 |{{ :les_fiches_revisions:arbre.png?400 |{{:les_fiches_revisions:arbre.png?400|}}
-//__**Vocabulaire :**__//
+//__**Quelques thermes sont à connaitre pour parler d'arbre :**__//
-  * //__nœud :__// chaque élément de l'arbre (ex : A, B, …)
+  * //__nœud :__// élément qui forme l'arbre (ex : A, B, …)
-  * //__nœud racine__// : premier nœud de l'arbre (ici : A)
+  * //__nœud racine :__// initiale départ de l'arbre (ici : A)
-  * //__nœud fils :__// les nœuds D et E sont les fils du nœud B
+  * //__nœud fils :__// 1 ou 2 nœud(s) sous un autre nœud (ex : J et K sont les fils de F)
-  * //__nœud père :__// le nœud B est le père des nœuds D et E
+  * //__nœud père :__// nœuds au-dessus de nœuds fils (ex: F est le père de J et K)
   * //__feuille :__// nœud n'ayant aucun fils (ex : D)
   * //__arête :__// segment qui relie deux nœuds
   * //__profondeur d'un nœud :__// nombre de nœuds du chemin entre la racine et le nœud (ex : F est à une profondeur de 3)
-  * //__hauteur d'un noeud :__// profondeur maximale de l'arbre (ici : 5)
+  * //__hauteur d'un arbre :__// profondeur maximale de l'arbre (ici : 5)
+  * //__taille d'un arbre :__// nombre de nœuds composant l'arbre (ici : 17)
-Dans un arbre binaire, chaque noeud possède au plus 2 fils (souvent appelés fils droit et fils gauche).
-Le sous-arbre d'un noeud est le deux sous-arbre ayant pour racine le fils du noeud. Chaque noeud peut avoir jusqu'à deux sous-arbres (un par fils).
+Un arbre binaire ( ayant donc 1 ou 2 fils) aura forcément des sous-arbres , qui peuvent être comparés à des branches d'un vraie arbre. Donc le sous-arbres gauches est tous les nœuds qui sont sous le nœud donné à gauche. C'est la même chose pour le sous-arbre droit mais cependant c'est à droite .
+Ici , le sous-arbre gauche de A est en rouge et le droit est est violet.
+{{ :les_fiches_revisions:structure_des_donnees:capture_d_ecran_2023-01-18_161010.png?400 |}}
+====Arbres binaires de recherche====
+Un arbre binaire de recherche est un cas particulier d'arbre binaire. Pour avoir un arbre binaire de recherche :
+  * il faut avoir un arbre binaire
+  * il faut que les clés de noeuds composant l'arbre soient ordonnables (on doit pouvoir classer les noeuds, par exemple, de la plus petite clé à la plus grande)
+  * soit x un noeud d'un arbre binaire de recherche :
+                 - Si y est un noeud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé.
+                 - Si y est un noeud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé.

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page