Comptage des nœuds feuilles dans un arbre de hiérarchie familiale
Considérons une hiérarchie familiale modélisée par un arbre généalogique. L'objectif est de déterminer, pour chaque niveau de profondeur depuis la racine, le nombre de membres sans enfants (nœuds feuilles).
Spécification d'entrée : Chaque cas de test débute par une ligne contenant deux entiers N et M. N représente le nombre total de nœuds dans ...
Publié le 1 juin à 07h08
Décomposition en chaînes lourdes dans les arbres
Principe fondamental
Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs.
Définitions essentielles
Fils lourd : enfant dont la sous-arbre contient le plus de nœuds
Fils léger : tout enfant n'étant pas fils lourd
Arête lourde : reliant un nœud à son fils lourd
Arête légère : ...
Publié le 31 mai à 07h30