Estruturas de dados: árvore binária em Java

Olá, olá! É difícil ser um programador forte sem conhecimentos básicos. E aqui nos referimos não apenas ao conhecimento da sintaxe da linguagem de programação nativa, mas também aos fundamentos e conceitos de programação em geral. Uma dessas bases são algoritmos e estruturas de dados. Via de regra, alguns têm mais conhecimento sobre o assunto, outros menos, mas existem algumas informações básicas que todos deveriam saber. Entre os bancos de dados para estruturas de dados, definitivamente vale a pena entender as árvores binárias de busca. Na verdade, hoje veremos a própria estrutura com seus recursos e descobriremos como você pode implementar uma árvore binária em Java . Primeiro, vamos descobrir o que é uma árvore binária. Uma árvore binária é uma estrutura de dados em que cada nó (pai) possui no máximo dois filhos (herdeiro direito e esquerdo). Na prática, dois tipos de árvores binárias são comumente usados ​​– árvore de busca binária e pirâmide (heap). Hoje veremos uma árvore de pesquisa binária.

Benefícios da árvore binária

Qual é a vantagem de armazenar dados como uma árvore de pesquisa binária? Imagine que temos um livro de referência de 100 páginas e precisamos encontrar uma página específica que contenha os dados que precisamos. Também sabemos pelo conteúdo de qual página específica precisamos. Se seguirmos o caminho habitual, teremos que virar uma página de cada vez até chegar à que necessitamos. Ou seja, percorreremos de 1 a 100 páginas até chegarmos ao lugar certo. Por exemplo, se precisarmos da página 77, teremos 77 pesquisas. Se falarmos sobre complexidade de tempo, então será O(N) . Mas isso pode ser feito de forma mais eficiente, certo? Vamos tentar fazer a mesma coisa, mas usando pesquisa binária :

1. Dividimos o diretório em duas partes, a primeira - de 1 a 50, a segunda - 51-100. Sabemos exatamente em qual destas partes a nossa página está: se pegarmos novamente a página 77, ela estará na segunda parte do livro.
2. A seguir, consideramos a segunda parte e a dividimos em duas - de 51 a 75, de 76 a 100. Nesse caso, nossa página estará novamente na segunda metade, na faixa de 76 a 100.
3. A seguir, dividimos esse intervalo por 2 e obtemos 76-88 e 89-100. A página cabe na primeira lacuna, então descartamos a segunda.
4. A seguir estão os intervalos: 76-81 e 82-88, pegue o primeiro.
5. 76-78 e 79-81, pegue o primeiro.
6. 76 e 77-78, pegue o segundo.
7. 77 e 78, pegue o primeiro e pegue nossa página - 77.

Em vez de 77 passos, precisávamos apenas de 7! A complexidade de tempo desta pesquisa será O(log(N)) .

Regras para construir uma árvore de pesquisa binária

A árvore de pesquisa binária é construída de acordo com certas regras:

• cada nó possui no máximo dois filhos;
• cada valor menor que o valor do nó torna-se o filho esquerdo ou o filho do filho esquerdo;
• todo valor maior ou igual ao valor do nó torna-se o filho certo ou o filho do filho certo.

Por exemplo, temos uma série de números de 1 a 10. Vamos ver como será a árvore de pesquisa binária para esta série: Vamos pensar se todas as condições de uma árvore binária são atendidas aqui:

• todos os nós não têm mais do que dois herdeiros, a primeira condição é atendida;
• se considerarmos, por exemplo, um nó com valor 7 (ou qualquer outro), veremos que todos os valores dos elementos da subárvore esquerda serão menores e da direita serão maiores. Isso significa que as condições 2 e 3 foram atendidas.

Vejamos como ocorrem as operações básicas - inserção, exclusão, pesquisa.

Procure um elemento

Ao procurar um elemento com um determinado valor, começamos no elemento raiz:

1. Se for igual ao valor desejado, o elemento raiz é o desejado; caso contrário, comparamos os valores da raiz e do desejado.
2. Se o elemento que procuramos for maior, passamos para o filho direito; caso contrário, passamos para o filho esquerdo.
3. Se o elemento não for encontrado, aplique as etapas 1 e 2, mas ao filho (direita ou esquerda) até que o elemento seja encontrado.

Por exemplo, na árvore de pesquisa binária mostrada acima, queremos encontrar o elemento com valor 5:

• comparamos com o elemento raiz, vemos que o elemento raiz é maior, então passamos para o filho esquerdo, que tem valor 3;
• comparamos o que procuramos e o elemento com valor 3, vemos que o que procuramos é maior, portanto precisamos do descendente direito do elemento em questão, ou seja, o elemento com valor 5;
• Comparamos este descendente com aquele que procuramos e vemos que os valores são iguais - o elemento foi encontrado.

Inserindo um elemento

O algoritmo de inserção também é muito, muito simples:

1. Comparamos o novo com o raiz (se não existir, o novo elemento é o raiz).

2. Se for um novo elemento:

   • for menor, então vamos para o herdeiro esquerdo; se não houver, o novo elemento toma o lugar do herdeiro esquerdo e o algoritmo é concluído;
   • é maior ou igual à raiz, então passamos para o herdeiro certo. E da mesma forma, se este elemento não existir, então um novo elemento tomará o lugar do elemento correto e o algoritmo será concluído.

3. Para o novo elemento em questão, que estava à direita ou à esquerda do passo anterior, repita os passos 1 e 2 até que o elemento inserido esteja no lugar.

   Como exemplo, desejaremos inserir na árvore considerada acima, um elemento com o valor 11:

   • comparamos com o elemento raiz 7 e vemos que o elemento raiz é menor, então passamos para o herdeiro direito;
   • o próximo elemento em consideração tem um valor de 9, que é menor que o novo 11, então passamos para o herdeiro certo;
   • o herdeiro certo tem valor 10, que novamente é menor, então vamos para o primeiro elemento, e como não está lá, um novo elemento com valor 11 é colocado neste local.
   ↓

Removendo um elemento

Talvez, de todas as operações com árvores de busca binária, a exclusão seja a mais difícil. Em primeiro lugar, busca-se o elemento a ser excluído, após a descoberta segue-se uma etapa, que pode ter três variações:

1. O nó a ser excluído é um nó folha (não tem filhos).

   Talvez o mais simples. Tudo se resume ao fato de simplesmente cortá-lo da árvore, sem manipulações desnecessárias. Por exemplo, da nossa árvore removemos o nó com o valor 8:

   ↓

2. O nó que está sendo excluído tem um filho.

   Nesse caso, excluímos o nó selecionado e colocamos seu descendente em seu lugar (em essência, simplesmente cortamos o nó selecionado da cadeia). Como exemplo, vamos remover um nó com valor 9 da árvore:

   ↓

3. O nó que está sendo excluído tem dois filhos.

   A parte mais interessante. Afinal, se o nó que está sendo excluído tiver dois filhos ao mesmo tempo, você não poderá simplesmente substituí-lo por um desses filhos (especialmente se o filho tiver seus próprios filhos).

   Exemplo: Na árvore acima, qual nó deve ser o filho esquerdo do nó 3?

   Se você pensar um pouco, fica óbvio que este deveria ser um nó com valor 4. Mas e se a árvore não for tão simples? Se contiver centenas de valores, será tão fácil descobrir quem será o sucessor?

   É claro que não. Portanto, precisamos de nosso próprio algoritmo de busca de pequenos receptores:

   1. Primeiramente devemos ir até o filho direito do nó selecionado, cujo valor deve ser maior que o valor do nó.
   2. Em seguida, passamos para o filho esquerdo do filho direito (se existir), depois para o filho esquerdo do filho esquerdo, etc., seguindo a cadeia de filhos esquerdos.
   3. Conseqüentemente, o último filho esquerdo neste caminho será o sucessor do nó original.

   Vamos generalizar um pouco esse pequeno algoritmo: na subárvore do filho direito do nó de origem, todos os nós são maiores que aquele que está sendo deletado, o que pode ser entendido a partir das regras básicas da árvore binária de busca. Nesta subárvore procuramos o menor valor.

   Em outras palavras, procuramos o menor nó em um conjunto de nós maior que o nó original. Este menor nó entre os maiores será o sucessor mais adequado.

   Como ficará a árvore após remover o nó com valor 3:

   ↓

Agora é hora de passar da prática à teoria. Vamos dar uma olhada em como podemos exibir essa estrutura de dados em Java. Classe de nó único:

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

Nada muito complicado: cada elemento possui um link para seu filho esquerdo e direito. E agora, talvez, a classe mais importante seja a classe árvore:

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);// подводим черту
   }
}

Novamente, nada muito complicado. As operações da árvore de pesquisa binária descritas anteriormente estão presentes, além de um método para exibir a árvore no console. Bem, agora vamos dar uma olhada na árvore em ação:

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

As operações de pesquisa/inserção/exclusão em uma árvore de pesquisa binária têm uma complexidade de tempo de O(log(N)) . Mas esse é o melhor cenário. Em geral, a complexidade de tempo das operações varia de O(log(N)) a O(N) . Depende do grau de degeneração da árvore.

O que é uma árvore degenerada?

Esta é a árvore na qual os elementos caíram quando adicionados à posição do nó mais à esquerda (menor número) ou do nó maior (maior). Isto pode acontecer se, por exemplo, toda a árvore esquerda estiver vazia em cada nível, existindo apenas árvores direitas, caso em que a árvore degenera em uma lista (indo para a direita). Sim, é assim que uma árvore degenerada se torna efetivamente uma lista encadeada individualmente, na qual cada elemento conhece apenas o próximo. Neste caso, todas as operações nesta estrutura aproximam-se da complexidade de tempo de O(N) .

Em que caso uma árvore pode degenerar?

Por exemplo, se você adicionar uma lista de elementos classificados. Se a lista estiver ordenada em ordem crescente, a raiz será a primeira, respectivamente a menor. O próximo depois dele assumirá a posição de filho certo. E o que vem depois será maior que o segundo e assumirá a posição de seu sucessor direito, e assim por diante... Se a lista estiver em ordem decrescente, acontecerá a mesma coisa, mas com os elementos mais à esquerda. Para evitar isso, depois de receber vários elementos, você pode simplesmente misturá-los. Então a classificação desaparecerá e os números ficarão mais ou menos uniformemente espalhados pela árvore. Por hoje é tudo, obrigado pela atenção!