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

Tout d'abord, définissez un arbre binaire de recherche, représenté en code Java comme suit :

public class BST<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;
        }
    }
    // Nœud racine
    private Node root;
    // Nombre de nœuds dans l'arbre
    private int count;
    // Constructeur, construit un arbre binaire de recherche vide par défaut
    public BST() {
        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;
    }
}

Node représente un nœud, et count représente le nombre de nœuds.

L'exemple suivant montre les étapes d'insertion de l'élément 61 dans l'arbre binaire de recherche ci-dessous :

(1) L'élément à insérer, 61, est supérieur à 42 ; comparez le nœud racine du sous-arbre droit de 42.

(2) 61 est supérieur à 59, donc 61 doit être déplacé à la position correspondante dans le sous-arbre droit de 59. Comme il est vide ici, insérez-le directement comme nœud enfant droit de 59.

L'opération d'insertion est également un processus récursif, couvrant trois cas : égal, supérieur à et inférieur à.

Exemple de code Java

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

Code du fichier src/example/binary/BinarySearchTreeInsert.java :

package example.binary;

/**
* Insérer un nouvel élément dans l'arbre binaire de recherche
 */

public class BinarySearchTreeInsert<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;
        }
    }

    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 BinarySearchTreeInsert() {
        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);
    }

    // Code principal --- début
    // 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;
    }
    // Code principal --- fin
}
autres extensions