Estrutura de Dados

Disponível somente no TrabalhosFeitos
  • Páginas : 19 (4691 palavras )
  • Download(s) : 0
  • Publicado : 10 de abril de 2014
Ler documento completo
Amostra do texto
Árvores, suas Generalizações e
Aplicações: Árvores Binárias e Árvore
de Busca

1.1 Introdução
Caros alunos,
Nesta unidade iremos iniciar nosso estudo em uma das estruturas de
dados mais importante e fundamentais na área de computação: árvore.
Árvores estão presentes nas mais variadas aplicações, apenas citando
algumas: video games, roteadores, programas peer-to-peer, algoritmos
decompreensão, em linguagens de programação. Diferentemente de
vetores e listas ligadas onde os dados estão organizados sequencialmente,
árvores

permitem

a

modelagem

de

estruturas

hierárquicas,

como

por exemplo uma árvore genealógica. Não somente a modelagem,
mas a utilização de Árvore Binária de Busca garante um desempenho
considerável com relação a estruturas sequenciais. Iniciaremos com a definição do que é árvore em computação.
Prosseguiremos com a definição de árvore binária e finalmente árvore
binária de busca.

1.2 Árvores
Existem

situações

em

que

a

informação

tem

uma

estrutura

hierárquica ou aninhada como àquelas que encontramos em árvores
genealógicas ou organogramas. Listas ligadas geralmente provêm mais
flexibilidade quevetores, entretanto são estruturas lineares e é difícil
utilizá-los para organizar uma representação hierárquica de objetos
(Drozdek, 2005).
A abstração que modela estruturas hierárquicas é chamado de árvore
e este modelo de dados está entre os mais fundamentais em ciência da
computação (Aho; Ullman, 1992).
Árvore, no contexto de ciência da computação, é uma estrutura de
dados

queherda

as

características

das

topologias

em

árvore.

Conceitualmente diferente das listas encadeadas, em que os dados se
encontram numa sequência, nas árvore os dados estão dispostos de
forma hierárquica. Na próxima seção iremos iniciar a formalização da
terminologia de árvore juntamente com diversos exemplos.

1.2.1 Terminologia Básica
Na Figura 1 é apresentada arepresentação gráfica de uma árvore
como é comumente utilizada em computação.

Figura 1 - Representação gráfica de uma árvore. A árvore acima é dita enraizada no nó
de valor 2 e possui tamanho 7. A altura da árvore é 3. Fonte: Autoria própria.

Uma árvore é estruturada como um conjunto de nós interligados.
Cada nó (representado por uma circunferência na Figura 1) contém um
campo chave que neste casoem específico são números. Além do campo
chave, cada nó possui um campo dado, que permite armazenar qualquer
tipo de informação. Cada nó pode estar ligado a uma quantidade de n
outros nós (esta quantidade depende do tipo de árvore, conforme
veremos ao longo do curso).
Além disso, existe uma relação pai e filho entre as ligações dos nós.
Aquele que está realizando a ligação é o pai, enquantoaquele que está
recebendo a ligação é o filho. Por exemplo, na Figura 1 temos que o nó 4
é pai de 5 e 3, por sua vez, os nós 5 e 3 são filhos de 4.
Seja T uma árvore qualquer. T deve satisfazer as seguintes
condições:
1. T é conexo, ou seja, todos os nós estão conectados de
alguma maneira. A partir de qualquer nó podemos caminhar
pelas ligações e podemos chegar a qualquer outro nó. Há exatamente um único caminho entre dois nós quaisquer.
Já em uma floresta (veremos a definição adiante), há no
máximo um caminho entre dois vértices, devido à não
conectividade;
2. T é acíclico, ou seja, não existe ciclos dentro da árvore. Isto
implica que entre dois nós existe apenas um único caminho. E
um simples ciclo é formado se qualquer aresta for adicionada
a T;
3. T é conexo, edeixará de ser conexo se qualquer aresta for
removida de T;
4. T é conexo, acíclico e dado que possui n nós em T, este terá
n-1 ligações.

Figura 2: Toda árvore possui nós especiais denominados de nó raiz e nós folhas.

Toda árvore é iniciada em um nó. Este nó é chamado de nó raiz. Na
Figura 2, podemos ver destacado em azul o nó raiz representado com a
chave 2. Diz-se que a árvore é...
tracking img