Suppression d'un nœud dans un arbre binaire de recherche

Avant d'introduire la suppression de nœuds dans un arbre binaire de recherche, cette section explique d'abord comment trouver les valeurs minimale et maximale, et comment supprimer les valeurs minimale et maximale.

Prenons la valeur minimale comme exemple (la valeur maximale est analogue) :

Logique de code pour trouver la valeur de clé minimale : rechercher récursivement vers le bas dans le nœud enfant gauche :

...
// Retourne le nœud ayant la valeur de clé minimale dans l'arbre binaire de recherche de racine node
private Node minimum(Node node){
    if( node.left == null )
        return node;

    return minimum(node.left);
}
...

Pour supprimer la valeur de clé minimale dans un arbre binaire de recherche, si le nœud n'a pas de sous-arbre droit, supprimez-le directement ; si un sous-arbre droit existe, comme le montre la figure :

Suppression du nœud 22 : il a un enfant droit, donc remplacez simplement le nœud 22 par le nœud 33 du sous-arbre droit.

Cette suppression de la valeur minimale est exprimée en code :

...
// Supprime le nœud minimum de l'arbre binaire de recherche de racine node
// Retourne la racine du nouvel arbre binaire de recherche après la suppression du nœud
private Node removeMin(Node node){

    if( node.left == null ){

        Node rightNode = node.right;
        node.right = null;
        count --;
        return rightNode;
    }

    node.left = removeMin(node.left);
    return node;
}
...

Parlons maintenant de la suppression de nœuds dans un arbre binaire de recherche, qui se répartit dans les trois cas suivants :

1、Suppression d'un nœud n'ayant qu'un enfant gauche, comme le nœud 58 dans la figure ci-dessous.

Supprimez l'élément 58 et laissez le sous-arbre gauche prendre directement la position de 58 ; les propriétés de l'ensemble de l'arbre binaire de recherche restent inchangées.

2、Suppression d'un nœud n'ayant qu'un enfant droit, comme le nœud 58 dans la figure ci-dessous.

Supprimez l'élément 58 et laissez le sous-arbre droit prendre directement la position de 58 ; les propriétés de l'ensemble de l'arbre binaire de recherche restent inchangées.

3、Suppression d'un nœud ayant à la fois un enfant gauche et un enfant droit, comme le nœud 58 dans la figure ci-dessous.

(1) Trouvez la valeur minimale dans le sous-arbre droit, qui est le nœud 59.

(2) Le nœud 59 remplace le nœud 58 à supprimer.

D'après les règles ci-dessus, l'exemple de code essentiel pour supprimer le nœud dont la valeur de clé est key dans l'arbre binaire de recherche dont la racine est node est :

Téléchargement du paquet de code source :Télécharger

code du fichier src/example/binary/BSTRemove.java :

package example.binary;

import java.util.LinkedList;

/**
* Suppression de nœud dans un arbre binaire de recherche
 */

public class BSTRemove<Key extends Comparable<Key>, Value>  {
    // Les nœuds dans l'arbre sont une classe privée ; le monde extérieur n'a pas besoin de connaître l'implémentation spécifique des nœuds de l'arbre binaire de recherche
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }

        public Node(Node node){
            this.key = node.key;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
        }
    }

    private Node root;  // Nœud racine
    private int count;  // Nombre de nœuds dans l'arbre

    // Constructeur, construit un arbre binaire de recherche vide par défaut
    public BSTRemove() {
        root = null;
        count = 0;
    }

    // Renvoie le nombre de nœuds dans l'arbre binaire de recherche
    public int size() {
        return count;
    }

    // Renvoie si l'arbre binaire de recherche est vide
    public boolean isEmpty() {
        return count == 0;
    }

    // Insère une nouvelle paire de données (key, value) dans l'arbre binaire de recherche
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Vérifie si key existe dans l'arbre binaire de recherche
    public boolean contain(Key key){
        return contain(root, key);
    }

    // Recherche dans l'arbre binaire de recherche la valeur correspondant à key. Si la valeur n'existe pas, renvoie null
    public Value search(Key key){
        return search( root , key );
    }

    // Parcours préfixe de l'arbre binaire de recherche
    public void preOrder(){
        preOrder(root);
    }

    // Parcours infixe de l'arbre binaire de recherche
    public void inOrder(){
        inOrder(root);
    }

    // Parcours postfixe de l'arbre binaire de recherche
    public void postOrder(){
        postOrder(root);
    }

    // Parcours en largeur de l’arbre binaire de recherche
    public void levelOrder(){

        // Nous utilisons LinkedList comme file d’attente
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(root);
        while( !q.isEmpty() ){

            Node node = q.remove();

            System.out.println(node.key);

            if( node.left != null )
                q.add( node.left );
            if( node.right != null )
                q.add( node.right );
        }
    }

    // Trouver la clé minimale dans l'arbre binaire de recherche
    public Key minimum(){
        assert count != 0;
        Node minNode = minimum( root );
        return minNode.key;
    }

    // Trouver la clé maximale dans l'arbre binaire de recherche
    public Key maximum(){
        assert count != 0;
        Node maxNode = maximum(root);
        return maxNode.key;
    }

    // Supprimer le nœud avec la clé minimale de l'arbre binaire de recherche
    public void removeMin(){
        if( root != null )
            root = removeMin( root );
    }

    // Supprimer le nœud avec la clé maximale de l'arbre binaire de recherche
    public void removeMax(){
        if( root != null )
            root = removeMax( root );
    }

    // Supprimer le nœud avec la valeur de clé key de l'arbre binaire de recherche
    public void remove(Key key){
        root = remove(root, key);
    }

    //********************
    //* Fonctions utilitaires pour l'arbre binaire de recherche
    //********************

    // Insérer le nœud (key, value) dans l'arbre binaire de recherche enraciné au nœud node, en utilisant un algorithme récursif
    // Retourne la racine de l'arbre binaire de recherche après l'insertion du nouveau nœud
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // Vérifie si l'arbre binaire de recherche enraciné à node contient un nœud dont la valeur de clé est key, en utilisant un algorithme récursif
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // Trouver la valeur correspondant à key dans l'arbre binaire de recherche enraciné à node, algorithme récursif
    // Renvoyer NULL si la valeur n'existe pas
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

    // Effectuer un parcours préfixe sur l'arbre binaire de recherche enraciné à node, algorithme récursif
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Effectuer un parcours infixe sur l'arbre binaire de recherche enraciné à node, algorithme récursif
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // Effectuer un parcours post-ordre sur l'arbre binaire de recherche dont la racine est node, algorithme récursif
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }

    // Retourne le nœud ayant la valeur de clé minimale dans l'arbre binaire de recherche de racine node
    private Node minimum(Node node){
        if( node.left == null )
            return node;

        return minimum(node.left);
    }

    // Renvoyer le nœud avec la valeur de clé maximale dans l'arbre binaire de recherche enraciné au nœud node
    private Node maximum(Node node){
        if( node.right == null )
            return node;

        return maximum(node.right);
    }

    // Supprime le nœud minimum de l'arbre binaire de recherche de racine node
    // Retourne la racine du nouvel arbre binaire de recherche après la suppression du nœud
    private Node removeMin(Node node){

        if( node.left == null ){

            Node rightNode = node.right;
            node.right = null;
            count --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    // Supprimer le nœud maximal de l'arbre binaire de recherche enraciné au nœud node
    // Retourne la racine du nouvel arbre binaire de recherche après la suppression du nœud
    private Node removeMax(Node node){

        if( node.right == null ){

            Node leftNode = node.left;
            node.left = null;
            count --;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    // Supprimer le nœud ayant la valeur de clé key de l'arbre binaire de recherche enraciné en node, algorithme récursif
    // Retourne la racine du nouvel arbre binaire de recherche après la suppression du nœud
    Node remove(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) < 0 ){
            node.left = remove( node.left , key );
            return node;
        }
        else if( key.compareTo(node.key) > 0 ){
            node.right = remove( node.right, key );
            return node;
        }
        else{   // key == node->key

            // Le cas où le sous-arbre gauche du nœud à supprimer est vide
            if( node.left == null ){
                Node rightNode = node.right;
                node.right = null;
                count --;
                return rightNode;
            }

            // Le cas où le sous-arbre droit du nœud à supprimer est vide
            if( node.right == null ){
                Node leftNode = node.left;
                node.left = null;
                count--;
                return leftNode;
            }

            // Le cas où les sous-arbres gauche et droit du nœud à supprimer ne sont pas vides

            // Trouver le plus petit nœud supérieur au nœud à supprimer, c'est-à-dire le nœud minimum dans le sous-arbre droit du nœud à supprimer
            // Remplacer le nœud à supprimer par ce nœud
            Node successor = new Node(minimum(node.right));
            count ++;

            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            count --;

            return successor;
        }
    }
}
autres extensions