Árvores: estrutura de dados

Conheça as principais características e propriedades de uma árvore, uma das mais importantes estruturas de dados não lineares da computação.

Nos siga em nossas redes sociais.

Conceito de árvores

As árvores representam um dos tipos de estruturas de dados mais importantes da computação. Elas podem ser implementadas em praticamente qualquer linguagem de programação.

A estrutura de uma árvore define uma organização de elementos dispostos de forma hierárquica. A imagem abaixo ilustra a representação de uma árvore, onde é possível perceber a analogia do termo utilizado para a estrutura.

Ela possui uma grande utilidade em diversas aplicações reais, tais como: estruturas de pastas em um sistema operacional, interfaces gráficas, banco de dados e sites da internet. Veja abaixo dois exemplos.

Uma árvore modelando relacionamentos em uma rede social

Uma árvore modelando a estrutura de pastas em um sistema operacional

Estrutura de uma árvore

Toda árvore é formada por dois elementos básicos denominados:

  1. nós (ou nodos)
  2. arestas que interconectam estes nós.

Veja a ilustração na imagem abaixo.

Os nós de uma árvore representam espaços onde podem ser armazenados diversos tipos de informações, tais como: um telefone, uma data, um nome, uma lista de e-mails, um perfil de um usuário em uma rede social, para citar alguns.

As arestas, representam relacionamentos entre esses nós. Representam a forma com a qual os nós se conectam, e essa relação depende totalmente da forma como a árvore é utilizada e do tipo de informação que os nós da árvore armazenam. Por exemplo:

  • em uma árvore que modela relacionamentos em uma rede social, as arestas podem representar graus de amizade.
  • em uma árvore que modela a estrutura de pastas de um sistema operacional, as arestas podem representar graus de pertencimento (quais pastas pertencem a quais outras pastas).

A grande diferença de uma árvore para outras estruturas de dados comuns (tais como arranjos, listas, filas e pilhas) é que as árvores não são organizadas em uma sequência. Em uma árvore não podemos determinar o próximo elemento e o elemento anterior, porque as suas informações não se organizam de maneira enfileirada.

Veja na ilustração abaixo essa diferença.

Em uma lista, cada informação possui relação com outros dois elementos: o anteior e o próximo.
Em uma árvore, cada informação (nó) pode possui relação com mais de dois elementos

Por este motivo, as árvores são denominadas estruturas não lineares. E isto a torna uma estrutura bastante especial, com diversas propriedades e características diferenciadas.

Propriedades hierárquicas de uma árvore

Nó raiz

Toda a árvore possui um nó principal, denominado raiz. A raiz representa o nó inicial de todos os tipos de árvore.

Nós filhos e nós pais

A partir da raiz, todos os nós inferiores ligados a um nó superior são denominados nós filhos. Todos os nós superiores, que geram nós inferiores, são chamados de nós pais.

Nó folha

Os nós que não possuem filhos são denominados nós folha.

O termo “nó folha” faz alusão às folhas de uma árvore, já que elas representam o final de um galho. A imagem abaixo ilustra essa metáfora.

Nós irmãos.

Outro conceito importante é o conceito de irmandade entre os nós. Dois nós são irmãos se eles descendem diretamente do mesmo nó pai. Veja os exemplos nas ilustrações abaixo.

Graus e ordem de uma árvore

O grau é a propriedade que qualifica os nós de uma árvore, ela define a quantidade de filhos que cada nó de uma árvore possui. Veja nas ilustrações abaixo.

A ordem é um conceito que qualifica toda a árvore. A ordem de uma árvore é definida pelo seu nó de maior grau. Ex.: se o maior grau da árvore é 3, então a árvore possui ordem 3. Veja abaixo algumas ilustrações.

Árvore de ordem 2

Árvore de ordem 3

Árvore de ordem 4

Ancestralidade e descendência

A ancestralidade é um conceito que qualifica nós superiores em relação a nós inferiores. Quando existe um conjunto de arestas que ligam um nó superior A a um nó inferior B, dizemos que A é ancestral de B.

A descendência é um conceito que qualifica nós inferiores em relação a nós superiores. Quando existe um conjunto de arestas que ligam um nó inferior B a um nó superior A, dizemos que B é descendente de A.

Profundidade de um nó

A profundidade é um conceito que qualifica um nó de uma árvore. Ela define a distância de um determinado nó até a raiz.

Nível de uma árvore

O nível define as fatias de profundidade de uma árvore, de maneira que os filhos de um nó sempre são colocados em níveis posteriores.

Altura de uma árvore

Representa a maior profundidade da árvore. Representa a distância entre a raiz e um nó folha do maior nível da árvore.

Conceito de subárvore

A partir da raiz, cada novo filho representa uma subárvore, uma nova árvore que se redefine de forma recursiva.

Representação computacional

Para representar computacionalmente uma árvore, precisamos de duas estruturas: uma para representar os nós da árvore e outra para representar toda a árvore.

Representação de uma árvore de ordem 2 (binária)

O código abaixo apresenta uma possível representação estrutural para uma árvore de ordem 2 (conhecida como árvore binária). Perceba que na classe node (linhas 7-18) temos dois apontadores (linhas 9-10), um para o filho da esquerda e outro para o filho da direita.

1./* Classe que representa àrvore binária*/

2.public class BinaryTree {

3.     Node root; // apontador para o nó raiz

4.}

5.

6./* Classe que representa os nós da árvore*/

7.public class Node {

8.     int value; // valor armazenado no nó

9.     Node left; // apontador para o nó filho esquerdo

10.     Node right; // apontador para o nó filho direito

11.

12.     /* Constutor do nó*/

13.     Node(int value) {

14.          this.value = value;

15.          right = null;

16.          left = null;

17.     }

18.}

Representação de uma árvore de ordem 4 (quadtree)

O código abaixo apresenta uma possível representação estrutural para uma árvore de ordem 4 (conhecida como quadtree). Perceba que na classe node (linhas 7-16) temos um arranjo de apontadores (linha 9) no lugar de dois apontadores left e right.

1./* Classe que representa a QuadTree*/

2.public class QuadTree {

3.     Node root; // apontador para o nó raiz

4.}

5.

6./* Classe que representa os nós da árvore*/

7.public class Node {

8.     int value; // valor armazenado no nó

9.     Node[] children; // arranjo de apontadores para os nós filhos

10.     

11.     /* Constutor do nó*/

12.     Node(int value) {

13.          this.value = value;

14.          children = new Node[4]; // inicializa os apontadores

15.     }

16.}

Os códigos apresentados acima representam apenas as estruturas das árvores. Além da representação estrutural, as árvores possuem diversas operações, tais como as operações básicas de: inserção, remoção, busca, para citar algumas.

Nos siga
em nossas redes sociais.

Nos siga em nossas redes sociais.