Árvore (estrutura de dados)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Representação simples de uma árvore binária equilibrada de altura quatro (h=3).

A Árvore é composta por 1 (um) Elemento principal chamado Raiz, que possui ligações para outros Elementos, que são denominados de Ramos ou filhos. Estes ramos levam a outros elementos que também possuem outros ramos. O elemento que não possui ramos é conhecido como Folha e/ou -terminal.

O número máximo de ramos 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 ramos.

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.

O algoritmo abaixo descreve uma travessia pré-ordem: PercursoPreordem(nó): Processa nó Para cada filho de nó (se houver) Executa recursivamente PercursoPreordem(filho)

Outra Operação, utilizada nas árvores de pesquisa é a travessia da Raiz até uma das Folhas. Essa operação tem um custo computacional proporcional ao número de níveis da árvore. O pior caso é a travessia de todos os elementos até a folha de nível mais baixo. Árvores balanceadas apresentam o melhor pior caso possível, para um certo número de Nós. O pior caso apresenta-se na árvore degenerada em que cada possui exatamente Um filho, e a árvore tem o mesmo número de níveis que de Nós, assemelhando-se a uma lista ligada.

Ver também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.