Estruturas de Dados: Árvores Binárias

Árvores binárias são estruturas de busca eficientes e muito úteis em diversas situações. Entendendo seu conceito, você criará soluções otimizadas para problemas de busca e acesso de dados.

Sem dúvidas, árvores são estruturas de dados que usamos em várias situações, pois são muito úteis para armazenar dados hierárquicos. Dessa forma, podemos usá-las em bancos de dados, pastas de arquivos, sistemas de busca e na interface DOM (Document Object Model), que usa de conceitos como parent nodes (nó-pai) e child nodes (nó-filho).

O dados são divididos em nós que compõem os níveis da árvore. O nível zero é a raiz, pois é a partir dele que toda a árvore vai se organizar. Chamamos os nós que partem da raiz de nós-filhos da raiz (child nodes). Eventualmente, quando novos nós saem dos nós-filhos, eles se tornam nós-pai (parent nodes) e assim por diante. Finalmente, temos ainda os nós-folha, que são aqueles que não tem nós-filhos.

Árvores Binárias

Para ser binária, cada nó da árvore deve ter de 0 a 2 filhos, no máximo. Ou seja, ela pode ser vazia, sem nenhuma subárvore, ou pode ter duas subárvores, a subárvore direita e a subárvore esquerda. Observe a imagem:

Observe que nas árvores binárias só existe um caminho a percorrer, indo da raiz aos nós-folha. Isso é importante para definir a altura da árvore, que se define pelo maior caminho a partir de um determinado nó.

Na imagem, podemos observar que:

• A é a altura do nó raiz (24) até o nó-folha (39), então a altura de A é 3;
• B é a altura do nó raiz (24) até o nó 35, então a altura de B é 2;
• C é a altura do nó raiz (24) até o nó-filho 32, então a altura de C é 1.

Atenção! A altura e o nível de uma árvore binária não são a mesma coisa. Altura é a distância entre um nó e outro, ou seja, quantos nós existem entre um nó e outro. No exemplo, a altura de A é 3 porque entre 24 e 39 existem 3 nós (o 32, o 35 e o 39).

Algoritmos de busca em árvores binárias

Usamos algoritmos de busca em árvores binárias quando queremos buscar um determinado valor dentro de uma árvore. Por exemplo, quando usamos propriedades childNodes ou firstChild no DOM, essas propriedades retornam uma nodeList de filhos (childNodes) do elemento passado e o primeiro filho do elemento passado (firstChild), respectivamente.

Os algoritmos de busca mais conhecidos são três: pré-ordem, em ordem e em pós-ordem.

Pré-Ordem

Esse algoritmo segue a seguinte lógica:

1. Visita o primeiro nó, que é a raiz;
2. Vai buscar o valor na subárvore esquerda da raiz;
3. Caso não encontre o valor na subárvore esquerda, percorre a subárvore direita.

Em Ordem

O algoritmo em ordem segue a seguinte lógica:

1. Percorre a subárvore à esquerda;
2. Visita o nó raiz;
3. Percorre a subárvore à direita

Pós-Ordem

O algoritmo pós-ordem segue a seguinte lógica:

• Percorre a subárvore à esquerda;
• Percorre a subárvore à direita;
• Visita o nó raiz.

O código a seguir mostra uma construção de árvore com os algoritmos de busca:

let arvore = {
    left: {
        left: undefined,
        right: {
            value: 3
        },
        value: 2
    },
    right : undefined,
    value: 10
}

function preOrder(tree) {
    console.log(tree.value)
    tree.left && preOrder(tree.left)
    tree.right && preOrder(tree.right)
}

function inOrder(tree) {
    tree.left && inOrder(tree.left)
    tree.right && inOrder(tree.right)
    console.log(tree.value)
}
function posOrder(tree) {
    tree.left && posOrder(tree.left)
    console.log(tree.value)
    tree.right && posOrder(tree.right)
}

console.log("Pré-Ordem: ")
preOrder(arvore)
console.log("Em Ordem: ")
inOrder(arvore)
console.log("Pós-Ordem: ")
posOrder(arvore)

Conclusão

No Visual Go você pode ver o funcionamento de árvores binárias e entender como o algoritmo as percorre para buscar os valores e como isso interage com o código.

Bons estudos!