Estatistica

Uma árvore é composta por um conjunto de nós. Existe um nó r, denominado raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r. Esses nós raízes das sub-árvores são ditos filhos do nó pai. Nós com filhos são comumente chamados de nós internos e nós que não tem filhos são chamado de folhas, ou nós externos. Tradicionalmente, as árvores são desenhadas com a raiz para cima e folhas para baixo, ao contrário do que seria de se esperar. As figuras a seguir exemplificam os conceito da estrutura de uma árvore.

O número de filhos permitido por nó e as informações armazenadas em cada nó diferenciam os diversos tipos de árvores existentes. Em árvores binárias, cada nó tem zero, um ou dois filhos. De maneira recursiva, podemos definir uma árvore binária como sendo:

• Uma árvore vazia; ou

• Um nó raiz tendo duas sub-árvores, identificadas como a sub-árvore da direita (sad) e a sub-árvore da esquerda (sae).

Essa definição recursiva é usada na construção de algoritmos, e na verificação (informal) da correção e do desempenho. A figura a seguir ilustra a definição de árvore binária.

Além de ser manipulada facilmente, a árvore binária aperfeiçoa a alocação de memória e simplifica a implementação de operações. Podemos dividir árvores binárias em quatro tipos:

• Árvore estritamente binária.

• Árvore binária cheia;

• Árvore binária completa;

• Árvore degenerada.

Uma árvore estritamente binária é uma árvore binária em que cada nó tem 0 ou 2 filhos. Uma árvore binária cheia é uma árvore em que se um nó tem alguma sub-árvore vazia então ele está no último nível. Uma árvore completa é aquela em que se n é um nó com algumas de sub-árvores vazias, então n se localiza no penúltimo ou no último nível. Portanto, toda árvore cheia é completa e estritamente binária. E por fim, uma árvore é dita degenerada quando todos seus nós interno têm uma única sub-árvore associada.

Exemplo de árvore binária:

A figura acima ilustra uma estrutura de árvore binária. Os nós a, b, c, d, e, e f formam uma árvore binária da seguinte maneira: a árvore é composta do nó a, da sub-árvore à esquerda formada por b e d, e da sub-árvore à direita formada por c, e e f. O nó a representa a raiz da árvore e os nós b e c as raízes das sub-árvores. E por fim, os nós d,e e f são folhas da árvore.

Para descrever árvores binárias, podemos usar a seguinte notação textual: a árvore vazia é representada por <>, e árvores não vazias por < raiz sae sad>. Com essa notação, a árvore exemplifica acima pode ser representada por: <a<b<>d<><>>><c<e<><>><f<><>>>>.

Uma propriedade fundamental de todas as árvores é que só existe um caminho da raiz para qualquer nó. Com isso, pode-se definir a altura de uma árvore