Three Types of Trees (T3)

Não canso de assistir esta ótima aula do Donald Knuth. Além de informativa e complexa, ela é muito divertida. Segundo Knuth, de tempos em tempos, durante a época do Natal, ele ministra uma aula sobre árvores (matemáticas e/ou computacionais), denominadas de Christmas Tree Lecture. Inclusive ele referencia o cartoon do XKCD sobre árvore (de natal) – onde ele é frequentemente homenageado.

1 tree

Este cartoon é um dos meus favoritos pela quantidade de coisas ligadas (intencionalmente ou não) com algoritmos e estruturas de dados. A árvore de natal representa uma árvore binária balanceada, abaixo uma estrutura de heap organizada pelo máximo (max priority queue) e a estrela no topo da árvore pode ser interpretada como o algoritmo A-Star (A-Estrela ou A*), cujo objetivo é encontrar o caminho mais curto entre um ponto de origem e um determinado ponto de destino.

Árvore Balanceada ou Não Balanceada, eis a questão

A estrutura de dados do tipo árvore é aplicada em diversos lugares: na organização do sistema de arquivos, na organização de dados para busca de informações, para determinar um caminho, na representação de uma expressão algébrica, entre outros. Um tipo comum de árvore é a binary search tree (BST), que permite a organização dos dados de modo que a busca seja eficiente. Por exemplo, a figura abaixo, retirada da Wikipedia, apresenta uma BST:

2 Sorted_binary_tree.svg

A regra básica de uma BST é: dado um determinado nó (ou vértice), todos os nós (ou vértices) filhos (ou adjacentes) estarão a esquerda, se forem menores do que o pai, ou estarão a direita, se forem maiores que o pai. Quando os valores forem iguais, é convencionado livremente se irá para esquerda ou para a direita quando aceitar entradas repetidas, caso contrário irá ignorá-lo ou subscrevê-lo. Na figura anterior, onde não há nós (ou vértices) com valores repetidos, é notado que: G é pai de I, e I está a direita porque lexicograficamente G é menor do que I. I é pai de H, e H está a esquerda de porque lexicograficamente I é maior do que H. Ou seja, G < I e I > H. Então, montar e buscar numa árvore do tipo BST é relativamente um trabalho trivial. Por exemplo, o código F# abaixo é uma estrutura cujo representa um nó (ou vértice) com bifurcação de forma genérica:

type Node<‘a> = { value : ‘a; left : Node<‘a> option; right : Node<‘a> option }

A função newNode, é uma helper para criação nós (ou vertices) também em F#:

let newNode (value, left, right) = Some { value = value; left = left; right = right }

Logo, para reproduzir a árvore da figura anterior, basta a sequência de instruções F# como segue:

let c = newNode(‘C’, None, None)
let e = newNode(‘E’, None, None)
let h = newNode(‘H’, None, None)
let a = newNode(‘A’, None, None)
let d = newNode(‘D’, c, e)
let i = newNode(‘I’, h, None)
let b = newNode(‘B’, a, d)
let g = newNode(‘G’, None, i)
let f = newNode(‘F’, b, g)

Onde é obtido o seguinte resultado:

3 fsi_node

O valor em questão é do tipo caractere, o tipo Node é genérico, logo o parametro genérico ’a será substituido por char devido ao mecanismo de inferência de tipos do F#. Por causa do tipo de dado inferido, o exemplo utiliza comparação lexicográfica, mas para outros tipos de dados isto não é necessáriamente verdade e um tipo customizado deverá prover via interfaces de comparação o comportamento desejado.

Uma ação comum com árvores é percorrê-las, onde a frase em inglês correspondente é tree traversal. Existem dois modos de busca comuns para isso: por profundidade, denominada de depth-first search e por extensão, denominada de  breadth-first search.

Em profundidade, significa que a partir de um dado nó (ou vértice), o próximo elemento a ser visitado é um elemento filho mais a esquerda. Se este filho tiver outros filhos, eles  serão os próximos a serem visitados da esquerda para direita. E isto é feito até a exaustão, ou seja, todos forem visitados. Bem, este é o tipico procedimento que é dificil explicar por palavras. Portanto, “plotando” com o Mathematica a árvore equivalente ao código anterior, temos:

4 btree

Uma busca parcial por profundidade, iniciando por F, teria como resultado as visitas subsequentes a B e A. No caso de um depth-first search, é necessário saber que para percorrer todos os nós (ou vértices) e ter um resultado de visitas, existem 3 formas categorizadas como: pre-order, in-order e post-order. Estas formas indicam, como o nó em questão é visitado ou uma função de visita atua, e como os nós (ou vértices) filhos são percorridos. Isto altera totalmente o resultado final – como será visto a seguir. Em linhas gerais, no contexto de uma BST, a ação pre-order é: visitar o nó (ou vértice) atual, percorrer a sub-árvore da esquerda e percorrer a sub-árvore da direita. A ação in-order é: percorrer a sub-árvore da esquerda, visitar o nó (ou vértice) atual e percorrer a sub-árvore da direita. A ação post-order é: percorrer a sub-árvore da esquerda, percorrer a sub-árvore da direita e visitar o nó (ou vértice) atual. Abaixo o código em F#, em destaque, usando recursão para os 3 tipos de depth-first search:

5 df_traversal_code

Se for aplicado na árvore anterior, obtemos o seguinte resultado:

6 df_traversal

Como indicado anteriormente, outro modo para percorrer uma árvore é por extensão, também conhecido como percorrer a árvore por níveis ou horizontalmente. O código em C# a seguir apresenta como implementar a árvore e o breadth-first search em destaque. A versão em C# utiliza iterator para implementar o método AsBreadthFirst:

7 bf_traversal_code

Se for aplicado na árvore anterior, obtemos o seguinte resultado:

Level order traversal sequence: F B G A D I C E H

Uma vez conhecida as caracteristicas fundamentais para percorrer um árvore, vale analisar suas caracteristicas com relação ao balanceamento. As implementações das árvores apresentadas aqui até o momento são balanceadas por mera coincidência, pois sua montagem foi manual. No entanto, é possível configurarmos uma árvore não balanceada, onde todos os nós (ou vértices) estejam dispostos a extrema esquerda.

8 unbalanced_tree

A desvantagem de uma árvore não balanceada é com relação a busca, cujo no pior caso, se todos os elementos estiverem à esquerda, como no exemplo anterior, cada um destes elementos deverá ser visitado. Ou seja, o mesmo comportamento de um array não ordenado, com  a desvatagem da localidade – no caso do array todos os elementos estão contiguamente alinhados o que é bom, dado a hierarquia de memória dos computadores aos quais estamos submetidos. O balanceamento numa árvore do tipo binária, é fundamental para diminuir a complexidade de busca com relação ao tempo. Uma das técnicas mais eficientes para balanceamento de árvores que conheço é a left leaning red black tree, criada por Robert Sedgewick. Onde os nós (ou vértices) são classificados em vermelhos ou negros. Com as seguintes propriedades para balanceamento:

1)      O nó (ou vértice) raiz é negro. Bem como, todos os nós (ou vértices) nulos são negros;

2)      Todos os nós (ou vértices) vermelhos são dispostos a esquerda;

3)      Na inserção, o nó (ou vértice) é vermelho, exceto no caso da raíz;

4)      Executar em recursividade os itens a, b e c até a exaustão:

  • Quando o filho da direita for vermelho e o filho da esquerda for negro executar rotação a esquerda;
  • Quando o filho da esquerda for vermelho e o neto da esquerda for vermelho executar rotação a direita;
  • Quando ambos filhos forem vermelhos executar a troca de cores (flip). O flip consiste em tornar os dois filhos em negros e o pai em vermelho (exceto o pai raíz, ele permancerá em negro).

Apesar de intimidadora, esta técnica é bem simples. A seguir, é apresentado o balancemento de uma árvore que recebará a sequência de 1 a 10, na notação matemática de intervalo isto significa: [1, 10].

9 llrb

Imprimindo cada inserção de 1 a 10, é apresentado o conjunto das ações executadas em cada inserção e o resultado da árvore quando percorrida com breadth-first:

10 llrb_result

A seguir o código da left_leaning_red_black_bst, em C++ 11:

11 llrb_code_1

A essência da inserção de valores fica por conta do método recursive_insert que traduz as ações enumeradas anteriormente:

12 llrb_code_2

O método recursive_insert é dividido essencialmente em 2 partes: a busca para o ponto de inserção, ou seja, onde posicionar o nó (ou vértice) corretamente de acordo com o padrão de um BST, e ajustar os nós  (ou vértices) para manter as propriedades enumeradas anteriormente.

Abaixo encontram-se os métodos que detalham cada etapa operacional exigida pelo método recursive_insert:

13 llrb_code_3

E o test case do exemplo left_leaning_red_black_bst:

14 llrb_code_4

A seguir, algumas observações interessantes relacionadas a árvores, principalmente as balanceadas:

1)      Se folhar meu livro favorito sobre STL, especificamente na página 332, é indicado que a estrutura de dados interna dos tipos set, multiset, map e multimap são árvores binárias balanceadas, cujo a implementação é compartilhada entre elas. Curiosamente, na página 315 contém a informação que os tipos set e multiset utilizam como estrutura interna uma red black tree. Se esta árvore é uma LLRB vai depender do fornecedor da STL. TreeMap e TreeSet do Java também são implementadas em termos de uma red black tree. Para .NET, uma das melhores opcções para coleções não-concorrentes é a The C5 Generic Collection Library, onde existem algumas opções de red black trees.

2)      Boost tem suporte para grafos (e por tabela árvores) com a Boost Graph Library (BGL).

15 boost_graph

16 graph

3)     Existem estruturas de dados que são persistentes, ou seja, os estados anteriores não são destruídos. Isto é comum em estrutura de dados também denominadas imutáveis recentementes liberadas para a plataforma .NET e presentes em Clojure. A obra seminal, se não for pioneira no campo, Pure Functional Data Structures de Chris Okasaki explica em detalhes este tipo de estrutura de dados. Então como seria uma BST persistente?

17 persistent_bst

A medida que são inseridos os nós (ou vértices) na árvore, a referência anterior é mantida. No desenho anterior, é exibido a evolução da árvore a medida que são inseridos os itens, a aresta contínua indica que o elemento é uma cópia (valor imutável) e a aresta pontilhada uma referência.

A seguir o código em F# de um BST persistente:

18 persistent_bst_code

4)      Grafos podem ser representados como árvore. Por exemplo, o grafo conectado em forma de estrela:

19 graph_star

Pode ser expandido em uma árvore e ser percorrido como no clássico problema do caixeiro viajante ou do caminho mais curto (desde que visite todos os nós, problema exemplificado na figura abaixo):

20 brute_force_tsp

E o respectivo código em F#, usando a transformação de grafo para árvore e força bruta para encontrar a menor distância se todos os nós (ou vértices) forem percorridos:

21 graph_to_tree

5)      Sabendo que os sistemas operacionais utilizam estruturas de dados do tipo red black, fui atrás de uma aplicação real. Recentemente, investigando o código fonte do kernel do Linux (não que eu faça isto com frequência) encontrei as seguintes dependências e relações com estrutura de dados rbtree: kernel.h, rbtree_augmented.h, rbtree.h, rbtree.c e rbtree_test.c. Então, achei que seria divertido portá-la para rodar no Visual C++. Em linhas gerais, o código portado mantém todas as caracteristicas dos códigos escritos em C originalmente, porém eu precisei fazer alguns ajustes para tê-los em C++ no Windows.

22 rb_linux_1

A parte chata foi adaptar uma macro do kernel.h chamada container_of, no caso fui obrigado a usar um pequeno truque com lambda para manter o código original inalterado. O código é um pouco grande, então não vou reproduzi-lo aqui totalmente, mas ele está disponível no pacote para download deste post.

O que é interessante saber é o caso de teste:

23 rb_linux_2

E o resultado, onde podemos acompanhar a evolução da entrada de 10 nós (ou vértices) de 1 a 10:

24 rb_linux_3

A implementação encontrada no Linux, não é uma left leaning red black tree, que garante na média uma busca e uma inserção próximos de lg N (logaritmo na base 2 de N elementos). O resultado final é uma árvore não perfeitamente balanceada, mesmo assim obedecendo as caracteristicas de uma BST balanceada:

25 linux_rbtree_result

Faça o download dos códigos fontes e imagens dos exemplos e boa diversão…

Versão PDF deste Post

About Fabio Galuppo

I'm Software Engineer and Professional Trainer. I love Programming and Rock'n'Roll.
This entry was posted in C++, Computer Science, F#, Functional Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s