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.
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:
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:
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:
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:
Se for aplicado na árvore anterior, obtemos o seguinte resultado:
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:
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.
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].
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:
A seguir o código da left_leaning_red_black_bst, em C++ 11:
A essência da inserção de valores fica por conta do método recursive_insert que traduz as ações enumeradas anteriormente:
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:
E o test case do exemplo left_leaning_red_black_bst:
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).
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?
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:
4) Grafos podem ser representados como árvore. Por exemplo, o grafo conectado em forma de estrela:
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):
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:
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.
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:
E o resultado, onde podemos acompanhar a evolução da entrada de 10 nós (ou vértices) de 1 a 10:
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:
Faça o download dos códigos fontes e imagens dos exemplos e boa diversão…
