Série 7 – Ensembles par arbres de recherche : corrigé

Le code du corrigé est disponible sous la forme d'une archive Zip, qui contient également le code de l'énoncé. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

Le problème qui se pose ici est que la méthode newSet est définie sans borne sur son paramètre de type T :

public abstract class SetTest {
    abstract <T> Set<T> newSet();

    // … méthodes de test
}

Dès lors, on ne peut pas écrire une version concrète de cette méthode qui appelle le constructeur de TreeSet puisque celui-ci exige que le type T soit un sous-type de Comparable<T>. Pour corriger cela, il faut donc ajouter une borne au paramètre de type de la méthode newSet afin qu'elle ait les mêmes exigences. On obtient alors :

public abstract class SetTest {
    abstract <T extends Comparable<T>> Set<T> newSet();

    // … méthodes de test
}

Heureusement, toutes les méthodes de test de TreeSet utilisent déjà des sous-types de Comparable (Integer et String principalement) et il n'y a donc pas d'autres modifications à apporter. Bien entendu, les éventuelles sous-classes existantes de SetTest doivent être adaptées en fonction.

La méthode add peut distinguer deux cas :

1. L'arbre est vide, auquel cas l'élément peut être placé dans un nœud nouvellement créé qui devient la racine,
2. L'arbre n'est pas vide, auquel cas il faut rechercher l'élément à ajouter dans l'arbre. S'il s'y trouve déjà, il n'y a rien à faire. S'il ne s'y trouve pas, il faut l'ajouter dans un nœud qui soit un fils du dernier nœud rencontré lors de la recherche.

Le premier cas est trivial, et le second est nettement simplifié par la méthode nodeOrParentFor, qui retourne soit le nœud contenant l'élément si celui-ci est présent dans l'arbre, soit le dernier nœud rencontré lors de la recherche. Dans ce dernier cas, la méthode add doit simplement créer un nœud pour le nouvel élément et l'ajouter en tant que fils du dernier nœud rencontré.

public void add(E newElem) {
    if (root == null) {
        root = new Node<>(newElem);
    } else {
        Node<E> n = nodeOrParentFor(newElem);
        int cmp = newElem.compareTo(n.elem);
        if (cmp < 0) {
            assert n.smaller == null;
            n.smaller = new Node<>(n, newElem);
        } else if (cmp > 0) {
            assert n.greater == null;
            n.greater = new Node<>(n, newElem);
        } else
            return;
    }
    size += 1;
}

La méthode remove doit commencer par trouver le nœud contenant l'élément à supprimer, s'il existe. Ensuite, elle doit effectivement supprimer ce nœud de l'arbre.

La recherche du nœud peut se faire facilement au moyen de la méthode nodeFor, tandis que la suppression du nœud peut être confiée à une méthode removeNode, qui reste à écrire. L'avantage de procéder ainsi est que la méthode removeNode est également utile pour mettre en œuvre la méthode remove de l'itérateur. La méthode remove elle-même est donc très simple :

public void remove(E elem) {
    Node<E> n = nodeFor(elem);
    if (n != null)
        removeNode(n);
}

La méthode removeNode doit quant à elle distinguer deux cas :

1. le nœud à supprimer possède 0 ou 1 fils,
2. le nœud à supprimer possède deux fils.

Le premier cas est relativement simple, puisque la suppression peut alors se faire de manière similaire à ce que l'on fait dans une liste chaînée. Le second cas est plus compliqué, mais il est heureusement assez facile de le ramener au premier. En effet, si le nœud à supprimer possède deux fils, il suffit de chercher le nœud successeur du nœud à supprimer (c-à-d le nœud contenant le plus petit élément de l'ensemble qui soit plus grand que celui du nœud en question), puis de placer la valeur de ce successeur dans le nœud à supprimer et enfin de supprimer le successeur, qui a au maximum un fils.

La méthode removeNode ci-dessous commence donc par traiter, au besoin, le second cas comme décrit plus haut. Cela fait, on a la garantie de se trouver dans le premier cas, ce qui est exprimé par une assertion. La suppression peut donc se faire de la même manière que dans une liste chaînée, puisqu'on désire supprimer un nœud qui se trouve entre un ou deux voisins (le parent et l'éventuel fils). Le code est légèrement plus complexe que celui de la méthode de suppression de notre classe LinkedList car ici la « liste » n'est pas circulaire et ne possède pas de nœud d'en-tête. Il y a donc plus de cas particuliers à prendre en compte.

private void removeNode(Node<E> n) {
    if (n.smaller != null && n.greater != null) {
        Node<E> s = successor(n);
        n.elem = s.elem;
        n = s;
    }
    assert n.smaller == null || n.greater == null;
    Node<E> maybeChild = (n.smaller != null ? n.smaller : n.greater);
    if (maybeChild != null)
        maybeChild.parent = n.parent;
    if (n.parent == null)
        root = maybeChild;
    else if (n == n.parent.smaller)
        n.parent.smaller = maybeChild;
    else
        n.parent.greater = maybeChild;
    size -= 1;
}

L'itérateur garde deux références pour représenter l'état de l'itération. La première, nommée next, désigne le prochain nœud à parcourir. C'est l'élément contenu dans ce nœud qui est donc retourné par la méthode next. La seconde, nommée last, contient—en première approximation—le prédécesseur de next, ou null lorsque next désigne le premier nœud. La référence last sert à mettre en œuvre la méthode remove et est donc mise à null lorsque cette méthode est appelée et que le nœud qu'elle désigne a été supprimé.

La référence last joue donc également le rôle qui était joué par la variable booléenne canRemove d'autres itérateurs. En effet, il n'est valide d'appeler remove que si last n'est pas null.

L'itérateur n'est pas très difficile à écrire étant donné l'existance de la méthode successor. Il suffit en effet de faire en sorte que next référence initialement le premier nœud de l'arbre (c-à-d celui qui se trouve « en bas à gauche »), et ensuite d'appeler successor dans la méthode next. On obtient donc le code ci-dessous :

public Iterator<E> iterator() {
    return new Iterator<E>() {
        private Node<E> next, last;

        {
            last = null;
            next = root;
            while (next != null && next.smaller != null)
                next = next.smaller;
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            E elem = next.elem;
            last = next;
            next = successor(next);
            return elem;
        }

        @Override
        public void remove() {
            if (last == null)
                throw new IllegalStateException();
            removeNode(last);
            last = null;
        }
    };
}

Pour mémoire, dans une classe anonyme, le code placé entre accolades dans le corps de la classe est exécuté au moment de la construction de l'instance. C'est une sorte de constructeur mais qui ne peut pas prendre d'arguments.