Estrutura de Dados

Á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 de compreensã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 que vetores, 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 que

herda

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 a