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;
    Noeud droit;

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

  private Noeud racine;
  private int taille = 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);
      taille++;
      return true;
    }

    Noeud actuel = racine;
    Noeud parent = null;
    int cmp = 0;

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

      if (cmp < 0) {
        actuel = actuel.gauche; // aller à gauche
      } else if (cmp > 0) {
        actuel = actuel.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);
    }

    taille++;
    return true;
  }

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

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

      if (cmp == 0) {
        return actuel;
      }
      if (cmp < 0) {
        actuel = actuel.gauche;
      } else {
        actuel = actuel.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;
    Noeud actuel = racine;

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

    if (actuel == null) {
      return false;
    }

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

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

      // Remplacer la clé
      actuel.cle = suivant.cle;
      parent = succParent;
      actuel = suivant;
    }

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

    if (parent == null) {
      racine = child;
    } else if (parent.gauche == actuel) {
      parent.gauche = child;
    } else {
      parent.droit = child;
    }

    taille--;
    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 taille;
  }

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

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

  @Override
  public Object[] toArray() {
    Object[] arr = new Object[taille];
    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();
  }
}