Sistema Computacional - Estrutura de dados árvore

Estrutura de dados árvore

No contexto da computação, a estrutura de dados árvore é considerada como uma das mais importantes ferramentas classificadas como não-lineares. Diferente das listas, em que os dados são dispostos em uma certa sequência, as árvores são construídas de modo hierárquico, ou seja, os seus elementos se encontram em níveis abaixo ou acima de outros elementos.

Apesar de a princípio ser uma estrutura de dados simples em relação ao tratamento computacional, a árvore pode ser construída com base em diversas propriedades que podem ser mais vantajosas para certos casos do que em outros. Árvores como a rubro-negra apresentam um bom desempenho em operações de busca, mas por outro lado possui uma complexidade maior.

Existem uma grande diversidade de aplicações para a estrutura de dados árvore como, por exemplo, no sistema operacional que utiliza dessas estruturas para organizar as pastas. Além disso, também é útil em banco de dados, interfaces gráficas e sites da internet.

Conceito

A estrutura de dados árvore pode ser definida como um conjunto de registros que satisfaz certas condições sendo que esses registros são denominados nós ou células. As informações básicas que um nó precisa ter é um campo para guardar o endereço do nó a esquerda, um campo para guardar o endereço do nó a direita e um campo para guardas as informações que precisar assim como na imagem abaixo.

[pic 1]

Para construir a árvore é preciso respeitar a seguinte condição: todo nó que for inserido do lado esquerdo desse nó, deve possuir um índice menor que ele. Isso também vale para o nó da direita e para os respectivos filhos desses novos nós.

Todos os nós que estiverem dispostos em um nível hierárquico abaixo são denominados filhos e o mesmo vale para o nó do nível superior que é chamado de pai. De certa forma, as nomenclaturas utilizadas em uma árvore genealógica se aplicam para esse tipo de estrutura de dados.

Como resultado dessa condição, ao inserir os elementos 6, 4, 1, 5, 7, 8, 3 obtém-se a seguinte estrutura de dados árvore:

[pic 2]

Operações

Os procedimentos necessários para conseguir manusear os nós corretamente são:

• Buscar: para encontrar um dado elemento na árvore basta ter o índice que se deseja buscar e compará-lo com cada elemento, ou seja, se for menor vai para a esquerda, senão para a direita.
• Inserir: a inserção irá utilizar o método buscar para encontrar o local exato que deve ser inserido o novo elemento.
• Remover: a operação de remoção, para ser efetuada com sucesso, deve levar em consideração os filhos do nó a ser removido, pois não se deve perde-los.

A estrutura de dados árvore, sem dúvida, apresenta propriedades bastante interessante e que valem a pena ser exploradas.

---

[pic 3]

Fonte: https://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/N-ary_to_binary.svg/2000px-N-ary_to_binary.svg.png

Nome da Imagem: estrutura-de-dados-árvore-condição-nó