terça-feira, 30 de junho de 2009

Arvores em Python

Esse não é o melhor post que eu poderia fazer, mas é o máximo que posso fazer no momento atual.

Uma das coisas que mais gosto de programar sem me preocupar com mercado, eficiência, tempo e prazos é poder estudar o que me dá na telha ... Um exemplo disso é meu frequente interesse em estruturas de dados. Eu sei que muitos não vêem utilidade em algumas coisas como pilhas de prioridade, árvores e grafos, só para citar alguns.

No dia-a-dia dos programadores comerciais, não duvido mesmo que haja a necessidade de se preocupar com isso, já que existem componentes prontos para as mais diversas atividades e problemas imagináveis. No entanto, muitos desses componentes se utilizam de um ou outro conceito de estruturas de dados. O que estou propondo hoje não é nada mais do que colar dois códigos desenvolvidos nesses últimos dias de estudo de uma estrutura interessante. A Árvore.

Árvores como Estruturas de Dados




Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore. Conceitualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

A árvore é composta por um elemento principal chamado raiz, que possui ligações para outros elementos, que são denominados de galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O elemento que não possui galhos é conhecido como folha ou nó terminal.

O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 galhos.

Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma travessia em-ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.

Minha implementação pessoa de uma árvore não é das melhores, mas no meu ponto de vista é bastante didática. Você encontra o código completo aqui: http://pastebin.ca/1470151

Continuando nosso estudo sobre árvores, vamos falar um pouco de outro tipo de árvore, que me interessou bastante, que é a Árvore AVL.

Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, a altura de dois nós folha difere no máximo em uma unidade. As operações de busca, inserção e eliminação de elementos possuem complexidade O(logn) (no qual n é o número de elementos da árvore). Inserções e eliminações podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de adição e exclusão de elementos. Para definir o balanceamento é utilizado um fator específico para nós.

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

A minha implementação de uma árvore AVL se deu inicialmente do código da primeira árvore citada no início. No entanto, devido à problemas de performance, eu preferi começar implementando uma árvore binária normal e em seguida adicionar o suporte à rotação dos nós para balanceamento da mesma. O código você pode encontrar aqui: http://pastebin.ca/1470156

Atualmente eu não tenho utilizado as mesmas para nenhum propósito específico. O meu objetivo com a construção dessas duas estruturas foi meramente didático, como prova de que eu podia facilmente implementar uma dessas na linguagem, já que me falaram que "no Python, por não ter ponteiros, fica mais difícil de pensar em estruturas de dados mais avançadas". E é aí que discordo, pois sem me preocupar com alocação de memória, e com o suporte à orientação à objetos, programar estruturas de dados mais avançadas, como estas, fica muito mais fácil e intuitivo, como você puderam ver pelo código das mesmas. Vá ver uma implementação de Árvores AVL em C/C++ e venha conversar comigo.

Abração.

Referências:

Árvores (Wikipédia)
Árvores AVL (Wikipédia)