Árvores

Com o tempo, novos modelos de árvores serão adicionados a este documento.

Em computaçào, árvores são tipos abstratos de dados que que simulam estruturas hierárquicas. Uma estrutura de árvore pode ser definida recursivamente como uma estrutura de nós, onde um nó contém uma chave, possivelmente um valor associado a essa chave, e uma lista de nós, porém nenhum nó da lista de nós pode ser duplicado, e nenhum nó pode apontar para um nó anterior. As árvores são um caso específico de grafos, direcionados e que não contém cíclos, ou seje, são exemplos de DAG, Directed Acyclic Graph (Grafos Acíclicos Direcionados).

Uma árvore é uma estrutura recursiva definida por um nó $r$, que chamamos de raiz da árvore (ou raiz,ou nó raiz). Este nó pode conter um conjunto de nós filhos, que por sua vez são também raízes de sub-árvores. Um caso especial de árvore é a árvore vazia, uma árvore sem nenhum nó.

Podemos definir uma árvore recursivamente, assumindo que um nó $r$ é uma árvore $T$. Se $T_1, T_2, \ldots, T_n$ são árvores disjuntas, com raízes $r_1, r_2, \ldots, r_n$, podemos conectar o nó $r$ às raízes das árvores $T_1, T_2, \ldots, T_n$, fazendo de $r$ raiz da árvore gerada. Diz-se então que $r$ é o nó pai e os nós $r_1, r_2, \ldots, r_n$ são os nós filhos. Assim, podemos descrever a árvore $T$ como:

$$ T = \{r\} \cup T_1 \cup T_2 \cup \ldots \cup T_n $$

Ou, de forma mais sucinta como:

$$ T = \{ r, T_1, T_2, \ldots, T_n \} $$

O nó raiz de uma árvore se caracteriza por não possuir um nó pai. Além deste nó, a árvore também é composta dos nós internos, que possuem um pai e um ou mais filhos, e dos nós folha, que possuem um pai, porém não possuem filhos (Figura 1).

Estrutura de árvore. Estrutura em Árvore

A estrutura de um nó (Figura 2) varia de acordo com a aplicação na qual a árvore é utilizada, e ela pode incluir ou não um conjunto de dados. Este conjunto de dados pode conter chaves e/ou valores. Em alguns modelos de árvores, todos os nós contém dados (tanto chaves, como valores), em outros modelos os dados estão concentrados apenas nas folhas, e em outros todos os nós possuem a representação de uma chave, porém os valores só são armazenados nas folhas.

Estrutura de um nó da árvore. Estrutura em Árvore

Cada nó de uma árvore tem um grau (ou ordem), que é dado pelo número de filhos que possui. Uma árvore pode ter um grau definido, e, neste caso, nenhumo de seus nós podem possuir um grau maior que o grau definido para a árvore. Uma árvore cheia, é uma árvore onde todos os nós, com exceção das folhas, possuem o grau máximo definido para a árvore. Uma árvore balanceada, que é uma árvore onde as sub-árvores de um nó possuem, aproximadamente, a mesma altura. Uma, árvore cheia, é uma árvore balanceada (Figura 3).

Exemplos de árvores. Exemplos de Árvores

A altura de um nó é o tamanho do maior caminho do nó até as folhas. A altura da raiz é a altura da árvore. Diversos algoritmos possuem sua eficiência diretamente relacionada a altura da árvore, por esse motivo, é interessante que seja possível limitar ou controlar a altura da árvore.

A profundidade de um nó é o tamanho do caminho deste nó até a raiz. Uma outra form de ver a profundidade da árvore é através de níveis, onde a raiz da árvore se encontra no nível 0 (zero), os filhos da raiz no nível 1 (um), os filhos destes nós no nível 2 (dois), e assim por diante.

Aplicações

Árvores são muito utilizadas em diversas áreas de computação, como na:

  • Representação de dados hierárquicos
    são utilizadas em sistemas como LDAP (ou na sua versão opensource), ou na representação de hierarquias de classes por herança.
  • Armazenar dados de forma que a pesquisa seja eficiente
    árvores de pesquisa como as [árvores binários de pesquisa] ou as B-Trees são bastante utilizadas em índices de bancos de dados para rápida recuperação dos dados.
  • Ordenar dados
    árvores são utilizadas para ordenação de dados, como no algoritmo heapsort, ou na criação de árvores binárias de pesquisa, que ordenam os dados naturalmente.
  • Algoritmos de roteamento
    alguns algoritmos de roteamento como o STP, OSPF e IS-IS, utilizam estruturas de árvores em seus algoritmos.
  • Inteligência Artificial
    diversos algoritmos utilizam estruturas de árvores, sendo um dos métodos mais conhecidos são as árvores de decisão, bastante utilizadas em aprendizado de máquinas (machine learning).
  • Organização de dados espaciais
    modelos de árvores são utilizados para organizar, localizar e filtrar dados com informações espaciais, como coordenadas de GPS.

Operações em Árvores

Embora diveras outras operações possam ser realizadas em árvores, aqui são listadas as operações mais gerais, utilizadas por qualquer modelo de árvore.

Procurar um item

Talvez a operação mais comum em árvores seja a procura por um item específico. As árvores podem ser criadas de forma que a pesquisa de elementos seja muito eficiente, o mais eficiente possível, quando a pesquisa é realizada baseada em comparações. Devido a esta capacidade, as árvores são muito utilizadas na criação de arrays associativos.

Enumerar itens

Em diversas situações é preciso executar operações em todos os elementos de uma árvore, ou enumerá-los. Estas operações podem ser executadas eficientemente, percorrendo a estrutura de uma árvore.

Duas formas tradicionais de percorrer uma estrutura de árvore é utilizar o caminho em pré ordem (Algoritmo 1) ou o caminho em pós ordem (Algoritmo 2). No caminho em pré ordem (pre order), o nó é avaliado antes que o caminho siga pelos filhos deste nó. No caminho em pós ordem (post order), o nó é avaliado após as sub-árvores que tem os filhos do nó como raízes.

A implementação destas formas de percorrer a árvore é bastante simples se utilizarmos recursão. Por serem estruturas naturalmente recursivas, a implementação de algoritmos recursivos em árvores é bastante eficiente, e, normalmente, muito mais simples do que as versões iterativas dos mesmos algoritmos.

Percurso em pré-ordem

pre_order_walk(node):
    visit(node)
    for child in node.children:
        pre_order_walk(child)

Percurso em pós-ordem

post_order_walk(node):
    for child in node.children:
        post_order_walk(child)
    visit(node)

Além do percurso na árvore utilizando diretamente a conexão entre os nós, é possível realizar o percurso na árvore com relação aos seus níveis (Algoritmo 3).

Percurso em níveis

level_order_walk(node):
    q = Queue()
    q.push(node)
    while not q.is_empty()
        n = q.pop()
        visit(n)
        for child in n.children:
            q.push(child)

Além dos percursos como o objetivo de enumerar os elementos de uma árvore, podemos realizar percursos na árvore com o objetivo de encontrar caminhos dentro da estrutura (por exemplo, em árvores de diretórios, em sistemas de arquivos), ou para encontrar distâncias relativas entre nós de uma árvore.

Adicionar um novo elemento, em uma posição da árvore

Ao adicionar elementos à árvore, este elemento deve manter as regras da árvore, preservando as características, de pesquisa, organização, e inserção. Neste processo, deve ser garantido que o elemento adicionado não tenha como filhos um outro elemento já existente da árvore, para que não se crie um ciclo.

Remover um elemento

A remover elementos de uma árvore, uma série de casos especiais devem ser tratados, e deve ser garantido que a estrutura da árvore mantenha-se estável. Em alguns modelos de árvores, este processo pode ser bastante complexo, em outros, é um processo extremamente simples.

Poda: remoção de uma seção

A poda de uma árvore é a remoção de toda uma seção da árvore, normalmente marcada por uma sub-árvore. É uma operação razoavelmente simples, pois envolve um número menor de casos a serem tratados.

Enxerto: inserção de uma seção

A inserção de uma sub-árvore em uma árvore é um processo semelhante à inserção de um único elemento, no entanto, como a sub-árvore contém vários elementos, é necessário garantir que a inserção de todos os elementos não modifique as regras para o restante da árvore.

Modelos de Árvores

Existem diversos modelos de árvores, desenvolvidos para aplicações diferentes. Estes modelos variam tanto na forma como as chaves são tratadas, como na forma como os dados são armazenados na árvore, e em relação ao grau dos nós. A semelhança entre os diversos modelos é a estrutura básica das árvores, que garantem a inexistência de ciclos, e a existência de um único caminho entre a raiz e uma das folhas da árvore.

Heaps

Um heap é uma estrutura de árvore especializada de forma a satisfazer uma propriedade específica: se A é pai de B, então a chave do nó A é ordenada em relação à chave do nó B com a mesma ordenação aplicada em todo o heap. A ordenação aplicada ao heap criará um "heap máximo", quando a regra de ordenação for pais com chaves maiores que as dos filhos, ou um "heap mínimo", quando a regra de ordenação for pais com chaves menores que as dos filhos. Desta forma, o heap máximo apresenta o elemento com a chave de maior valor na raiz, e o heap mínimo apresenta a menor chave na raiz.

Heaps são muito úteis na implementação eficiente de filas de prioridade e do algoritmo de Dijkstra. O algoritmo de ordenação heapsort utiliza um heap para realizar a ordenação de elementos de forma eficiente.

Árvores Binárias de Pesquisa

Árvores binárias de pesquisa (BST do inglês Binary Search Trees) são árvores de grau dois, onde os elementos armazenados são ordenados de acordo com o valor de suas chaves. Como os elementos são armazenados de forma ordenada, a busca por elementos se assemelha a uma busca binária, sendo muito eficiente, auxiliando, não apenas na recuperação de itens, mas também na inserção e remoção de elementos.

Um nó de uma árvore binária de pesquisa possui uma chave, e dois filhos, o filho esquerdo, e o filho direito. Na inserção de um novo item, a chave do novo item é comparada com a chave do item, se o valor desta chave for menor, o processo de inserção continua no filho à esquerda, no entanto, caso este valor seja maior, o processo de inserção continua no filho à direita (Figura 4).

Árvore Binária de Pesquisa Exemplos de Árvores

Em árvores binárias de pesquisa, o percurso em ordem (Algoritmo 4) permite recuperar todos os elementos ordenados pelas chaves de pesquisa. Nesta forma de percurso, os elemetos a esquerda são percorridos primeiro, então o elemento do nó é avaliado, e só então os elementos a direita são percorridos.

Percurso em pós-ordem

in_order_walk(node):
    in_order_walk(child)
    visit(node)
    in_order_walk(child)

Este modelo básico de árvore binária de pesquisa, apesar de útil, apresenta limitações com relação a estrutura gerada, dependendo da ordem de inserção dos elementos. Por esse motivo, outros modelos de árvores binárias de pesquisa foram criados e são normalmente utilizados.

Árvores Binárias de Pesquisa Auto-organizáveis

Uma árvore binária auto-balanceável é que uma árvore binária de pesquisa que automaticamento mantém um limite máximo de altura independente da ordem dos elementos inseridos. Estes modelos de árvores binárias de pesquisa evitam a degeneração em uma lista encadeada, por exemplo quando são inseridos elementos com chaves seqüenciais. Mantendo a altura da árvore com $n$ limitada a $\lfloor log_2\,n \rfloor$ os algoritmos de busca, pela chave de pesquisa, aproximam-se do limite $O(lg\,n)$.

Árvores binárias de pesquisa auto-balanceáveis são muito utilizadas como estrutura de armazenamento de dados de arrays associativos, conjuntos, filas de prioridade, e listas ordenadas.

Entre os modelos mais populares de árvores binárias auto-balanceáveis, os mais comuns são as AVL, Red-black, Splay, Scapegoat, e Treap.