BinarySearchTree.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 BinarySearchTree<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();
  }
}