O que é uma árvore binária?
Uma árvore binária é um tipo de estrutura de dados usada na programação de computadores para armazenar, classificar e acessar informações. Árvores binárias são a variedade mais simples, mas são muito úteis e fáceis de implementar. Uma implementação típica de uma árvore binária depende de um nó raiz vinculado a uma série de nós que compõem a própria árvore por variáveis de ponteiro. Esse tipo de árvore deriva seu nome do fato de que nenhum nó na árvore pode ter mais de dois filhos.
As estruturas de dados em árvore vêm em muitas variedades. Eles são compostos de nós diferentes, organizados em um padrão hierárquico. Um único nó, a raiz, é o ponto de acesso através do qual toda a árvore de dados pode ser pesquisada ou manipulada. Este nó raiz aponta para o nó superior dentro da própria árvore.
Qualquer nó dentro de uma árvore, exceto o nó superior, terá um nó pai localizado acima dele na hierarquia da árvore. Também pode ter nós filhos, localizados abaixo dele. Um determinado nó é acessado através dos que estão acima na árvore e fornece acesso aos que estão abaixo dele.
As estruturas de dados da árvore binária permitem que cada nó tenha no máximo dois filhos. Um determinado nó pode, portanto, ter zero, um ou dois nós filhos conectados a ele. As árvores binárias comuns permitem nós com qualquer número de filhos em qualquer ponto da árvore. Eles também não impõem restrições sobre como os valores armazenados nos nós que compõem uma árvore são organizados.
As estruturas de dados são mais úteis quando melhoram a velocidade com a qual os dados podem ser acessados por um computador, e versões modificadas de árvores binárias são usadas para melhorar sua eficiência. Uma árvore de pesquisa binária é aquela em que todos os valores de dados localizados na ramificação descendente esquerda de um determinado nó têm valores iguais ou inferiores ao valor armazenado nesse nó. Os valores no lado direito de um nó em uma árvore binária ordenada devem, por sua vez, ser maiores que o valor no nó base. Essa ordenação de dados permite que um algoritmo de pesquisa muito mais eficiente seja escrito.
A forma de uma árvore binária também é importante para determinar a eficiência de um algoritmo de pesquisa. A variedade menos eficiente de uma árvore binária é aquela em que cada nó tem apenas um único filho. Um computador pode precisar examinar todos os itens de dados na árvore inteira para localizar uma única informação nesta configuração. A árvore binária mais eficiente, por outro lado, é aquela em que todos os nós, exceto os que estão no fundo da árvore, têm dois filhos e onde todos os nós das folhas, os nós inferiores da árvore, estão à mesma distância da raiz.