1 Tableaux

Le but de cet exercice est d’implémenter de manière efficace les fonctions ci-dessous agissant sur un tableau d’entiers int[] t. Les tableaux reçus en argument ne doivent pas être modifiés.

Important (exercice 1): vous devrez soumettre un seul fichier pour la partie 1 (formulaire à la fin de la Section 1), contenant les solutions des questions 1.1, 1.2.

Les questions 1.1 et 1.2 sont indépendantes et peuvent se traiter dans n’importe quel ordre.

public class EfficientArrayOperations {

    static int coupureEquilibree(int[] t) {...}
    static boolean doublonProche(int[] t, int k) {...}

}

1.1 Coupure équilibrée

On souhaite couper un tableau t = [t₀, t₁, …, t_n − 1] contenant n entiers en deux parties consécutives et non vides de manière équilibrée: il faudra calculer un indice 0 < p < n tel que les sommes S_g = t₀ + t₁ + … + t_p − 1 et S_d = t_p + t_p + 1 + … + t_n − 1 doivent être aussi proches que possible, c’est-à-dire qu’on veut minimiser
|S_g − S_d|
En cas d’égalité il faudra renvoyer le plus petit indice qui donne une coupe équilibrée.

Les éléments du tableau peuvent être positifs, négatifs ou nuls. On pourra supposer que le tableau contient au moins deux éléments.

Dans la classe EfficientArrayOperations

compléter la méthode int coupureEquilibree(int[] t), qui doit renvoyer un indice p, compris entre 1 et t.length-1, minimisant la différence en valeur absolue entre : la somme des éléments t[0], ..., t[p-1] et la somme des éléments t[p], ..., t[t.length - 1].

Si plusieurs indices conviennent, la méthode doit renvoyer le plus petit. Utiliser des variables de type long pour les sommes et les écarts. La méthode Math.abs() permet de calculer une valeur absolue.

Voici quelques exemples d’exécution de la méthode coupureEquilibree(int[] t)

Tableau `t`	Résultat attendu
{4, 1, 2, 3}	2
{1, 1, 1}	1
{-2, 5, -1, 2}	3
{7, -3}	1

Suggestion (pour question 1.1) : dans une première phase, calculer la somme totale du tableau dans une première boucle. Parcourir ensuite les coupures possibles de gauche à droite. Maintenir une variable contenant la somme des éléments situés à gauche de la coupure. À chaque déplacement, un seul élément passe de la partie droite à la partie gauche. Calculer la somme de droite à partir de la somme totale et de celle de gauche. Mémoriser le meilleur écart rencontré et l’indice correspondant.

Important (Complexité) : Votre programme doit avoir une complexité linéaire et ne doit pas créer de tableau auxiliaire. Une solution trop lente pour les plus grandes entrées, de complexité plus que linéaire, ne sera pas acceptée.

Tester votre code avec la classe Test11.

1.2 Détection de répétitions rapprochées

Dans cet exercice nous souhaitons tester si un tableau t contient des doublons qui sont à distance au plus k.

Dans la classe EfficientArrayOperations, compléter la méthode suivante:

static boolean doublonProche(int[] t, int k) qui renvoie true s’il existe deux indices distincts i < j tels que : t[i] = t[j] et j − i ≤ k. La fonction doit renvoyer false sinon.

Le tableau t peut être vide et k est un entier positif ou nul.

Voici quelques exemples d’exécution de la méthode doublonProche(int[] t, int k)

Tableau `t`	k	Résultat attendu
{8, 3, 5, 8, 3}	2	false
{8, 3, 5, 8, 3}	3	true
{5, 1, 2, 5, 5}	1	true
{4, 4}	0	false
{}	5	false

Important (Complexité) : Une solution en temps moyen O(n), où n est la taille du tableau t, est attendue. Une solution examinant toutes les paires d’indices sera trop lente pour les plus grandes entrées et ne sera pas acceptée.

Suggestion (exercice 1.2) : Vous pourrez utiliser une table de hachage (HashMap) qui associe à chaque valeur déjà rencontrée l’indice de sa dernière occurrence, en utilisant la syntaxe HashMap<Integer, Integer> derniere = new HashMap<>();

Tester votre code avec la classe Test12.

Dépôt partie 1: déposer EfficientArrayOperations.java.

2 Arbres d’Arne Andersson

Important (exercice 2): vous devrez soumettre un seul fichier (Aa.java) pour la partie 2, contenant les solutions des questions 2.1, 2.2, 2.3, 2.4 et 2.5.

Ces questions NE SONT PAS indépendantes: avant de passer à la question suivante, pensez à tester vos fonctions et assurez-vous du résultat positif du test.

Le formulaire de soumission se trouve tout en bas de la page.

Dans cet exercice, nous allons implémenter une classe d’arbres bien équilibrés différente (et plus simple) de celle vue en cours (AVL). Il s’agit des arbres d’Arne Andersson (dans la suite, on les appellera arbres AA).

Intuition: dans un arbre AA les nœuds noirs apparaissent en même nombre sur tout chemin de la racine à une feuille, tandis que ceux rouges peuvent apparaître en nombres différents sur différentes branches, mais ne sont pas trop fréquents.

Définition (arbres AA) Un arbre binaire de recherche est AA si et seulement s’il satisfait les propriétés suivantes :

chaque nœud a une couleur pouvant être rouge ou noire;
la racine est noire;
les deux fils d’un nœud rouge sont noirs;
(garantie forte d’équilibrage): le nombre de nœuds noirs est le même sur tous les chemins allant de la racine aux feuilles ; ce nombre est appelé le niveau de l’arbre;
le fils gauche de tout nœud est noir (autrement dit, tout nœud rouge est le fils droit d’un autre nœud).

Un arbre `AA` de niveau 2	Un arbre rouge et noir qui n’est pas `AA`

Rappel: Par convention, un arbre vide est représenté par null.

Comment implémenter un arbre AA en Java

class Aa {
    final int valeur, couleur;
    final Aa gauche, droit;
    static final int R=0, N=1;

    // Constructeur
    Aa (int valeur, int couleur, Aa gauche, Aa droit) {
        this.valeur = valeur;
        this.couleur = couleur;
        this.gauche = gauche;
        this.droit = droit;
    }

    static String infixe (Aa a) {
        return (a==null)?"":(infixe(a.gauche) + " " + a.valeur + infixe(a.droit));
    }

}

Une implémentation d’un arbre AA est fournie (classe Aa): le champ couleur indique la couleur du nœud (0 pour rouge, 1 pour noir). Les deux constantes de classe, static final int R=0, N=1 correspondent à ces deux couleurs. Dans la suite, vous pourrez utiliser ces deux constantes plutôt que des entiers pour fixer les couleurs des nœuds.

La classe Aa est munie d’un constructeur Aa (int valeur, int couleur, Aa gauche, Aa droit) qui initialise les champs du nouvel arbre. Il faut noter que ce constructeur peut construire des arbres qui ne sont pas AA et devra donc être utilisé avec précaution par la suite.

Débogage: pour vous aider dans la phase de débogage on fournit aussi une fonction static String infixe (Aa a) qui parcourt l’arbre a et renvoie une chaîne de caractères listant les valeurs contenues dans les nœuds de a selon l’ordre infixe.

Indication : Pour l’arbre AA ci-dessus, le résultat de la fonction infixe(a) est la chaîne de caractères suivante:

1 3 5 6 8 9 11

Cet arbre est de niveau 2 et peut s’obtenir avec le code Java suivant:

        Aa a = new Aa (3, Aa.N,
           new Aa (1, Aa.N, null, null),
           new Aa (8, Aa.R,
               new Aa (5, Aa.N,
                   null,
                   new Aa (6, Aa.R, null, null)),
               new Aa (9, Aa.N,
                   null,
                   new Aa (11, Aa.R, null, null))));

}

2.1 Niveau d’un arbre

On va d’abord calculer, étant donné un arbre AA, le nombre de sommets noirs sur un chemin allant de la racine aux feuilles. Cette fonction nous sera utile pour la question suivante.

Dans la classe Aa, compléter la méthode

static int niveau (Aa a) qui compte le nombre de sommets noirs de la racine à une feuille arbitraire. Le niveau de l’arbre vide (null) est 0.

Testez votre code avec la classe Test21.

2.2 Vérifier l’équilibrage d’un arbre

On souhaite vérifier de manière automatique que les arbres que nous allons construire satisfont bien les propriétés d’équilibrage des arbres AA. On pourra supposer que les arbres en entrée sont bien des Arbres Binaires de Recherche, et on cherche juste à vérifier que les couleurs respectent les propriétés des arbres AA.

Dans la classe Aa, compléter la méthode

static boolean testSousArbreAa(Aa a, int n, boolean racinePeutEtreRouge) qui a le comportement suivant:
- testSousArbreAa(a, n, true) renvoie true si et seulement si l’arbre a est un arbre AA de niveau n.
- testSousArbreAa(a, n, false) renvoie true si et seulement si l’arbre a est un arbre AA de niveau n tel que a.couleur = N.

Indication La méthode pourra être codée récursivement sur les deux sous-arbres de a. À vous de trouver les bonnes valeurs des paramètres pour ces appels récursifs, et le bon cas d’arrêt.

Dans la classe Aa, compléter la méthode

static boolean testSousArbreAa(Aa a) qui teste si l’arbre a est bien un arbre AA: cette fonction est appelée récursivement et fait appel à la fonction testSousArbreAa(Aa a, int n, boolean racinePeutEtreRouge) (à vous de trouver les bonnes valeurs des paramètres pour ces appels récursifs).

Testez votre code avec la classe Test22.

Insertion et maintien des propriétés des arbres AA

Nous allons à présent implémenter une méthode permettant d’insérer un élément dans un arbre AA, tout en conservant les propriétés des arbres AA.

Commençons par examiner ce qui se passe lorsqu’on insère un nœud rouge à la place d’une feuille. Ce choix préserve le nombre de nœuds noirs sur tout chemin de la racine à une feuille.

Deux cas se présentent : + si le nouveau nœud est un fils gauche, il faut rétablir la propriété selon laquelle tout nœud rouge est un fils droit ;

s’il est un fils droit dont le père est rouge, il faut rétablir la propriété selon laquelle les fils d’un nœud rouge sont noirs.

Les autres propriétés des arbres AA restent inchangées.

2.3 Rotation droite

Indication : Afin de comparer les structures de l’arbre a avant et après rééquilibrage, on fournit une classe Fenetre dont le constructeur crée une fenêtre graphique et y affiche la structure de l’arbre. Ainsi, à chaque fois que vous invoquerez new Fenetre(a) dans votre code, une nouvelle fenêtre s’ouvrira et affichera la structure de l’arbre a.

Si un nœud n possède un fils gauche rouge m, on rétablit la propriété correspondante par la rotation droite ci-dessous (un rectangle bleu représente un nœud de couleur quelconque et un triangle violet un sous-arbre AA) :

Cette rotation peut faire apparaître deux nœuds rouges consécutifs sur une branche droite. Cette situation sera corrigée par la rotation gauche présentée dans la section suivante.

Dans la classe Aa, compléter la méthode :

static Aa rotDroite(Aa a), qui effectue, si nécessaire, le rééquilibrage par rotation droite à la racine de a, et renvoie a inchangé sinon.

Testez votre implémentation avec la classe Test23.

2.4 Rotation gauche

Dans le cas où le fils droit de la racine et son propre fils droit sont rouges, on peut obtenir un sous-arbre AA en effectuant la rotation et recoloration illustrée ci-dessous:

Après cette étape, on obtient un arbre AA valide. Sa racine étant rouge, s’il apparait comme sous-arbre d’un autre arbre, un rééquilibrage peut toutefois encore être nécessaire. Ce problème sera résolu de la même manière par application d’une rotation gauche au niveau supérieur.

Dans la classe Aa, compléter

la méthode rotGauche(Aa a) qui effectue le ré-équilibrage ci-dessus à la racine de l’arbre si celui-ci est nécessaire et renvoie l’arbre inchangé dans le cas contraire.

Tester votre code avec la classe Test24.

2.5 Insertion dans un arbre AA

Remarque (complexité de l’insertion): l’insertion est attendue en temps logarithmique, avec création de nœuds sur le chemin de recherche.

À l’aide des méthodes implémentées dans les questions précédentes, dans la classe Aa compléter la méthode (récursive) suivante:

static Aa insere(Aa a, int i) qui insère l’élément i dans l’arbre AA a. Cette méthode renverra un arbre vérifiant toutes les hypothèses des arbres Aa excepté que la racine pourra être noire ou rouge. (Si i est déjà dans a, on renvoie a non modifié.)

Suggestion On pourra suivre recommande l’approche suivante :

effectuer une descente récursive classique (comme pour l’insertion dans un arbre binaire de recherche) ;
insérer un nœud rouge (avec la valeur i) à la place d’une feuille ;
lors de chaque retour d’un appel récursif, appeler successivement les deux méthodes de rééquilibrage décrites plus haut, d’abord rotDroite puis rotGauche sur l’arbre que vous vous apprêtez à renvoyer (c’est-à-dire le nouvel arbre créé suite à l’insertion dans le sous-arbre gauche ou le sous-arbre droit).

Dernière étape: correction de la couleur de la racine

A l’issue du processus ci-dessus, on obtiendra finalement un arbre AA valide, sauf que la racine peut être rouge, ce qui n’est pas autorisé dans la définition des arbres AA. Dans ce cas, il suffit de changer la couleur de la racine, si celle-ci est rouge.

Indication (pour tester et debugger) En cas de problèmes, afin de tester votre code, créez un arbre a vide dans lequel vous insérerez quelques entiers. Après chaque insertion vous pourrez vérifier à la main la validité de la structure de a en l’affichant dans une fenêtre graphique avec la commande new Fenetre(a).

Dans la classe Aa compléter la méthode :

static Aa insereEtCorrigeRacine(Aa a, int i) qui fait un appel à insere(Aa a, int i) puis met à jour la couleur de la racine de l’arbre obtenu si nécessaire. N’oubliez pas que vous ne pouvez pas changer directement la couleur d’un nœud : pour cela, il vous faudra créer un nouveau nœud.

Tester votre code avec la classe Test25.

Dépôt partie 2: déposer Aa.java.