Strutture dati: albero binario in Java

Ciao Ciao! È difficile essere un bravo programmatore senza conoscenze di base. E qui intendiamo non solo la conoscenza della sintassi del linguaggio di programmazione nativo, ma anche i fondamenti e i concetti della programmazione in generale. Uno di questi fondamenti sono gli algoritmi e le strutture dati. Di norma, alcuni sono più informati su questo argomento, altri meno, ma ci sono alcune informazioni di base che tutti dovrebbero conoscere. Tra i database per strutture dati vale sicuramente la pena comprendere gli alberi di ricerca binari. In realtà oggi esamineremo la struttura stessa con le sue caratteristiche e scopriremo come implementare un albero binario in Java . Per prima cosa, scopriamo cos'è un albero binario. Un albero binario è una struttura dati in cui ciascun nodo (genitore) ha al massimo due figli (erede destro e sinistro). In pratica, vengono comunemente utilizzati due tipi di alberi binari: albero di ricerca binario e piramide (heap). Oggi esamineremo un albero di ricerca binario.

Vantaggi dell'albero binario

Qual è il vantaggio di archiviare i dati come albero di ricerca binario? Immagina di avere un libro di consultazione di 100 pagine e di dover trovare una pagina specifica che contenga i dati di cui abbiamo bisogno. Sappiamo anche dal contenuto di quale pagina specifica abbiamo bisogno. Se seguiamo il percorso abituale, dovremo girare una pagina alla volta fino ad arrivare a quella che ci occorre. Cioè, percorreremo da 1 a 100 pagine finché non ci troveremo nel posto giusto. Ad esempio, se abbiamo bisogno della pagina 77, avremo 77 ricerche. Se parliamo di complessità temporale, allora sarà O(N) . Ma questo può essere fatto in modo più efficiente, giusto? Proviamo a fare la stessa cosa, ma utilizzando la ricerca binaria :

1. Dividiamo la directory in due parti, la prima - da 1 a 50, la seconda - 51-100. Sappiamo esattamente in quale di queste parti si trova la nostra pagina: se prendiamo di nuovo la pagina 77, è nella seconda parte del libro.
2. Successivamente, consideriamo la seconda parte e la dividiamo in due: da 51 a 75, da 76 a 100. In questo caso, la nostra pagina sarà di nuovo nella seconda metà, nell'intervallo 76-100.
3. Successivamente, dividiamo questo intervallo per 2 e otteniamo 76-88 e 89-100. La pagina si inserisce nel primo spazio, quindi scartiamo il secondo.
4. Poi ci sono gli intervalli: 76-81 e 82-88, prendi il primo.
5. 76-78 e 79-81, prendi il primo.
6. 76 e 77-78, prendi il secondo.
7. 77 e 78, prendi il primo e prendi la nostra pagina - 77.

Invece di 77 passi, ne bastavano 7! La complessità temporale di questa ricerca sarà O(log(N)) .

Regole per costruire un albero di ricerca binario

L'albero binario di ricerca è costruito secondo alcune regole:

• ogni nodo ha al massimo due figli;
• ogni valore inferiore al valore del nodo diventa il figlio sinistro o il figlio del figlio sinistro;
• ogni valore maggiore o uguale al valore del nodo diventa il figlio destro o il figlio del figlio destro.

Ad esempio, abbiamo una serie di numeri da 1 a 10. Vediamo come apparirà l'albero di ricerca binario per questa serie: pensiamo se tutte le condizioni di un albero binario sono soddisfatte qui:

• tutti i nodi non hanno più di due eredi, la prima condizione è soddisfatta;
• se consideriamo, ad esempio, un nodo con il valore 7 (o qualsiasi altro), vedremo che tutti i valori degli elementi nel sottoalbero di sinistra saranno inferiori e in quello di destra saranno maggiori. Ciò significa che le condizioni 2 e 3 sono soddisfatte.

Diamo un'occhiata a come avvengono le operazioni di base: inserimento, cancellazione, ricerca.

Cerca un elemento

Quando cerchiamo un elemento con un dato valore, partiamo dall'elemento radice:

1. Se è uguale al valore cercato l'elemento radice è quello cercato; in caso contrario confrontiamo i valori della radice e di quello cercato.
2. Se l'elemento che stiamo cercando è più grande, ci spostiamo sul figlio di destra; in caso contrario, ci spostiamo sul figlio di sinistra.
3. Se l'elemento non viene trovato, applicare i passaggi 1 e 2, ma al figlio (destro o sinistro) finché l'elemento non viene trovato.

Ad esempio, nell'albero di ricerca binario mostrato sopra, vogliamo trovare l'elemento con il valore 5:

• lo confrontiamo con l'elemento radice, vediamo che l'elemento radice è più grande, quindi ci spostiamo sul figlio di sinistra, che ha valore 3;
• confrontiamo quello che cerchiamo e l'elemento con valore 3, vediamo che quello che cerchiamo è più grande, quindi ci serve il discendente destro dell'elemento in questione, cioè l'elemento con valore 5;
• Confrontiamo questo discendente con quello che stiamo cercando e vediamo che i valori sono uguali: l'elemento è trovato.

Inserimento di un elemento

Anche l'algoritmo di inserimento è molto, molto semplice:

1. Confrontiamo quello nuovo con quello radice (se non esiste, il nuovo elemento è quello radice).

2. Se un nuovo elemento:

   • è minore, allora si passa all'erede di sinistra; se non ce n'è, il nuovo elemento prende il posto dell'erede di sinistra, e l'algoritmo è completato;
   • è maggiore o uguale alla radice, allora passiamo all'erede giusto. E allo stesso modo, se questo elemento non esiste, allora un nuovo elemento prenderà il posto dell'elemento giusto e l'algoritmo sarà completato.

3. Per il nuovo elemento in questione, che era a destra o a sinistra rispetto al passaggio precedente, ripetere i passaggi 1 e 2 finché l'elemento inserito non è al suo posto.

   Ad esempio, vorremo inserire nell'albero considerato sopra, un elemento con valore 11:

   • confrontiamo con l'elemento radice 7 e vediamo che l'elemento radice è più piccolo, quindi passiamo all'erede giusto;
   • il successivo elemento in esame ha valore 9, che è inferiore al nuovo 11, quindi passiamo al giusto erede;
   • l'erede legittimo ha un valore di 10, che è ancora inferiore, quindi andiamo al primo elemento e poiché non è presente, in questo posto viene inserito un nuovo elemento con un valore di 11.
   ↓

Rimozione di un elemento

Forse, tra tutte le operazioni con alberi di ricerca binari, la cancellazione è la più difficile. Innanzitutto si procede alla ricerca dell'elemento da eliminare, dopo aver individuato il quale segue una fase, che può avere tre varianti:

1. Il nodo da eliminare è un nodo foglia (non ha figli).

   Forse il più semplice. Tutto si riduce al fatto che lo tagliamo semplicemente dall'albero, senza manipolazioni inutili. Ad esempio, dal nostro albero rimuoviamo il nodo con il valore 8:

   ↓

2. Il nodo da eliminare ha un figlio.

   In questo caso eliminiamo il nodo selezionato e al suo posto mettiamo il suo discendente (in sostanza tagliamo semplicemente il nodo selezionato dalla catena). Ad esempio, rimuoviamo un nodo con valore 9 dall'albero:

   ↓

3. Il nodo da eliminare ha due figli.

   La parte più interessante. Dopotutto, se il nodo da eliminare ha due figli contemporaneamente, non è possibile sostituirlo semplicemente con uno di questi figli (specialmente se il figlio ha i propri figli).

   Esempio: nell'albero sopra, quale nodo dovrebbe essere il figlio sinistro del nodo 3?

   Se ci pensate un po', diventa ovvio che questo dovrebbe essere un nodo con un valore pari a 4. Ma cosa succede se l'albero non è così semplice? Se contiene centinaia di valori, sarà così facile capire chi sarà il successore?

   È chiaro che no. Pertanto, abbiamo bisogno del nostro piccolo algoritmo di ricerca del ricevitore:

   1. Per prima cosa dobbiamo andare sul figlio destro del nodo selezionato, il cui valore deve essere maggiore del valore del nodo.
   2. Poi andiamo al figlio sinistro del bambino destro (se ne esiste uno), poi al figlio sinistro del bambino sinistro, ecc., seguendo la catena dei figli sinistro.
   3. Di conseguenza, l'ultimo figlio rimasto su questo percorso sarà il successore del nodo originale.

   Generalizziamo un po' questo piccolo algoritmo: nel sottoalbero del figlio destro del nodo sorgente, tutti i nodi sono più grandi di quello da eliminare, il che può essere compreso dalle regole di base dell'albero binario di ricerca. In questo sottoalbero cerchiamo il valore più piccolo.

   In altre parole, stiamo cercando il nodo più piccolo in un insieme di nodi più grandi del nodo originale. Questo nodo più piccolo tra quelli più grandi sarà il successore più adatto.

   Come apparirà l'albero dopo aver rimosso il nodo con valore 3:

   ↓

Ora è il momento di passare dalla pratica alla teoria. Diamo un'occhiata a come possiamo mappare questa struttura dati in Java. Classe a nodo singolo:

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 +
               '}';
   }
}

Niente di troppo complicato: ogni elemento ha un collegamento al figlio sinistro e destro. E ora, forse, la classe più importante è 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);// подводим черту
   }
}

Ancora una volta, niente di troppo complicato. Sono presenti le operazioni sull'albero di ricerca binaria descritte in precedenza, oltre a un metodo per visualizzare l'albero nella console. Bene, ora diamo un'occhiata all'albero in azione:

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

Le operazioni di ricerca/inserimento/eliminazione in un albero di ricerca binario hanno una complessità temporale di O(log(N)) . Ma questo è lo scenario migliore. In generale, la complessità temporale delle operazioni varia da O(log(N)) a O(N) . Dipende dal grado di degenerazione dell'albero.

Cos'è un albero degenere?

Questo è l'albero in cui cadono gli elementi quando vengono aggiunti alla posizione del nodo più a sinistra (numero più piccolo) o del nodo più grande (più grande). Questo può accadere se, ad esempio, l'intero albero di sinistra è vuoto ad ogni livello, ci sono solo alberi di destra, nel qual caso l'albero degenera in una lista (andando a destra). Sì, è così che un albero degenere diventa effettivamente una lista concatenata singolarmente, in cui ogni elemento conosce solo quello accanto. In questo caso, tutte le operazioni su questa struttura si avvicinano alla complessità temporale di O(N) .

In quale caso un albero può degenerare?

Ad esempio, se aggiungi un elenco di elementi ordinati. Se l'elenco è ordinato in ordine crescente, la radice sarà rispettivamente la prima e la più piccola. Il prossimo dopo di lui prenderà la posizione del bambino giusto. E quello che segue sarà più grande del secondo e prenderà la posizione del suo successore destro, e così via... Se l'elenco è in ordine decrescente, accadrà la stessa cosa, ma con gli elementi più a sinistra. Per evitare ciò, dopo aver ricevuto un numero di elementi, puoi semplicemente mescolarli. Quindi l'ordinamento scomparirà e i numeri saranno sparsi più o meno uniformemente in tutto l'albero. Per oggi è tutto, grazie per l'attenzione!