1 Range Minimum Queries

Dans cet exercice, nous allons implémenter une manière efficace de répondre au problème appelé Range Minimum Query sur un tableau T de taille n. Étant donnés deux indices 0 ≤ l ≤ r < n, le résultat renvoyé par rmq(T, l, r) sera un élément de valeur minimale parmi ceux stockés dans le sous-tableau T[l..r] (de l inclus à r inclus).

Les données manipulées sont des paires (String s, int val) où val est la valeur et s une étiquette. Elles sont codées par la classe Data (fournie).

public class Data {
    String s;  // étiquette de la donnée
    int val;   // valeur de la donnée

    Data(String s, int val) {
        this.s   = s;
        this.val = val;
    }

    public int compareTo(Data d) {
        if(this.val>d.val) return 1;
        else if(this.val<d.val) return -1;
        return 0;
    }

    /* Renvoie l'élément ayant valeur minimale entre d1 et d2 */
    static Data min(Data d1, Data d2) {
        if (d1.compareTo(d2) <= 0) return d1;
        else return d2;
    }

    /* Affiche les éléments d'un tableau de type Data[] */
    static void printArray(Data[] T) {...}
}

La comparaison entre deux données d1 et d2 peut se faire à l’aide de la méthode int compareTo(...). On fournit aussi la fonction Data min(Data d1, Data d2) qui renvoie la donnée ayant la valeur minimale entre d1 et d2.

Les données sont stockées dans un tableau Data[] T qui constitue l’entrée du programme.

Dans l’exemple ci-dessous, le tableau T contient les données démographiques de 16 villes dans le monde. Le résultat de rmq(T, 5, 11) est (Los Angeles, 3287), car c’est la donnée de plus petite valeur entre l’indice 5 (New York) et l’indice 11 (Buenos Aires).

public class EfficientRMQ implements RMQ {
    Data[] table; // tableau en entrée
    int b;         // taille des blocs
    Data[] B;     // tableau auxiliaire

    /* Initialise le tableau auxiliaire */
    EfficientRMQ(Data[] table, int b) {...}

    /* Renvoie un élément de valeur minimale */
    public Data getMin(int l, int r) {...}
}

2 Arbres et calcul du LCA

Dans cet exercice, nous manipulons des arbres généraux dont les nœuds ont une arité (nombre de fils) arbitraire. Les nœuds sont représentés à l’aide de la classe Tree (fournie).

/* Classe qui représente un (noeud d'un) arbre général */
public class Tree {
    /* étiquette stockée dans le nœud */
    String element;

    /* vecteur stockant les fils du nœud courant */
    Vector<Tree> children;

    /* Construit un nœud de l'arbre ayant 'element' pour étiquette. */
    Tree(String element) {
        this.element = element;
        this.children = new Vector<Tree>();
    }

    // Pour aider le debugging
    /* affiche les noeuds de l'arbre selon un parcours BFS (par niveaux) */
    static void print(Tree node) {...}
}

Un nœud contient un champ String element (la donnée stockée dans le nœud) et un Vector (champ children) contenant les sous-arbres. Un nœud est une feuille si le vecteur est vide.

On souhaite implémenter une fonction qui, étant données les deux étiquettes el1 et el2 de deux nœuds dans un même arbre, calcule leur plus proche ancêtre commun (en anglais Lowest Common Ancestor ou LCA), c’est-à-dire le nœud le plus éloigné de la racine qui soit à la fois un ancêtre du nœud el1 et du nœud el2.

Remarque (importante) : dans la suite, on supposera que l’arbre considéré contient des étiquettes toutes distinctes et que les étiquettes el1 et el2 de la requête sont distnicteapparaissent bien dans l’arbre. Ainsi, on pourra aussi supposer que l’arbre en entrée contient au moins deux éléments.

Les images ci-dessous illustrent la définition du LCA :

Suggestion (aide pour débogage) La classe Tree est munie d’une méthode void print(Tree node) qui affiche les nœuds de l’arbre par niveaux. L’arbre illustré dans l’exemple sera ainsi affiché :

A
B C D E
F G H I J K
L

3 LCA (plus efficace)

Il est possible de calculer le lca(el1, el2) en traduisant un problème de requête sur un arbre en un problème de range minimum query sur un tableau. Cela peut s’avérer efficace lorsque le nombre de requêtes de type LCA est important par rapport à la taille de l’arbre.

Remarque : comme fait auparavant, on pourra supposer que l’arbre en entrée a une taille au moins 2, et contient notamment les étiquettes el1 et el2 qui sont censées être distinctes.

Dans une première phase, nous allons remplir un tableau Data[] dist de longueur 2n − 1 (où n est la taille de l’arbre) de la manière suivante. En partant de la racine, on effectue un parcours récursif de l’arbre comme ceci : chaque fois qu’on rencontre un nœud,

• on stocke dans dist la paire (el, depth), où el est l’étiquette du nœud et depth sa profondeur (distance à la racine) ;

• on parcourt récursivement tous ses sous-arbres ;

• on stocke une occurrence supplémentaire de (el, depth) dans le tableau dist.

Par ailleurs, on remplit une table de hachage indices avec, pour chaque étiquette el de l’arbre, l’indice de sa première occurrence dans le tableau dist.

Voici une illustration du résultat sur un arbre contenant n = 12 nœuds :

Pour répondre à une requête de type lca(s1, s2) sur l’arbre, on peut localiser (en temps constant) les deux indices i1 et i2 correspondants aux premières occurrences de s1 et s2 dans le tableau dist. Puis trouver la paire de profondeur minimale dans dist[i1..i2] en utilisant une implémentation de Range Minimum Query.

On se donne une classe EfficientLCA pour les questions suivantes.

public class EfficientLCA {

    /* Implémentation de RMQ: naive (ex 1.1) ou efficace (1.3) */
    RMQ rmq;

    /* l'arbre considéré */
    Tree node;

    /* pour chaque nœud, on stocke sa distance à la racine */
    Data[] dist;

    /* pour chaque nœud, stoque son indice dans dist[]
    (utile pour exo 3.1) */
    HashMap<String,Integer> indices=new HashMap<String,Integer>();

    EfficientLCA(Tree node, int b) {
        this.node = node;
        int n=Tree.size(node);
        this.dist=new Data[2*n-1];
        ...
    }

}