[Curso de AeED - Aula 18] - Árvores

1- Árvores

Nos capítulos anteriores examinamos as estruturas de dados que podem ser chamadas de unidimensionais ou lineares, como vetores e listas. A importância dessas estruturas é inegável, mas elas não são adequadas para representarmos dados que devem ser dispostos de maneira hierárquica. Por exemplo, os arquivos (documentos) que criamos num computador são armazenados dentro de uma estrutura hierárquica de diretórios (pastas). Existe um diretório base dentro do qual podemos armazenar diversos subdiretórios e arquivos. Por sua vez, dentro dos sub-diretórios, podemos armazenar outros sub-diretórios e arquivos, e assim por diante, recursivamente. A Figura 1 mostra uma imagem de uma árvore de diretório no Windows.

Figura 1 - Árvore de diretórios do windows

Neste capítulo, vamos introduzir árvores, que são estruturas de dados adequadas para a representação de hierarquias. A forma mais natural para definirmos uma estrutura de árvore é usando recursividade. Uma árvore é composta por um conjunto de nós. Existe um nó r, denominado raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r. Esses nós raízes das sub-árvores são ditos filhos do nó pai, r. Nós com filhos são comumente chamados de nós internos e nós que não têm filhos são chamados de folhas, ou nós externos. É tradicional desenhar as árvores com a raiz para cima e folhas para baixo, ao contrário do que seria de se esperar. A Figura 2 exemplifica a estrutura de uma árvore.

Figura 2 - representação de árvore

Observamos que, por adotarmos essa forma de representação gráfica, não representamos explicitamente a direção dos ponteiros, subentendendo que eles apontam sempre do pai para os filhos. O número de filhos permitido por nó e as informações armazenadas em cada nó diferenciam os diversos tipos de árvores existentes. Neste curso, estudaremos dois tipos de árvores. Primeiro, examinaremos as árvores binárias, onde cada nó tem, no máximo, dois filhos. Depois examinaremos as chamadas árvores genéricas, onde o número de filhos é indefinido. Estruturas recursivas serão usadas como base para o estudo e a implementação das operações com árvores.

2 - Árvores Binárias

Numa árvore binária, cada nó tem zero, um ou dois filhos. De maneira recursiva, podemos definir uma árvore binária como sendo:
• uma árvore vazia; ou
• um nó raiz tendo duas sub-árvores, identificadas como a sub-árvore da
direita (sad) e a sub-árvore da esquerda (sae).

A Figura 3 a seguir ilustra uma estrutura de árvore binária. Os nós a, b, c, d, e, f formam uma árvore binária da seguinte maneira: a árvore é composta do nó a, da subárvore à esquerda formada por b e d, e da sub-árvore à direita formada por c, e e f. O nó a representa a raiz da árvore e os nós b e c as raízes das sub-árvores. Finalmente, os nós d, e e f são folhas da árvore.

Figura 3 - exemplo de árvore binária

Para descrever árvores binárias, podemos usar a seguinte notação textual: a árvore vazia é representada por (), e árvores não vazias por raiz(sae sad). Com essa notação, a(b(d()) c(e()f())). 
Pela definição, uma sub-árvore de uma árvore binária é sempre especificada como sendo a sae ou a sad de uma árvore maior, e qualquer das duas sub-árvores pode ser vazia. 

Uma propriedade fundamental de todas as árvores é que só existe um caminho da raiz para qualquer nó. Com isto, podemos definir a altura de uma árvore como sendo o comprimento do caminho mais longo da raiz até uma das folhas. Por exemplo, a altura da árvore da Figura 3 é 2. Assim, a altura de uma árvore com um único nó raiz é zero e, por conseguinte, dizemos que a altura de uma árvore vazia é negativa e vale -1.


3- Implementação em C

Análogo ao que fizemos para as demais estruturas de dados, podemos definir um tipo para representar uma árvore binária. Para simplificar a discussão, vamos considerar que a informação que queremos armazenar nos nós da árvore são valores de caracteres simples. Vamos inicialmente discutir como podemos representar uma estrutura de árvore binária em C. Que estrutura podemos usar para representar um nó da árvore? Cada nó deve armazenar três informações: a informação propriamente dita, no caso um caractere, e dois ponteiros para as sub-árvores, à esquerda e à direita. Então a estrutura de C para representar o nó da árvore pode ser dada por:

struct tree {
         int value;
         struct tree* left;
         struct tree* right;
};

Da mesma forma que uma lista encadeada é representada por um ponteiro para o primeiro nó, a estrutura da árvore como um todo é representada por um ponteiro para o nó raiz.

Como acontece com qualquer TAD (tipo abstrato de dados), as operações que fazem sentido para uma árvore binária dependem essencialmente da forma de utilização que se pretende fazer da árvore. Nas funções que se seguem, consideraremos que existe o tipo Tree definido por:

typedef struct tree Tree;

Como veremos as funções que manipulam árvores são, em geral, implementadas de forma recursiva, usando a definição recursiva da estrutura.

Vamos procurar identificar e descrever apenas operações cuja utilidade seja a mais geral possível. Uma operação que provavelmente deverá ser incluída em todos os casos é a inicialização de uma árvore vazia. Como uma árvore é representada pelo endereço do nó raiz, uma árvore vazia tem que ser representada pelo valor NULL. Assim, a função que inicializa uma árvore vazia pode ser simplesmente:

Tree* initialize(void){
          return NULL;
}

Para criar árvores não vazias, podemos ter uma operação que cria um nó raiz dadas a informação e suas duas sub-árvores, à esquerda e à direita. Essa função tem como valor de retorno o endereço do nó raiz criado e pode ser dada por:

Tree* create(char c, Tree* sae, Tree* sad){
          Tree* p = (Tree*)malloc(sizeof(Tree*));
          p->value = c;
          p->left = sae;
          p->right = sad;
          return p;
}

As duas funções inicializa e cria representam os dois casos da definição recursiva de árvore binária: uma árvore binária (Tree* a;) é vazia (a = inicializa();) ou é composta por uma raiz e duas sub-árvores (a = cria(c,sae,sad);). Assim, com posse dessas duas funções, podemos criar árvores mais complexas.

4 - Inserção

Quando estamos tratando de uma árvore binária de busca, é possível otimizar a inserção de um novo elemento passando apenas o valor que deseja-se inserir e o nó raiz. A partir destas informações a recursão é utilizada para percorrer a árvore e encontrar o local adequado para inserir o novo nó. Veja um exemplo de função para adicionar um elemento para a árvore:

Tree* add(Tree* nod, int number) {
    if (nod == NULL) {
        nod = (Tree*) malloc(sizeof (Tree));
        if (nod == NULL) {
            return NULL;
        }
        nod->value = number;
        nod->left = NULL;
        nod->right = NULL;
        return nod;
    }
    if (nod->value > number) {
        nod->left = add(nod->left, number);
    } else {
        nod->right = add(nod->right, number);
    }
    return nod;
}

A figura 4 mostra como se comporta o algoritmo de inserção de um novo elemento em uma árvore binária de busca.

Figura 4 - inserção do nó 5 na árvore binária.

5- Remoção

Quer saber mais sobre a Inclusão de novos nós em uma árvore binária? veja este vídeo do professor Norton:



A exclusão de um nó de uma árvore binária deve prezar pela exclusão do nó e a reorganização da árvore de modo que ela não perca suas propriedades. Sendo assim, deve se adotar alguma política de exclusão e implementa-la no código. A seguir veja um exemplo de como ocorre a exclusão de um nó em uma árvore por meio da animação da figura 5.

Figura 5 - Remoção de um nó
Existem algumas situações que devem ser tratadas no caso da exclusão de um nó, são elas:
- Se o nó excluído for o nó raiz;
- Se o nó excluído é uma folha;
- Se o nó excluído é uma possuir um ou dois filhos;

Para excluir um nó devemos adotar uma política de exclusão, elas podem ser:
- Excluir o nó mais a direita da sub-árvore da esquerda; ou
- Excluir o nó mais a esquerda da sub-árvore da direita;

Veja a implementação em C do algoritmo:

Tree* pop(Tree* t, int x) {
    Tree* tmp;
    if (t == NULL) {
        return t;
    }
    if (x < t->value) {
        t->left = pop(t->left, x);
    } else {
        if (x > t->value) {
            t->right = pop(t->right, x);
        } else { // here we say that the searched node is found 
            if (t->left && t->right) {
                tmp = findMinimum(t->right);
                t->value = tmp->value;
                t->right = pop(t->right, t->value);
            } else {
                tmp = t;
                if (t->left == NULL) {
                    t = t->right;
                } else {
                    if (t->right == NULL) {
                        t = t->left;
                    }
                    free(tmp);
                }
            }
        }
    }
    return t;

}

Você quer entender melhor como é feita a remoção? veja este excelente vídeo do professor Norton:




6 - Busca e impressão

Sobre os possíveis percursos de uma árvore podemos variar a impressão das subárvores e também da raiz. Assim, é possível realizar três tipos de percursos diferentes: inordem, pre-ordem e pós-ordem. 
O percurso in-ordem são impressos os nós da sub-árvore da esquerda, o nó raiz e os nós da subárvore da direita. Veja o exemplo de implementação?

void printInorder(Tree* nod) {
    if (nod == NULL) {
        return;
    }
    printInorder(nod->left);
    printf(" %d ", nod->value);
    printInorder(nod->right);
}

A impressão pré-ordem acontece quando a raiz é impressa, em seguida a sub-árvore da esquerda e por fim a sub-árvore da direita. Veja um exemplo:

void printPreOrder(Tree* nod) {
    if (nod == NULL) {
        return;
    }
    printf(" %d ", nod->value);
    printInorder(nod->left);
    printInorder(nod->right);
}

Por fim, temos a impressão pós ordem, onde é impressa a sub-árvore da esquerda, em seguida a sub-árvore da direita e por fim a raiz. Veja o Exemplo:

void printPosOrder(Tree* nod) {
    if (nod == NULL) {
        return;
    }
    printInorder(nod->left);
    printInorder(nod->right);
    printf(" %d ", nod->value);
}

Entenda como funciona a busca e também a impressão neste vídeo do professor Norton:



[Curso de AeED - Aula 18] - Árvores [Curso de AeED - Aula 18] - Árvores Reviewed by Vinicius dos Santos on 05:38:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!