Structures de données : arbre binaire en Java

Salut Salut ! Il est difficile d'être un bon programmeur sans connaissances de base. Et nous entendons ici non seulement la connaissance de la syntaxe du langage de programmation natif, mais également les principes fondamentaux et les concepts de programmation en général. L’un de ces fondements réside dans les algorithmes et les structures de données. En règle générale, certains sont plus informés sur cette question, d'autres moins, mais il existe certaines informations de base que tout le monde devrait connaître. Parmi les bases de données sur les structures de données, il vaut vraiment la peine de comprendre les arbres de recherche binaires. En fait, aujourd'hui, nous examinerons la structure elle-même avec ses fonctionnalités et découvrirons comment implémenter un arbre binaire en Java . Voyons d’abord ce qu’est un arbre binaire. Un arbre binaire est une structure de données dans laquelle chaque nœud (parent) a au plus deux enfants (héritier droit et gauche). En pratique, deux types d'arbres binaires sont couramment utilisés : l'arbre de recherche binaire et la pyramide (tas). Aujourd'hui, nous allons examiner un arbre de recherche binaire.

Avantages de l'arbre binaire

Quel est l’avantage de stocker les données sous forme d’arbre de recherche binaire ? Imaginez que nous ayons un ouvrage de référence de 100 pages et que nous devions trouver une page spécifique qui contiendra les données dont nous avons besoin. Grâce au contenu, nous savons également de quelle page spécifique nous avons besoin. Si nous suivons le chemin habituel, nous devrons tourner une page à la fois jusqu'à arriver à celle dont nous avons besoin. Autrement dit, nous parcourrons de 1 à 100 pages jusqu'à ce que nous nous trouvions au bon endroit. Par exemple, si nous avons besoin de la page 77, nous aurons alors 77 recherches. Si nous parlons de complexité temporelle, alors ce sera O(N) . Mais cela peut être fait plus efficacement, n’est-ce pas ? Essayons de faire la même chose, mais en utilisant la recherche binaire :

1. Nous divisons le répertoire en deux parties, la première - de 1 à 50, la seconde - 51-100. Nous savons exactement dans quelle partie de ces parties se trouve notre page : si nous reprenons la page 77, elle se trouve dans la deuxième partie du livre.
2. Ensuite, nous considérons la deuxième partie et la divisons en deux - de 51 à 75, de 76 à 100. Dans ce cas, notre page sera à nouveau dans la seconde moitié, entre 76 et 100.
3. Ensuite, nous divisons cet intervalle par 2 et obtenons 76-88 et 89-100. La page s'insère dans le premier espace, nous supprimons donc le second.
4. Viennent ensuite les intervalles : 76-81 et 82-88, prenez le premier.
5. 76-78 et 79-81, prenez le premier.
6. 76 et 77-78, prenez le deuxième.
7. 77 et 78, prenez le premier et récupérez notre page - 77.

Au lieu de 77 marches, il nous en fallait seulement 7 ! La complexité temporelle de cette recherche sera O(log(N)) .

Règles de construction d'un arbre de recherche binaire

L'arbre de recherche binaire est construit selon certaines règles :

• chaque nœud a au plus deux enfants ;
• chaque valeur inférieure à la valeur du nœud devient l'enfant de gauche ou l'enfant de l'enfant de gauche ;
• chaque valeur supérieure ou égale à la valeur du nœud devient le bon enfant ou l'enfant du bon enfant.

Par exemple, nous avons une série de nombres de 1 à 10. Voyons à quoi ressemblera l'arbre de recherche binaire pour cette série : Voyons si toutes les conditions d'un arbre binaire sont remplies ici :

• tous les nœuds n'ont pas plus de deux héritiers, la première condition est remplie ;
• si l'on considère, par exemple, un nœud avec la valeur 7 (ou toute autre), nous verrons que toutes les valeurs des éléments dans le sous-arbre de gauche seront inférieures et dans celui de droite - plus. Cela signifie que les conditions 2 et 3 sont remplies.

Regardons comment se déroulent les opérations de base - insertion, suppression, recherche.

Rechercher un élément

Lors de la recherche d'un élément avec une valeur donnée, on part de l'élément racine :

1. S'il est égal à la valeur recherchée, l'élément racine est celui recherché ; sinon, on compare les valeurs de la racine et de l'élément recherché.
2. Si l’élément recherché est plus grand, on se déplace vers l’enfant de droite ; sinon, on se déplace vers l’enfant de gauche.
3. Si l'élément n'est pas trouvé, appliquez les étapes 1 et 2, mais à l'enfant (droite ou gauche) jusqu'à ce que l'élément soit trouvé.

Par exemple, dans l’arbre de recherche binaire présenté ci-dessus, nous souhaitons trouver l’élément ayant la valeur 5 :

• on le compare avec l'élément racine, on voit que l'élément racine est plus grand, donc on se déplace vers l'enfant de gauche, qui a une valeur de 3 ;
• on compare celui que l'on recherche et l'élément de valeur 3, on voit que celui que l'on recherche est plus grand, il faut donc le bon descendant de l'élément en question, à savoir l'élément de valeur 5 ;
• Nous comparons ce descendant avec celui que nous recherchons et voyons que les valeurs sont égales - l'élément est trouvé.

Insérer un élément

L'algorithme d'insertion est également très, très simple :

1. On compare le nouvel élément avec celui racine (s'il n'existe pas, le nouvel élément est celui racine).

2. Si un nouvel élément :

   • est inférieur, alors on passe à l'héritier gauche, s'il n'y en a pas, le nouvel élément prend la place de l'héritier gauche, et l'algorithme est complété ;
   • est supérieur ou égal à la racine, alors on passe à l'héritier droit. Et de même, si cet élément n’existe pas, alors un nouvel élément prendra la place du bon élément et l’algorithme sera complété.

3. Pour le nouvel élément en question, qui se trouvait à droite ou à gauche de l'étape précédente, répétez les étapes 1 et 2 jusqu'à ce que l'élément inséré soit en place.

   A titre d'exemple, nous voudrons insérer dans l'arbre considéré ci-dessus, un élément de valeur 11 :

   • nous comparons avec l'élément racine 7 et voyons que l'élément racine est plus petit, nous passons donc à l'héritier droit ;
   • l'élément suivant considéré a une valeur de 9, ce qui est inférieur au nouveau 11, nous passons donc à l'héritier de droite ;
   • l'héritier droit a une valeur de 10, ce qui est encore moins, on passe donc au premier élément, et comme il n'est pas là, un nouvel élément de valeur 11 est placé à cet endroit.
   ↓

Supprimer un élément

Peut-être que de toutes les opérations avec des arbres de recherche binaires, la suppression est la plus difficile. Tout d'abord, il y a une recherche de l'élément à supprimer, après quoi suit une étape qui peut avoir trois variantes :

1. Le nœud à supprimer est un nœud feuille (n'a pas d'enfant).

   Peut-être le plus simple. Tout se résume au fait que nous le coupons simplement de l'arbre, sans manipulation inutile. Par exemple, de notre arbre nous supprimons le nœud avec la valeur 8 :

   ↓

2. Le nœud en cours de suppression a un enfant.

   Dans ce cas, nous supprimons le nœud sélectionné et mettons son descendant à sa place (en substance, nous coupons simplement le nœud sélectionné de la chaîne). À titre d'exemple, supprimons un nœud de valeur 9 de l'arborescence :

   ↓

3. Le nœud en cours de suppression a deux enfants.

   La partie la plus intéressante. Après tout, si le nœud supprimé a deux enfants à la fois, vous ne pouvez pas simplement le remplacer par l'un de ces enfants (surtout si l'enfant a ses propres enfants).

   Exemple : dans l'arborescence ci-dessus, quel nœud doit être l'enfant gauche du nœud 3 ?

   Si vous y réfléchissez un peu, il devient évident qu'il doit s'agir d'un nœud de valeur 4. Mais que se passe-t-il si l'arbre n'est pas si simple ? S’il détient des centaines de valeurs, sera-t-il aussi simple de déterminer qui sera le successeur ?

   Il est clair que non. Par conséquent, nous avons besoin de notre propre algorithme de recherche de petits récepteurs :

   1. Il faut d’abord aller au bon enfant du nœud sélectionné, dont la valeur doit être supérieure à la valeur du nœud.
   2. Ensuite, nous nous déplaçons vers l'enfant gauche de l'enfant droit (s'il en existe un), puis vers l'enfant gauche de l'enfant gauche, etc., en suivant la chaîne des enfants gauche.
   3. En conséquence, le dernier enfant restant sur ce chemin sera le successeur du nœud d'origine.

   Généralisons un peu ce petit algorithme : dans le sous-arbre du fils droit du nœud source, tous les nœuds sont plus grands que celui en cours de suppression, ce qui peut être compris à partir des règles de base de l'arbre de recherche binaire. Dans ce sous-arbre, nous recherchons la plus petite valeur.

   En d’autres termes, nous recherchons le plus petit nœud dans un ensemble de nœuds plus grand que le nœud d’origine. Ce plus petit nœud parmi les plus grands sera le successeur le plus approprié.

   À quoi ressemblera l'arborescence après la suppression du nœud de valeur 3 :

   ↓

Il est désormais temps de passer de la pratique à la théorie. Voyons comment cartographier cette structure de données en Java. Classe de nœud unique :

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет meaning :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Rien de bien compliqué : chaque élément a un lien vers ses enfants gauche et droit. Et maintenant, la classe la plus importante est peut-être la classe tree :

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент or не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // or движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим meaningм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём How текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное meaning расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его meaning в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Encore une fois, rien de bien compliqué. Les opérations d'arbre de recherche binaire décrites précédemment sont présentes, ainsi qu'une méthode d'affichage de l'arborescence dans la console. Eh bien, regardons maintenant l'arbre en action :

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Les opérations de recherche/insertion/suppression dans un arbre de recherche binaire ont une complexité temporelle de O(log(N)) . Mais c’est le meilleur des cas. En général, la complexité temporelle des opérations varie de O(log(N)) à O(N) . Cela dépend du degré de dégénérescence de l'arbre.

Qu'est-ce qu'un arbre dégénéré ?

Il s'agit de l'arbre dans lequel les éléments sont tombés lorsqu'ils ont été ajoutés à la position du nœud le plus à gauche (le plus petit nombre) ou du nœud le plus grand (le plus grand). Cela peut arriver si, par exemple, tout l'arbre de gauche est vide à chaque niveau, il n'y a que des arbres de droite, auquel cas l'arbre dégénère en liste (allant vers la droite). Oui, c'est ainsi qu'un arbre dégénéré devient effectivement une liste à chaînage unique, dans laquelle chaque élément ne connaît que celui qui lui est voisin. Dans ce cas, toutes les opérations sur cette structure approchent la complexité temporelle de O(N) .

Dans quel cas un arbre peut-il dégénérer ?

Par exemple, si vous ajoutez une liste d'éléments triés. Si la liste est triée par ordre croissant, alors la racine sera la première, respectivement la plus petite. Le prochain après lui prendra la position du bon enfant. Et celui qui vient après sera plus grand que le second et prendra la position de son successeur droit, et ainsi de suite... Si la liste est par ordre décroissant, alors la même chose se produira, mais avec les éléments les plus à gauche. Pour éviter cela, après avoir reçu un certain nombre d'éléments, vous pouvez simplement les mélanger. Ensuite, le tri disparaîtra et les nombres seront répartis plus ou moins uniformément dans tout l'arbre. C'est tout pour aujourd'hui, merci de votre attention !