Différences
Ci-dessous, les différences entre deux révisions de la page.
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 07:54] – fbrucker | restricted: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' | ||
+ | |||
+ | {{restricted: | ||
+ | |||
+ | ===== 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' | ||
+ | |||
+ | |||
+ | ===== 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$. |