Guia para iniciantes em árvores binárias
Se você fez um curso de estruturas de dados em seu diploma de ciência da computação, ou é um programador autodidata, é provável que você tenha encontrado o termo “Árvores Binárias”. Embora possam parecer um pouco opressores e complexos, o conceito de uma árvore binária é bastante simples.
Continue lendo enquanto dissecamos árvores binárias e por que elas são um conceito central necessário para os programadores.
O que são árvores binárias?
As árvores binárias estão entre uma das primeiras estruturas de dados que os alunos aprendem em um curso de estruturas de dados. Uma árvore binária é feita de muitos nós, e cada nó da árvore binária contém dois ponteiros que indicam os nós de dados filhos esquerdo e direito.
O primeiro nó em uma árvore binária é chamado de “raiz”. Os nós do último nível em uma árvore são chamados de folhas.
Cada nó contém um item de dados e dois ponteiros de nó. Uma árvore binária vazia é representada por um ponteiro nulo. Como você já deve ter percebido, as árvores binárias só podem ter dois filhos (daí o nome).
Tipos de estruturas de árvore binárias
Existem várias estruturas de árvore binárias diferentes, dependendo da maneira como os nós são posicionados. Uma árvore binária é chamada de árvore binária completa quando cada nó da árvore tem zero ou dois filhos. Em uma árvore binária perfeita, todos os nós têm dois filhos e as folhas estão todas na mesma profundidade.
Uma árvore binária completa possui nós preenchidos em todos os níveis, com exceção do último nível. Em árvores binárias completas, os nós estão concentrados no lado esquerdo da raiz. Outra estrutura comum é uma árvore binária balanceada; nesta estrutura, as alturas das subárvores direita e esquerda devem diferir no máximo em um. Também é necessário que as subárvores esquerda e direita também sejam equilibradas.
É importante notar que a altura da árvore binária balanceada é O (logn), onde n é o número de nós na árvore.
Em alguns casos, se cada nó tiver apenas um filho esquerdo ou direito, a árvore binária pode se tornar uma árvore binária inclinada. Ela então se comportará como uma lista vinculada; essas árvores também são chamadas de árvore degenerada.
O que são árvores de pesquisa binárias?
Uma árvore de pesquisa binária (BST) é essencialmente uma árvore binária ordenada com uma propriedade especial conhecida como propriedade "árvore de pesquisa binária". A propriedade BST significa que os nós com um valor-chave menor que a raiz são colocados na subárvore esquerda e os nós com um valor-chave maior que a raiz fazem parte da subárvore direita.
A propriedade BST deve ser verdadeira para cada nó pai subsequente na árvore.
Árvores binárias de pesquisa oferecem inserção e pesquisa rápidas. As operações de inserção, exclusão e pesquisa têm uma complexidade de tempo de pior caso de O (n), que é semelhante a uma lista encadeada.
Benefícios das árvores binárias
As árvores binárias oferecem muitos benefícios, por isso continuam sendo uma estrutura de dados muito útil. Eles podem ser usados para mostrar os relacionamentos e hierarquias estruturais em um conjunto de dados. Mais importante, as árvores binárias permitem uma pesquisa, exclusão e inserção eficientes.
Também é muito fácil implementar e manter uma árvore binária. Uma árvore binária oferece aos programadores os benefícios de uma matriz ordenada e uma lista vinculada; pesquisar em uma árvore binária é tão rápido quanto em uma matriz classificada e as operações de inserção ou exclusão são tão eficientes quanto em listas vinculadas.
Árvores binárias são estruturas de dados importantes
Árvores binárias são uma estrutura de dados muito importante e é crucial que os programadores se sintam confortáveis em aplicá-las em seus programas. Freqüentemente, os entrevistadores perguntam problemas simples de árvore binária, como travessias, profundidade máxima, espelhamento, etc.
É altamente recomendável compreender o conceito de árvore binária e estar familiarizado com os problemas típicos de entrevista.
