Árvore Binária na Estrutura de Dados: Propriedades, Tipos, Representação e Benefícios

Entre os diferentes tipos de estruturas de dados estão as árvores binárias que vêm com mais usos do que a maioria dos outros tipos. Suas aplicações mais notáveis ​​incluem programação ponto a ponto, pesquisa, criptografia, roteadores de rede com maior largura de banda do que outros e videogames 3D. Vamos agora discutir em detalhes o que são árvores binárias na ciência de dados, quais são seus tipos e como elas são representadas.

O que são árvores binárias?

Se você já trabalhou em árvores normais antes ou mesmo conhece seus fundamentos, saberá que não há restrições quando se trata do número de filhos que diferentes nós podem ter nessas árvores. As árvores binárias são um pouco diferentes nesse sentido. Cada pai ou nó em árvores binárias pode ter no máximo apenas dois filhos.

Todos os nós em uma árvore binária têm três componentes primários –

• um elemento de dados
• uma referência certa
• uma referência à esquerda

O nó que está no topo da árvore é chamado de nó raiz. Nós pais são aqueles que têm filhos. Os nós filhos e os nós pais são conectados uns aos outros por meio de referências. Os nós que não têm filhos são chamados de nós folha.

É claramente evidente que os nós em árvores binárias podem ter um filho, dois filhos ou nenhum filho. Árvores binárias não são estruturas de dados lineares como filas, arrays, pilhas e listas vinculadas. Em vez disso, são estruturas de dados hierárquicas.

Confira: Ideias de projetos de ciência de dados para iniciantes

Propriedades importantes de nós em árvores binárias

Uma melhor compreensão dessas propriedades o ajudará a aproveitar ao máximo esta discussão sobre árvores binárias. A profundidade de nós diferentes é definida como o número de nós que existem no caminho que conecta a raiz a um nó específico. É por isso que a profundidade do nó raiz é 0. Por outro lado, a altura de diferentes nós em uma árvore binária é o número de nós que se encontram no caminho que conecta um nó particular com o nó raiz. É por isso que a altura dos nós folha é 0.

Como você pode ver claramente, a profundidade de um nó é medida a partir do nó raiz e depois descendo para alcançar esse nó. Por outro lado, quando se trata de calcular a altura, começamos no nó em questão e depois viajamos em direção ao nó raiz. Nas duas vezes, começamos em 0. Há pessoas que também medem altura e profundidade de 1 e não de 0, o que não é errado e é exatamente o que as pessoas preferem.

Agora a profundidade máxima de um nó é definida como a profundidade de uma árvore binária. Da mesma forma, a altura máxima de um nó é definida como a altura de uma árvore binária. Assim, a altura e a profundidade de uma árvore binária são sempre as mesmas.

Saiba mais: Estruturas de dados e algoritmos em Python

O que é uma árvore de busca binária?

Uma árvore de busca binária é a mais comum de todos os outros tipos de árvores binárias. É uma árvore binária especializada que vem com propriedades diferentes e mais úteis do que qualquer outra forma de árvore binária. O que exatamente é uma árvore de busca binária ou BST? Assim como o próprio nome sugere, uma árvore de pesquisa binária é usada para pesquisar dados na árvore.

Um BST vem com propriedades que permitem que ele facilite buscas eficientes. Uma BST é uma árvore binária que tem a chave do nó que é menor e maior que os nós da subárvore direita e os nós da subárvore esquerda, respectivamente.

Representação de árvores binárias

1. Representação vinculada

Árvores binárias na representação encadeada são armazenadas na memória como listas encadeadas. Essas listas têm nós que não são armazenados em locais de memória adjacentes ou vizinhos e estão vinculados uns aos outros por meio do relacionamento pai-filho associado às árvores.

Nesta representação, cada nó tem três partes diferentes –

• ponteiro que aponta para o nó direito,
• ponteiro que aponta para o nó esquerdo,
• elemento de dados.

Esta é a representação mais comum. Todas as árvores binárias consistem em um ponteiro raiz que aponta na direção do nó raiz. Quando você vê um nó raiz apontando para nulo ou 0, você deve saber que está lidando com uma árvore binária vazia. Os ponteiros direito e esquerdo armazenam o endereço dos filhos direito e esquerdo da árvore.

2. Representação sequencial

Embora seja mais simples do que a representação vinculada, sua ineficiência a torna uma representação de árvore binária menos preferida das duas. A ineficiência está na quantidade de espaço necessária para o armazenamento de diferentes elementos da árvore. A representação sequencial usa um array para armazenamento de elementos de árvore.

O número de nós que uma árvore binária possui define o tamanho do array que está sendo usado. O nó raiz da árvore binária está no primeiro índice do array. O índice no qual um nó específico é armazenado definirá os índices nos quais os filhos direito e esquerdo do nó serão armazenados. Uma árvore vazia tem nulo ou 0 como seu primeiro índice.

Tipos de árvores binárias

1. Árvores binárias completas: Árvores binárias completas são aquelas árvores binárias cujos nós têm dois filhos ou nenhum. Em outras palavras, uma árvore binária se torna uma árvore binária completa quando, além das folhas, todos os outros nós têm dois filhos.
2. Árvores binárias completas: Árvores binárias completas são aquelas que possuem todos os seus diferentes níveis completamente preenchidos. A única exceção a isso pode ser o último nível, cujas teclas estão predominantemente à esquerda. Um heap binário é muitas vezes considerado como um exemplo de uma árvore binária completa.
3. Árvores binárias perfeitas: Árvores binárias perfeitas são árvores binárias cujas folhas estão presentes no mesmo nível e cujos nós internos carregam dois filhos. Um exemplo comum de uma árvore binária perfeita é uma árvore genealógica ancestral.
4. Árvores binárias degeneradas patológicas: Árvores degeneradas são aquelas árvores binárias cujos nós internos têm um filho. Seus níveis de desempenho são semelhantes às listas vinculadas. Saiba mais sobre os tipos de árvore binária.

Leia: As seis estruturas de dados mais usadas em R

Benefícios das árvores binárias

1. Uma maneira ideal de seguir a maneira hierárquica de armazenar dados
2. Reflete as relações estruturais que existem no conjunto de dados fornecido
3. Torne a inserção e a exclusão mais rápidas do que listas e matrizes vinculadas
4. Uma maneira flexível de armazenar e mover dados
5. São usados ​​para armazenar o maior número possível de nós
6. São mais rápidos que listas vinculadas e mais lentos que arrays quando se trata de acessar elementos

Conclusão

Neste blog, discutimos o que são árvores binárias em estruturas de dados, bem como falamos sobre seus tipos, suas representações e seus benefícios. Os dois principais usos das árvores são para pesquisar e armazenar dados e, portanto, são essenciais para o estudo da Ciência de Dados e seus campos relacionados.

Se você está curioso para aprender sobre árvores binárias em estruturas de dados, ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, mentoria com especialistas do setor, 1-on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.