restricted:alg-1:tp3.5

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
restricted:alg-1:tp3.5 [2015/09/29 11:54] – fbruckerrestricted:alg-1:tp3.5 [2015/10/31 10:01] (Version actuelle) – fbrucker
Ligne 1: Ligne 1:
 +====== TP 3.5 ======
  
 +Pour aller plus loin que le tp3. En est la suite directe et concerne les arbres.
 +
 +
 +===== Structure =====
 +
 +Utilisez la structure vue dans le tp3 pour encoder un arbre (la racine sera de numéro 0).
 +
 +Comment reconnaître la racine en ne connaissant que la structure ? 
 +
 +Encodez l'arbre de la figure suivante : 
 +
 +{{restricted:alg-1:tp3.5:arbre.png}}
 +
 +===== Codage par parent =====
 +
 +Le codage par parent d'un arbre est une façon compacte de décrire un arbre de N noeuds. On suppose pour cela que :
 +  * tous les sommets on un numéro unique entre 0 et N-1,
 +  * la racine a un numéro de 0.
 +
 +Le code consiste en un tableau de longueur N où la case d'indice $i$ contient l'indice du parent du noeud $i$.
 +
 +
 +===== Chemins =====
 +
 +==== A la racine ====
 +
 +Déduire du codage par parent une façon de trouver le chemin allant d'un noeud à la racine en $\mathcal{O}(N)$
 +
 +==== Entre deux noeuds quelconques ====
 +
 +Etant donné le chemin entre $i$ et la racine et le chemin entre $j$ et la racine, montrez que ces deux chemins sont identiques à partir d'un élément $k$ (cet élément pouvant être la racine). 
 +
 +En déduire un moyen en $\mathcal{O}(N)$ de trouver le chemin entre $i$ et $j$.