Définition d'un Arbre Binaire de Recherche

• Les clés sont uniques
• Toutes les clés du sous-arbre gauche sont inférieures à la clé racine
• Toutes les clés du sous-arbre droit sont supérieures à la clé racine

Structure de Nœud

class NoeudABR {
    int cle;
    Object valeur;
    NoeudABR gauche;
    NoeudABR droit;

    NoeudABR(int cle) {
        this.cle = cle;
    }

    NoeudABR(int cle, Object valeur) {
        this.cle = cle;
        this.valeur = valeur;
    }
}

Recherche de Valeur par Clé

Version Itérative

Object trouver(int cle) {
    NoeudABR courant = racine;
    while(courant != null) {
        if(cle < courant.cle) 
            courant = courant.gauche;
        else if(cle > courant.cle) 
            courant = courant.droit;
        else 
            return courant.valeur;
    }
    return null;
}

Version Récursive

Object trouverRec(int cle) {
    return chercher(racine, cle);
}

Object chercher(NoeudABR n, int cle) {
    if(n == null) return null;
    if(cle < n.cle) return chercher(n.gauche, cle);
    if(cle > n.cle) return chercher(n.droit, cle);
    return n.valeur;
}

Recherche de Valeur Minimale

Object min() {
    if(racine == null) return null;
    NoeudABR n = racine;
    while(n.gauche != null) 
        n = n.gauche;
    return n.valeur;
}

Rechecrhe de Valeur Maximale

Object max() {
    NoeudABR n = racine;
    while(n.droit != null) 
        n = n.droit;
    return n.valeur;
}

Insertion de Clé-Valeur

void inserer(int cle, Object val) {
    NoeudABR parent = null;
    NoeudABR courant = racine;
    
    while(courant != null) {
        parent = courant;
        if(cle < courant.cle) 
            courant = courant.gauche;
        else if(cle > courant.cle) 
            courant = courant.droit;
        else {
            courant.valeur = val;
            return;
        }
    }
    
    NoeudABr nouveau = new NoeudABR(cle, val);
    if(parent == null) 
        racine = nouveau;
    else if(cle < parent.cle) 
        parent.gauche = nouveau;
    else 
        parent.droit = nouveau;
}

Prédécesseur et Successeur

Prédécesseur

Object predecesseur(int cle) {
    NoeudABR courant = racine;
    NoeudABR ancetre = null;
    while(courant != null) {
        if(cle < courant.cle) 
            courant = courant.gauche;
        else if(cle > courant.cle) {
            ancetre = courant;
            courant = courant.droit;
        } else break;
    }
    if(courant == null) return null;
    if(courant.gauche != null) 
        return maxSousArbre(courant.gauche);
    return ancetre != null ? ancetre.valeur : null;
}

Successeur

Object successeur(int cle) {
    NoeudABR courant = racine;
    NoeudABR ancetre = null;
    while(courant != null) {
        if(cle < courant.cle) {
            ancetre = courant;
            courant = courant.gauche;
        } else if(cle > courant.cle) 
            courant = courant.droit;
        else break;
    }
    if(courant == null) return null;
    if(courant.droit != null) 
        return minSousArbre(courant.droit);
    return ancetre != null ? ancetre.valeur : null;
}

Suppression de Nœud

void supprimer(int cle) {
    NoeudABR parent = null;
    NoeudABR courant = racine;
    
    while(courant != null && courant.cle != cle) {
        parent = courant;
        if(cle < courant.cle) courant = courant.gauche;
        else courant = courant.droit;
    }
    
    if(courant == null) return;
    
    if(courant.gauche == null) 
        remplacer(parent, courant, courant.droit);
    else if(courant.droit == null) 
        remplacer(parent, courant, courant.gauche);
    else {
        NoeudABr succParent = courant;
        NoeudABr succ = courant.droit;
        while(succ.gauche != null) {
            succParent = succ;
            succ = succ.gauche;
        }
        if(succParent != courant) {
            remplacer(succParent, succ, succ.droit);
            succ.droit = courant.droit;
        }
        remplacer(parent, courant, succ);
        succ.gauche = courant.gauche;
    }
}

void remplacer(NoeudABR parent, NoeudABr ancien, NoeudABr nouveau) {
    if(parent == null) racine = nouveau;
    else if(parent.gauche == ancien) parent.gauche = nouveau;
    else parent.droit = nouveau;
}

Requêtes par Intervalle

Clés Inférieures

List<Object> clesInferieures(int borne) {
    List<Object> resultat = new ArrayList<>();
    Deque<NoeudABR> pile = new ArrayDeque<>();
    NoeudABr n = racine;
    while(n != null || !pile.isEmpty()) {
        if(n != null) {
            pile.push(n);
            n = n.gauche;
        } else {
            NoeudABr t = pile.pop();
            if(t.cle < borne) resultat.add(t.valeur);
            else break;
            n = t.droit;
        }
    }
    return resultat;
}

Clés Supérieures

List<Object> clesSuperieures(int borne) {
    List<Object> resultat = new ArrayList<>();
    Deque<NoeudABR> pile = new ArrayDeque<>();
    NoeudABr n = racine;
    while(n != null || !pile.isEmpty()) {
        if(n != null) {
            pile.push(n);
            n = n.droit;
        } else {
            NoeudABr t = pile.pop();
            if(t.cle > borne) resultat.add(t.valeur);
            else break;
            n = t.gauche;
        }
    }
    return resultat;
}

Clés dans Intervalle

List<Object> entreDeuxValeurs(int min, int max) {
    List<Object> resultat = new ArrayList<>();
    Deque<NoeudABR> pile = new ArrayDeque<>();
    NoeudABr n = racine;
    while(n != null || !pile.isEmpty()) {
        if(n != null) {
            pile.push(n);
            n = n.gauche;
        } else {
            NoeudABr t = pile.pop();
            if(t.cle >= min && t.cle <= max) 
                resultat.add(t.valeur);
            else if(t.cle > max) break;
            n = t.droit;
        }
    }
    return resultat;
}