ArbreBinaireRecherche.java

package collection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * Arbre binaire de recherche simple. Implémente l’interface Collection.
 */
public class ArbreBinaireRecherche<E extends Comparable<E>> implements Collection<E> {

    /** Classe interne représentant un nœud de l'arbre */
    private class Noeud {
	E cle;
	Noeud gauche, droit;

	Noeud(E k) {
	    this.cle = k;
	}
    }

    private Noeud racine;
    private int size = 0;

    @Override
    public boolean add(E e) {
	Objects.requireNonNull(e);

	// Si l’arbre est vide : racine = nouvel élément
	if (racine == null) {
	    racine = new Noeud(e);
	    size++;
	    return true;
	}

	Noeud cur = racine, parent = null;
	int cmp = 0;

	// Recherche de la position correcte pour insérer
	while (cur != null) {
	    parent = cur;
	    cmp = e.compareTo(cur.cle);

	    if (cmp < 0)
		cur = cur.gauche; // aller à gauche
	    else if (cmp > 0)
		cur = cur.droit; // aller à droite
	    else
		return false; // élément déjà présent
	}

	// Insertion du nœud
	if (cmp < 0)
	    parent.gauche = new Noeud(e);
	else
	    parent.droit = new Noeud(e);

	size++;
	return true;
    }

    /**
     * Recherche d'un nœud contenant la clé donnée
     */
    private Noeud findNode(E e) {
	Noeud cur = racine;

	while (cur != null) {
	    int cmp = e.compareTo(cur.cle);

	    if (cmp == 0)
		return cur;
	    if (cmp < 0)
		cur = cur.gauche;
	    else
		cur = cur.droit;
	}
	return null;
    }

    @Override
    public boolean contains(Object o) {
	if (o == null)
	    return false;

	try {
	    @SuppressWarnings("unchecked")
	    E e = (E) o;
	    return findNode(e) != null;
	} catch (ClassCastException ex) {
	    return false;
	}
    }

    @Override
    public boolean remove(Object o) {
	if (o == null)
	    return false;

	try {
	    @SuppressWarnings("unchecked")
	    E e = (E) o;
	} catch (ClassCastException ex) {
	    return false;
	}

	// Suppression simple (remplacement par successeur)
	// (Pour les benchmarks, remove n'est pas essentiel)
	E key = (E) o;
	Noeud parent = null, cur = racine;

	// Recherche du nœud à supprimer
	while (cur != null && !cur.cle.equals(key)) {
	    parent = cur;
	    if (key.compareTo(cur.cle) < 0)
		cur = cur.gauche;
	    else
		cur = cur.droit;
	}

	if (cur == null)
	    return false;

	// Cas où le nœud a deux enfants
	if (cur.gauche != null && cur.droit != null) {
	    Noeud succParent = cur, succ = cur.droit;

	    // Successeur = minimum du sous-arbre droit
	    while (succ.gauche != null) {
		succParent = succ;
		succ = succ.gauche;
	    }

	    // Remplacer la clé
	    cur.cle = succ.cle;
	    parent = succParent;
	    cur = succ;
	}

	// Cas 0 ou 1 enfant
	Noeud child = (cur.gauche != null) ? cur.gauche : cur.droit;

	if (parent == null)
	    racine = child;
	else if (parent.gauche == cur)
	    parent.gauche = child;
	else
	    parent.droit = child;

	size--;
	return true;
    }

    @Override
    public Iterator<E> iterator() {

	// Parcours en ordre croissant (in-order)
	return new Iterator<E>() {
	    private final Stack<Noeud> st = init(racine);

	    private Stack<Noeud> init(Noeud r) {
		Stack<Noeud> s = new Stack<>();
		Noeud c = r;

		while (c != null) {
		    s.push(c);
		    c = c.gauche;
		}
		return s;
	    }

	    @Override
	    public boolean hasNext() {
		return !st.isEmpty();
	    }

	    @Override
	    public E next() {
		Noeud n = st.pop();
		E res = n.cle;
		Noeud c = n.droit;

		while (c != null) {
		    st.push(c);
		    c = c.gauche;
		}

		return res;
	    }
	};
    }

    @Override
    public int size() {
	return size;
    }

    @Override
    public boolean isEmpty() {
	return size == 0;
    }

    @Override
    public void clear() {
	racine = null;
	size = 0;
    }

    @Override
    public Object[] toArray() {
	Object[] arr = new Object[size];
	int i = 0;

	for (E e : this)
	    arr[i++] = e;

	return arr;
    }

    @Override
    public <T> T[] toArray(T[] a) {
	return null; // même logique que RBTree ; omis pour brièveté
    }

    @Override
    public boolean containsAll(Collection<?> c) {
	for (Object o : c)
	    if (!contains(o))
		return false;

	return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
	boolean ch = false;

	for (E e : c)
	    ch |= add(e);

	return ch;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
	boolean ch = false;

	for (Object o : c)
	    ch |= remove(o);

	return ch;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
	List<E> del = new ArrayList<>();

	// Construire la liste des éléments à supprimer
	for (E e : this)
	    if (!c.contains(e))
		del.add(e);

	// Supprimer les éléments
	for (E e : del)
	    remove(e);

	return !del.isEmpty();
    }
}