Árvores: estrutura de dados

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:

• nós (ou nodos).
• 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 anterior 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.    /* Constutor do nó */
12.    Node(int value) {
13.        this.value = value;
14.        right = null;
15.        left = null;
16.    }
17.}

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.    /* Constutor do nó */
11.    Node(int value) {
12.        this.value = value;
13.        children = new Node[4]; // inicializa os apontadores
14.    }
15.}

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.