Arbre de recherche binaire à partir de zéro en Java

Présentation
Un arbre de recherche binaire (BST) est un type d'arbre binaire dans lequel chaque nœud a au plus deux enfants, appelés enfant de gauche et enfant de droite. Pour chaque nœud, le sous-arbre de gauche contient uniquement les nœuds dont les valeurs sont inférieures à la valeur du nœud, et le sous-arbre de droite contient uniquement les nœuds dont les valeurs sont supérieures à la valeur du nœud. Les BST sont utilisés pour des opérations efficaces de recherche, d'insertion et de suppression.

Pourquoi utiliser un arbre de recherche binaire ?
Les BST offrent plusieurs avantages :

Recherche efficace : la complexité temporelle moyenne est de O (log n) pour la recherche, l'insertion et la suppression.
Ensemble d'éléments dynamique : prend en charge les opérations dynamiques, contrairement aux tableaux statiques.
Éléments ordonnés : le parcours dans l'ordre d'un BST produit des éléments dans un ordre trié.
Guide étape par étape pour créer un BST
Étape 1 : Définir la structure des nœuds
La première étape consiste à définir la structure d’un nœud dans l’arborescence. Chaque nœud aura trois attributs : une valeur, une référence à l'enfant de gauche et une référence à l'enfant de droite.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Étape 2 : Créer la classe BST avec le constructeur
Ensuite, nous créons la classe BST qui contient une référence à la racine de l'arborescence et les méthodes d'insertion d'éléments.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

Étape 3 : implémenter la méthode d'insertion
Pour insérer un élément dans le BST, nous devons trouver la bonne position pour le nouveau nœud. La méthode d'insertion est généralement implémentée sous forme de fonction récursive.

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertRec(root.left, value);
    } else if (value > root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

Visualisation
Pour mieux comprendre le fonctionnement de l'insertion, prenons un exemple. Supposons que nous voulions insérer la séquence de nombres suivante dans le BST : 50, 30, 70, 20, 40, 60, 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

Insérer 40 :

  50
 /  \
30  70
/ \

Insérer 60

  50
 /  \
30  70
/ \  /

Insérer 80 :

  50
 /  \
30  70
/ \  / \

Code complet
Voici le code complet pour créer un BST et insérer des éléments :

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!