« Programmation algorithmique/Arbres » : différence entre les versions
Contenu supprimé Contenu ajouté
+ |
|||
Ligne 14 :
* Parcours en Profondeur, on part de la racine et on descends jusqu'à une première feuille avant de passer aux nœuds suivant puis remonter. Dans cette représentation, les feuilles apparaissent aux côtés de leur arborescence.
* Parcours en Largeur, les élément du niveau courant est noté puis on passe au fils de chacun d'eux. Cela peut s'apparenter à la vue dans un navigateur de fichier (Explorer Windows, Nautilus...).
== Intérêt ==
Le classement d'une série de données avec un arbre permet des recherches en log(N) si l'arbre est "équilibré" (si dans tout l'arbre, pour 2 branches voisines, on a soit une longueur égale, soit une différence de longueur de 1 au maximum).
Il existe des algorithmes peu coûteux pour garder un arbre "équilibré" sur insertion ou suppression d'un élément.
Exemple :
Si chaque noeud a 2 fils, un arbre "équilibré" de 63 éléments aura une profondeur de seulement 6 :
* 1er niveau = 1 noeud racine
* 2ème niveau = 2 noeuds
* 3ème niveau = 4 noeuds
* ...
* 6ème niveau = 32 noeuds
Une recherche d'un élément se fera donc bien en 6 tests (et 64 = 2**6 => log(64) = 6 * log (2) )
| |||