Árvores binárias de busca
Por Igor Cruz
(igor.cruz@ccc.ufcg.eu.br)
Estrutura de dados, na computação, representa uma forma organizada de armazenamento de dados em um computador com o objetivo de aumentar a eficácia do armazenamento e da obtenção da informação. Existem diversos tipos de estruturas de dados adequadas para diferentes tipos de aplicações, uma dessas estruturas é a árvore binária.


Uma árvore binária tem um nó raiz e no máximo duas sub-árvores, uma sub-árvore esquerda e uma sub-árvore direita.

Todos os nós da sub-árvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da sub-árvore direita possuem um valor superior ao nó raiz. O objetivo da árvore binária é estruturar os dados para tornar mais fácil a obtenção da informação;

Propriedades:

  • O grau de um nó é definido pelo número de sub-árvores que ele possui;

  • O grau da árvore é dado pelo nó, de maior grau, que ela possui;

  • A profundidade (distância de um nó folha até a raiz) de uma árvore com n elementos (n>0) é no mínimo log n na base 2, e no máximo n-1;

  • Uma árvore binária, não vazia com profundidade h, tem no mínimo h+1, e no máximo 2^(h+1)-1 nós;

  • A profundidade média de uma árvore de n nós é O(vn);

Confira o tutorial abaixo para entender melhor sobre o assunto:

Vamos agora responder a questão abaixo do POSCOMP 2013.

Resolvendo a questão:

  • O primeiro nó a adicionar é o 30, já que ele é a raiz;

  • O segundo e o terceiro devem ser o 15 e o 60 independente da ordem, já que os valores numéricos maiores que a raiz vão para a sub-árvore direita e os menores para a sub-árvore esquerda. Assim temos a árvore binária ao lado;

  • Para gerarmos a arvore descrita na questão, temos agora que adicionar a nossa árvore mais quatro nós, são eles: 10, 20, 40 e 80. Devemos então continuar a adicionar a partir do nó com menor valor, no nosso caso o 10, pois como ele é menor que 30, descemos para a sub-árvore a esquerda e como é menor que 15, ele se tornará seu filho a esquerda;

  • Em seguida adicionamos o 20, que assim como o 10, desce para a sub-árvore a esquerda de 30, porém, em seguida, como é maior que 15, se torna seu filho a direita;

  • Por fim adicionamos os nós 40 e 80, nessa ordem, pois, de acordo com a explicação anterior, respectivamente tornam-se o filho à esquerda e o filho à direita de 60;

  • Existem outras ordens de inserção que gerariam a mesma árvore, porém, para essa questão a resposta certa é a “letra c”;

Referências:

Jornal PETNews - Edição: Caio Paes - Revisão: Janderson Jason e Joseana Fechine
Grupo PET Computação UFCG, 2011. All rights reserved.