sábado, 12 de dezembro de 2009

Árvores Genéricas



O conceito de árvore genérica é simples, porém de grande importância para aqueles que estão se aprofundando no mundo da de TI. Em diversas faculdades, tal conceito é estudado em matérias como Estrutura de Dados, Linguagem de Programação e afins.

Enfim, o conceito de árvores genéricas é baseado no conceito das árvores genealógicas das famílias da nobreza européia, onde um rei possuísse apenas um filho, o primogênito, este seria o príncipe. Caso este viesse ter mais um filho, este seria, e irmão do primogênito, seria o primeiro infante. Caso o rei voltasse a ter outro filho, este seria irmão do primeiro infante, o segundo infante, e assim sucessivamente.

Pensando isso na forma de um algoritmo, teríamos uma estrutura, pessoal, e teríamos por vez as entidades Pai (o rei do exemplo) e filhos (o príncipe e o infante, que seguiriam uma lógica semelhante a do o diagrama abaixo:


Cada nó, ou seja, cada entidade, irá seguir uma estrutura, como a que é exposta logo abaixo:

Um detalhe muito importante entre as árvores genealógicas das famílias européias e as árvores genéricas da programação, é que na programação o infante ao nascer, toma o lugar do príncipe, se tornando filho do rei e o príncipe se torna seu irmão. O segundo infante ao nascer, toma o lugar o primeiro infante, se tornando filho do rei. O primeiro infante é irmão do segundo. O príncipe é então irmão do primeiro infante.

Outros detalhes que merecem ser considerados. As arvores genéricas podem ser nulas! Afinal, um rei com filho nulo é um rei sem filhos, certo? Outro detalhe é que na pratica cada nó da árvore genérica é tratado como se fosse uma árvore em si.

Vejamos um exemplo. Tendo a árvore:
Criaremos os objetos:

A1= cria(a)
A2=cria(b)
A3=cria(c)
A4=cria(d)

Que seriam os itens:


Iríamos começar a inserção da seguinte maneira:

Tendo a função de inserir o seguinte espelho:

Inserir (nó raiz, pai)

Então

Inserir (a4,a1)


assim:


Em seguida iríamos inserir a3:

Inserir (a3, a1)



Por fim a4:

Ins
erir (a4, a1)



Assim o valor de prim de a1 é atualizado a cada inserção.