Arbre binaire ou comment préparer un arbre de recherche binaire

Prélude

Cet article est dédié aux arbres binaires de recherche. Récemment, j'ai écrit un article sur la compression des données par la méthode de Huffman. À l'époque, je n'ai pas beaucoup prêté attention aux arbres binaires, car les méthodes de recherche, d'insertion et de suppression n'étaient pas pertinentes. Maintenant, j'ai décidé d'écrire un article spécifiquement sur les arbres. Commençons.

Un arbre est une structure de données composée de nœuds reliés par des arêtes. On peut dire qu'un arbre est un cas particulier d'un graphe. Voici un exemple d'arbre :

Ce n'est pas un arbre binaire de recherche ! Tout est sous le cat !

Terminologie

Racine

La racine de l'arbre est le nœud le plus élevé. Dans cet exemple, il s'agit du nœud A. Dans un arbre, il ne peut y avoir qu'un seul chemin menant de la racine à n'importe quel autre nœud ! En réalité, tout nœud peut être considéré comme la racine de son sous-arbre correspondant.

Parents/enfants

Tous les nœuds, à l'exception de la racine, ont exactement une arête reliant vers un autre nœud. Le nœud situé au-dessus du nœud actuel s'appelle le parent de ce nœud. Le nœud situé en dessous du nœud actuel et connecté à lui s'appelle l'enfant de ce nœud. Prenons un exemple. Si nous prenons le nœud B, alors son parent sera le nœud A, et ses enfants seront les nœuds D, E et F.

Feuille

Un nœud qui n'a pas d'enfants sera appelé feuille de l'arbre. Dans l'exemple, les feuilles seront les nœuds D, E, F, G, I, J, K.

C'est la terminologie de base. D'autres concepts seront abordés plus loin. Donc, un arbre binaire est un arbre dans lequel chaque nœud aura au maximum deux enfants. Comme vous l'avez deviné, l'arbre de l'exemple ne sera pas binaire, car les nœuds B et H ont plus de deux enfants. Voici un exemple d'arbre binaire :

Les nœuds de l'arbre peuvent contenir n'importe quelle information. Un arbre binaire de recherche est un arbre binaire dont les propriétés suivantes sont caractéristiques :

1. Les deux sous-arbres - gauche et droit - sont des arbres binaires de recherche.
2. Pour tous les nœuds du sous-arbre gauche d'un nœud X donné, les valeurs des clés de données sont inférieures à la valeur de la clé de données du nœud X lui-même.
3. Pour tous les nœuds du sous-arbre droit d'un nœud X donné, les valeurs des clés de données sont supérieures ou égales à la valeur de la clé de données du nœud X lui-même.

Clé une sorte de caractéristique du nœud (par exemple, un nombre). La clé est nécessaire pour pouvoir trouver l'élément de l'arbre correspondant à cette clé. Exemple d'arbre binaire de recherche :

Représentation de l'arbre

Au fur et à mesure de l'avancement, je fournirai quelques (possiblement incomplets) extraits de code pour améliorer votre compréhension. Le code complet sera à la fin de l'article.

L'arbre est constitué de nœuds. La structure d'un nœud :

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...autres méthodes du nœud
}

Chaque nœud a deux descendants (il est tout à fait possible que les descendants leftChild et/ou rightChild contiennent la valeur null). Vous avez probablement compris que dans ce cas, le nombre data représente les données stockées dans le nœud ; key est la clé du nœud.

Une fois le nœud compris, parlons des problèmes pertinents concernant les arbres. Ici et ci-après, par le terme « arbre », je désignerai un arbre binaire de recherche. La structure de l'arbre binaire :

public class BinaryTree<T> {
     private Node<T> root;

    //méthodes de l'arbre
}

Comme champ de la classe, nous n'aurons besoin que de la racine de l'arbre, car depuis la racine, en utilisant les méthodes getLeftChild() et getRightChild(), on peut atteindre n'importe quel nœud de l'arbre.

Algorithmes dans l'arbre

La recherche

Supposons que vous ayez un arbre construit. Comment trouver un élément avec la clé key ? Il faut se déplacer progressivement de la racine vers le bas de l'arbre et comparer la valeur key avec la clé de chaque nœud : si key est inférieur à la clé du nœud courant, passez au descendant gauche du nœud ; si supérieur, allez au droit ; si les clés sont égales, le nœud recherché est trouvé ! Le code correspondant :

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

Si current devient égal à null, cela signifie que la recherche a atteint la fin de l'arbre (au niveau conceptuel, vous êtes dans un endroit inexistant de l'arbre — un descendant d'une feuille).

Considérons l'efficacité de l'algorithme de recherche dans un arbre équilibré (un arbre dans lequel les nœuds sont répartis de manière plus ou moins uniforme). Dans ce cas, l'efficacité de la recherche sera O(log(n)), avec un logarithme en base 2. Regardez : si l'arbre équilibré a n éléments, cela signifie qu'il y aura log(n) niveaux dans l'arbre. Et dans la recherche, à chaque étape de la boucle, vous descendez d'un niveau.

Insertion

Si vous avez compris l'essence de la recherche, il vous sera facile de comprendre l'insertion. Il suffit de descendre jusqu'à la feuille de l'arbre (en suivant les règles de descente décrites dans la recherche) et de devenir son descendant — à gauche ou à droite, selon la clé. Mise en œuvre :

   public void insert(T insertData, int key) {
        Node current = root;
        Node parent;
        Node newNode = new Node(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

Dans ce cas, il faut, en plus du nœud actuel, conserver des informations sur le parent du nœud actuel. Lorsque current deviendra égal à null, la variable parent contiendra la feuille dont nous avons besoin.
L'efficacité de l'insertion sera, comme pour la recherche, de O(log(n)).

Désinstallation

La suppression est l'opération la plus complexe à effectuer sur l'arbre. Évidemment, il faut d'abord trouver l'élément que nous allons supprimer. Mais ensuite ? Si l'on se contente d'assigner la valeur null à sa référence, nous perdrons l'information sur le sous-arbre dont ce nœud est la racine. Les méthodes de suppression d'un arbre sont divisées en trois cas.

Premier cas. Le nœud à supprimer n'a pas de descendants.

Si le nœud à supprimer n'a pas de descendants, cela signifie qu'il s'agit d'une feuille. On peut donc simplement assigner la valeur null aux champs leftChild ou rightChild de son parent.

Deuxième cas. Le nœud à supprimer a un descendant.

Ce cas n'est pas très compliqué non plus. Revenons à notre exemple. Supposons que nous devions supprimer l'élément avec la clé 14. Convenez que puisqu'il est le descendant droit du nœud avec la clé 10, tout descendant de ce nœud (dans ce cas, le droit) aura une clé supérieure à 10, il est donc facile de "l'émonder" de l'arbre et de relier directement le parent au descendant du nœud supprimé, c'est-à-dire de relier le nœud avec la clé 10 au nœud 13. Il en serait de même si nous devions supprimer un nœud qui est le descendant gauche de son parent. Réfléchissez bien à cela — c'est une analogie exacte.

Troisième cas. Le nœud a deux descendants.

Le cas le plus complexe. Analysons par un nouvel exemple.

Recherche du successeur.

Supposons que nous devons supprimer un nœud avec la clé 25. Qui allons-nous mettre à sa place ? Quelqu'un de ses successeurs (descendants ou descendants des descendants) doit devenir le successeur(celui qui prendra la place du nœud supprimé).

Comment déterminer qui doit devenir le successeur ? Il est intuitivement clair que c’est le nœud dans l’arbre dont la clé est la suivante par ordre croissant après celle du nœud supprimé. L’algorithme est le suivant. Il faut se rendre à son successeur droit (toujours à droite, car il a déjà été dit que la clé du successeur est supérieure à celle du nœud supprimé), puis parcourir la chaîne des successeurs gauches de ce successeur droit. Dans notre exemple, nous devons passer au nœud avec la clé 35, puis descendre jusqu'à la feuille en suivant la chaîne de ses successeurs gauches — dans ce cas, cette chaîne ne contient que le nœud avec la clé 30. Strictement parlant, nous cherchons le nœud le plus petit dans l'ensemble des nœuds supérieurs au nœud recherché.

Code de la méthode de recherche du successeur :

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode; // parent du successeur
        Node<T> successor = deleteNode; // successeur
        Node<T> current = successor.getRightChild(); // simplement un nœud "courant"
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // à la sortie de la boucle, nous avons le successeur et le parent du successeur
        if (successor != deleteNode.getRightChild()) { // si le successeur ne coïncide pas avec le successeur droit du nœud supprimé
            parentSuccessor.setLeftChild(successor.getRightChild()); // alors son parent prend le descendant du successeur pour ne pas le perdre
            successor.setRightChild(deleteNode.getRightChild()); // relions le successeur au successeur droit du nœud supprimé
        }
        return successor;
    }

Code complet de la méthode delete :

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // En fonction de savoir si le nœud à supprimer est un enfant gauche ou droit de son parent, la variable booléenne isLeftChild prendra la valeur true ou false respectivement.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) { // premier cas
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // deuxième cas
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else { // troisième cas
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

La complexité peut être approximée à O(log(n)).

Recherche du maximum/minimum dans l'arbre

Il est évident que pour trouver la valeur minimale/maximale dans l'arbre, il faut parcourir successivement la chaîne des éléments gauche/droit de l'arbre respectivement ; lorsque vous atteindrez une feuille, elle sera l'élément minimal/maximal.

    public Node getMinimum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node getMaximum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

Complexité — O(log(n))

Parcours symétrique

Le parcours consiste à visiter chaque nœud de l'arbre dans le but d'effectuer une certaine action avec lui.

L'algorithme de parcours symétrique récursif :

1. Effectuer une action avec l'enfant gauche
2. Effectuer une action avec soi-même
3. Effectuer une action avec l'enfant droit

Code :

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Vous pouvez mettre tout ce que vous voulez ici
            inOrder(current.getRightChild());
        }
    }

Conclusion

Enfin ! Si j'ai manqué d'expliquer quelque chose ou si vous avez des remarques, n'hésitez pas à les laisser en commentaire. Comme promis, voici le code complet.

Node.java:

public class Node {
    private T data;
    private int key;
    private Node leftChild;
    private Node rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node newNode) {
        rightChild = newNode;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

P.S.

Dégénération en O(n)

Beaucoup d'entre vous ont peut-être remarqué : et si nous faisions en sorte que l'arbre devienne déséquilibré ? Par exemple, en ajoutant des nœuds avec des clés croissantes : 1,2,3,4,5,6… À ce moment-là, l'arbre ressemblera à quelque chose de semblable à une liste chaînée. Et oui, l'arbre perdra sa structure arborescente, et par conséquent, son efficacité d'accès aux données. La complexité des opérations de recherche, d'insertion et de suppression deviendra similaire à celle d'une liste chaînée : O(n). C'est là qu'apparaît, selon moi, l'un des principaux inconvénients des arbres binaires.

Seuls les utilisateurs enregistrés peuvent participer au sondage. Connectez-vous, s'il vous plaît.

Je ne suis pas sur Habr depuis longtemps, et j'aimerais savoir quels sujets d'articles aimeriez-vous voir plus souvent ?

• Structures de données

• Algorithmes (DP, récursion, compression de données, etc.)

• Application des structures de données et des algorithmes dans la vie réelle

• Programmation d'applications Android en Java

• Programmation d'applications web en Java

2 utilisateurs ont voté. 1 utilisateur s'est abstenu.

Source : habr.com