Implementação de uma árvore de busca binária

2024 Autor: Angel Austin | [email protected]. Última modificação: 2023-12-17 05:39

Árvore de busca binária - um banco de dados estruturado contendo nós, dois links para outros nós, direito e esquerdo. Os nós são um objeto da classe que possui dados, e NULL é o sinal que marca o fim da árvore.

É muitas vezes referido como BST, que tem uma propriedade especial: os nós maiores que a raiz estão localizados à direita e os menores à esquerda.

Teoria geral e terminologia

Em uma árvore de busca binária, cada nó, excluindo a raiz, é conectado por uma aresta direcionada de um nó para outro, que é chamado de pai. Cada um deles pode ser conectado a um número arbitrário de nós, chamados filhos. Nós sem "filhos" são chamados de folhas (nós externos). Elementos que não são folhas são chamados de internos. Nós com o mesmo pai são irmãos. O nó mais alto é chamado de raiz. No BST, atribua um elemento a cada nó e certifique-se de que eles tenham uma propriedade especial definida para eles.

Terminologia de árvore:

A profundidade de um nó é o número de arestas definidas da raiz até ele.
Altura de um nó é o número de arestas definidas a partir dele até a folha mais profunda.
A altura da árvore é determinada pela altura da raiz.
Árvore de busca binária é um design especial, fornece a melhor relação entre altura e número de nós.
Altura h com N nós no máximo O (log N).

Você pode facilmente provar isso contando os nós em cada nível, começando pela raiz, assumindo que contém o maior número deles: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Resolvendo isso para h dá h=O (log n).

Benefícios da madeira:

Reflete as relações estruturais dos dados.
Usado para representar hierarquias.
Garantir uma instalação e pesquisa eficientes.
Árvores são dados muito flexíveis, permitindo que você mova subárvores com esforço mínimo.

Método de pesquisa

Em geral, para determinar se um valor está no BST, inicie uma árvore de busca binária em sua raiz e determine se ela atende aos requisitos:

estar na raiz;
estar na subárvore esquerda da raiz;
na subárvore direita da raiz.

Se nenhum registrador base for satisfeito, uma busca recursiva é realizada na subárvore correspondente. Na verdade, existem duas opções básicas:

A árvore está vazia - retorna false.
O valor está no nó raiz - retorna true.

Deve-se notar que uma árvore de busca binária com um esquema desenvolvido sempre inicia a busca ao longo do caminho da raiz até a folha. Na pior das hipóteses, vai até a folha. Portanto, o pior tempo é proporcional ao comprimento do caminho mais longo da raiz à folha, que é a altura da árvore. Em geral, é nessa hora que você precisa saber quanto tempo leva para pesquisar em função do número de valores armazenados na árvore.

Em outras palavras, existe uma relação entre o número de nós em uma BST e a altura de uma árvore, dependendo de sua "forma". Na pior das hipóteses, os nós têm apenas um filho, e uma árvore de busca binária balanceada é essencialmente uma lista encadeada. Por exemplo:

Esta árvore tem 5 nós e altura=5. Encontrar valores no intervalo 16-19 e 21-29 exigirá o seguinte caminho da raiz até a folha (o nó contendo o valor 20), ou seja,, levará um tempo proporcional ao número de nós. Na melhor das hipóteses, todos eles têm 2 filhos e as folhas estão localizadas na mesma profundidade.

Esta árvore de busca binária tem 7 nós e altura=3. Em geral, uma árvore como esta (árvore completa) terá uma altura de aproximadamente log 2 (N), onde N é o número de nós na árvore. O valor de log 2 (N) é o número de vezes (2) que N pode ser dividido antes que zero seja alcançado.

Resumindo: o pior tempo necessário para pesquisar no BST é O (altura da árvore). O pior caso de árvore "linear" é O(N), onde N é o número de nós na árvore. Na melhor das hipóteses, uma árvore "completa" é O(log N).

inserção binária BST

Quer saber onde deveria estaro novo nó está localizado no BST, você precisa entender a lógica, ele deve ser colocado onde o usuário o encontrar. Além disso, você precisa se lembrar das regras:

Duplicações não são permitidas, tentar inserir um valor duplicado lançará uma exceção.
O método de inserção público usa um método auxiliar recursivo "auxiliar" para realmente inserir.
Um nó contendo um novo valor é sempre inserido como uma folha em BST.
O método de inserção público retorna void, mas o método auxiliar retorna um BSTnode. Ele faz isso para lidar com o caso em que o nó passado para ele é nulo.

Em geral, o método auxiliar indica que se a árvore de busca binária original estiver vazia, o resultado será uma árvore com um nó. Caso contrário, o resultado será um ponteiro para o mesmo nó que foi passado como argumento.

Exclusão no algoritmo binário

Como você pode esperar, deletar um elemento envolve encontrar um nó que contém o valor a ser removido. Há várias coisas neste código:

BST usa um auxiliar, método de exclusão sobrecarregado. Se o elemento que você está procurando não estiver na árvore, o método auxiliar será eventualmente chamado com n==null. Isso não é considerado um erro, a árvore simplesmente não muda neste caso. O método auxiliar delete retorna um valor - um ponteiro para a árvore atualizada.
Quando uma folha é removida, a remoção da árvore de busca binária define o ponteiro filho correspondente de seu pai para nulo, ou a raiz para nulo se o que está sendo removido foro nó é uma raiz e não tem filhos.
Observe que a chamada de exclusão deve ser uma das seguintes: root=delete (root, key), n.setLeft (delete (n.getLeft(), key)), n.setRight (delete(n. getRight(), chave)). Assim, em todos os três casos é correto que o método delete simplesmente retorne null.
Quando a busca pelo nodo que contém o valor a ser deletado for bem sucedida, há três opções: o nodo a ser deletado é uma folha (não tem filhos), o nodo a ser deletado tem um filho, tem dois filhos.
Quando o nó que está sendo removido tem um filho, você pode simplesmente substituí-lo por um filho, retornando um ponteiro para o filho.
Se o nó a ser deletado tiver zero ou 1 filho, então o método delete irá "seguir o caminho" da raiz até aquele nodo. Portanto, o pior tempo é proporcional à altura da árvore, tanto para pesquisa quanto para inserção.

Se o nó a ser removido tiver dois filhos, os seguintes passos são executados:

Encontre o nó a ser excluído, seguindo o caminho da raiz até ele.
Encontre o menor valor de v na subárvore direita, continuando pelo caminho até a folha.
Remova recursivamente o valor de v, siga o mesmo caminho do passo 2.
Assim, na pior das hipóteses, o caminho da raiz até a folha é executado duas vezes.

Ordem dos percursos

Traversal é um processo que visita todos os nós em uma árvore. Como uma árvore de pesquisa binária C é uma estrutura de dados não linear, não há travessia exclusiva. Por exemplo, às vezes vários algoritmos de travessiaagrupados nos dois tipos a seguir:

profundidade de cruzamento;
primeira passagem.

Há apenas um tipo de cruzamento de largura - ignorando o nível. Esta travessia visita os nós de nível inferior e esquerdo, superior e direito.

Existem três tipos diferentes de cruzamentos de profundidade:

Passando na pré-venda - primeiro visite o pai e depois o filho esquerdo e direito.
Passing InOrder - visitando o filho da esquerda, depois o pai e o filho da direita.
Depois do PostOrder - visitando o filho da esquerda, depois o filho da direita, depois o pai.

Exemplo de quatro percursos de uma árvore de busca binária:

Pré-venda - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
Em Ordem - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
Pós-pedido - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

A figura mostra a ordem em que os nós são visitados. O número 1 é o primeiro nó em uma travessia específica e 7 é o último nó.

Esses percursos gerais podem ser representados como um único algoritmo, assumindo que cada nó é visitado três vezes. O tour de Euler é um passeio em torno de uma árvore binária onde cada aresta é tratada como uma parede que o usuário não pode atravessar. Nesta caminhada, cada nó será visitado à esquerda, abaixo ou à direita. O tour de Euler, que visita os nós à esquerda, faz com que a preposição seja ignorada. Quando os nós abaixo são visitados, eles são percorridos em ordem. E quando os nós à direita são visitados - obtenhabypass passo a passo.

Navegação e Depuração

Para facilitar a navegação na árvore, crie funções que primeiro verifiquem se são o filho da esquerda ou da direita. Para alterar a posição de um nó, deve haver fácil acesso ao ponteiro no nó pai. Implementar corretamente uma árvore é muito difícil, então você precisa conhecer e aplicar processos de depuração. Uma árvore de busca binária com uma implementação geralmente tem ponteiros que não indicam a direção do percurso.

Para descobrir tudo isso, é usada uma função que verifica se a árvore pode estar correta e ajuda a encontrar muitos erros. Por exemplo, ele verifica se o nó pai é um nó filho. Com assert(is_wellformed(root)) muitos erros podem ser detectados prematuramente. Usando alguns pontos de interrupção fornecidos nesta função, você também pode determinar exatamente qual ponteiro está errado.

Função Konsolenausgabe

Esta função libera toda a árvore para o console e, portanto, é muito útil. A ordem em que a meta de saída da árvore é executada é:

Para fazer isso, primeiro você precisa determinar quais informações serão enviadas pelo nó.
E você também precisa saber a largura e a altura da árvore para contabilizar quanto espaço deixar.
As funções a seguir calculam esta informação para a árvore e cada subárvore. Como você só pode escrever no console linha por linha, você também precisará imprimir a árvore linha por linha.
Agora precisamos de outra maneira de retirartoda a árvore, não apenas linha por linha.
Com a ajuda da função dump, você pode ler a árvore e melhorar significativamente o algoritmo de saída, no que diz respeito à velocidade.

No entanto, esta função será difícil de usar em árvores grandes.

Copiar construtor e destruidor

Como uma árvore não é uma estrutura de dados trivial, é melhor implementar um construtor de cópia, um destruidor e um operador de atribuição. O destruidor é fácil de implementar recursivamente. Para árvores muito grandes, ele pode lidar com "estouro de heap". Neste caso, é formulado iterativamente. A ideia é retirar a folha que representa o menor valor de todas as folhas, para que fique do lado esquerdo da árvore. Cortar as primeiras folhas cria novas, e a árvore encolhe até finalmente deixar de existir.

O construtor de cópia também pode ser implementado recursivamente, mas tenha cuidado se uma exceção for lançada. Caso contrário, a árvore rapidamente se torna confusa e propensa a erros. É por isso que a versão iterativa é preferida. A ideia é passar pela árvore antiga e pela nova árvore, como você faria no destruidor, clonando todos os nós que estão na árvore antiga, mas não os novos.

Com este método, a implementação da árvore de busca binária está sempre em um estado saudável e pode ser removida pelo destruidor mesmo em um estado incompleto. Se ocorrer uma exceção, tudo o que você precisa fazer é instruir o destruidor a excluir a árvore semiacabada. operador de atribuiçãopode ser facilmente implementado usando Copy & Swap.

Criando uma árvore de busca binária

Árvores de busca binária ideais são incrivelmente eficientes se gerenciadas corretamente. Algumas regras para árvores de busca binária:

Um nó pai tem no máximo 2 nós filhos.
O nó filho esquerdo é sempre menor que o nó pai.
Um nó filho válido é sempre maior ou igual ao nó pai.

O array que será usado para construir a árvore de busca binária:

Um array inteiro base de sete valores em ordem não classificada.
O primeiro valor no array é 10, então o primeiro passo na construção da árvore é criar um nó raiz de 10, como mostrado aqui.
Com um conjunto de nós raiz, todos os outros valores serão filhos deste nó. Referindo-se às regras, o primeiro passo a ser dado para adicionar 7 à árvore é compará-lo com o nó raiz.
Se o valor 7 for menor que 10, ele se tornará o nó filho esquerdo.
Se o valor 7 for maior ou igual a 10, ele se moverá para a direita. Como se sabe que 7 é menor que 10, ele é designado como o nó filho esquerdo.
Realize comparações recursivamente para cada elemento.
Seguindo o mesmo padrão, faça a mesma comparação com o 14º valor do array.
Comparando o valor 14 com o nó raiz 10, sabendo que 14 é o filho correto.
Andando pelo array,venha para 20.
Comece comparando o array com 10, o que for maior. Então vá para a direita e compare com 14, ele tem mais de 14 anos e não tem filhos à direita.
Agora existe um valor de 1. Seguindo o mesmo padrão dos outros valores, compare 1 com 10, movendo para a esquerda e comparando com 7 e finalmente com o 1 filho esquerdo do 7º nó.
Se o valor for 5, compare com 10. Como 5 é menor que 10, passe para a esquerda e compare com 7.
Sabendo que 5 é menor que 7, continue descendo a árvore e compare 5 com 1 valor.
Se 1 não tiver filhos e 5 for maior que 1, então 5 é um filho válido de 1 nó.
Finalmente insira o valor 8 na árvore.
Quando 8 for menor que 10, mova-o para a esquerda e compare com 7, 8 é maior que 7, então mova-o para a direita e complete a árvore, tornando 8 um filho próprio de 7.

Obtendo e avaliando a elegância simples de árvores de busca binária ótimas. Como muitos tópicos em programação, o poder das árvores de busca binária vem de sua capacidade de resolver dados em pequenos componentes relacionados. A partir de agora, você pode trabalhar com todo o conjunto de dados de forma organizada.

Potenciais problemas de pesquisa binária

Árvores de busca binária são ótimas, mas há algumas ressalvas a serem lembradas. Eles geralmente só são eficazes se forem equilibrados. Uma árvore equilibrada é uma árvore na quala diferença entre as alturas das subárvores de qualquer nó na árvore é no máximo um. Vejamos um exemplo que pode ajudar a esclarecer as regras. Vamos imaginar que o array comece como classificável.

Se você tentar executar um algoritmo de árvore de busca binária nesta árvore, ele funcionará exatamente como se estivesse apenas iterando pelo array até que o valor desejado seja encontrado. O poder da pesquisa binária está na capacidade de filtrar rapidamente valores indesejados. Quando uma árvore não está balanceada, ela não fornecerá os mesmos benefícios que uma árvore balanceada.

É muito importante examinar os dados com os quais o usuário está trabalhando ao criar uma árvore de busca binária. Você pode integrar rotinas como a randomização de arrays antes de implementar uma árvore de busca binária para inteiros para balancear.

Exemplos de cálculo de pesquisa binária

Precisamos determinar que tipo de árvore resultará se 25 for inserido na seguinte árvore de busca binária:

5 15

/ /

2 12 20

Ao inserir x em uma árvore T que ainda não contém x, a chave x é sempre colocada em uma nova folha. Em conexão com isso, a nova árvore terá a seguinte aparência:

5 15

/ /

2 12 20

Que tipo de árvore você obteria se inserisse 7 na seguinte árvore de busca binária?

5 15

/ /

2 12 20

Resposta:

5 15

/ / /

2 7 12 20

Uma árvore de busca binária pode ser usada para armazenar qualquer objeto. A vantagem de usar uma árvore de busca binária em vez de uma lista encadeada é que, se a árvore for razoavelmente balanceada e mais parecida com uma árvore "completa" do que "linear", as operações de inserção, pesquisa e exclusão podem ser implementadas para executar em O(log N) tempo.