TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS ESTRUTURAS DE DADOS AVANÇADAS Aula 11

TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

ESTRUTURAS DE DADOS AVANÇADASAula 11

105/08/2011 Professor Leomir J. Borba- [email protected] –http://professorleomir.wordpress.com

AgendaLaboraratorio

Implementar Listas Lineares, Pilhas e Filas.Arvores Binárias.Bibliografia


Arvores Binárias.“Há três maneiras de fazer as coisas: a maneira errada, a maneira certa e

uma Maneira melhor.” Anônimo

Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionado em três subconjuntos : Raiz da árvore - elemento inicial (único); Sub-árvore da esquerda - se vista isoladamente compõe uma outra Árvore; Sub-árvore da direita - se vista isoladamente compõe uma outra

árvore.

Esquemas em árvores são utilizados para representar estruturas hierárquicas (árvores genealógicas, campeonatos de futebol ou organizações


Arvores Binárias. Uma árvore é composta por um elemento principal chamado

raiz, que possui ligações para outros elementos, que são denominados galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O elementoque não possui galhos é conhecido como folha ou nó terminal.


Arvores Binárias. A árvore pode não ter nenhum elemento (árvore vazia). –

Recursiva

As árvores onde cada nó que não seja folha numa árvore binária e tenha sub-árvores esquerda e direita não vazias são conhecidas como árvores estritamente binária. Uma árvore estritamente binária com n folhas tem 2n - 1 nós.


Arvores Binárias. A Figura abaixo apresenta um método convencional de representação de

uma árvore. Nesta árvore, o elemento A é a raiz da árvore, a sub-árvore da esquerda é o elemento B e a da direita é representada pelo elemento C. Um nó sem filhos é chamado de folha. Sendo A a raiz de uma árvore binária e B sua sub-árvore, é dito que A é pai de B e que B é ilho de A.


Arvores Binárias. Relações - Outras relações (e conceitos) podem ser observados na figura

9.2 : B e C são filhos de A. B e C são irmãos. D e E são irmãos. H e I são irmãos. TA é a sub-árvore enraizada em A,

portanto toda a árvore. TF é a sub-árvore enraizada em F,

que contém os nós F, H e I. Nós sem Filhos são chamados de folhas,

portanto os nós D, G, H e I são folhas.


Arvores Binárias. Grau de saída de um nó

O número de Filhos de um nó é chamado de grau de saída de um nó. Por exemplo, o nó B tem grau de saída 2 e o nó C grau 1.

Caminho Um caminho da árvore é composto por uma seqüência de nós

consecutivos (n1,n ,n ,…,nk-1,nk) tal que existe sempre a relação: nj é pai de nj+1. Os k nós formam um caminho de comprimento k - 1. O comprimento entre o nó A e o nó H é 3.

Nível do nó O nível de um nó pode ser deinido como o nó raiz de nível 0. Os

outros nós têm um nível que é uma unidade a mais do que o nível do seu pai. Na árvore da figura . tem-se:

Nível 0: ANível 1: B e CNível 2: D, E e FNível 3: G, H e I


Arvores Binárias. Altura de um nó

A altura de um nó é o comprimento do maior caminho do nó até alguns de seus descendentes (são todos os nós que podem ser alcançados caminhando-se para baixo a partir do nó).

A altura de cada uma das folhas é 1, dessa forma altura de A=4, C=3, , Ee F=2 de acordo com a figura 9.2 no slide 6.

Árvore Binária Completa Uma árvore completa é uma árvore estritamente binária na

qual todas as folhas estão no mesmo nível k. Sendo k a profundidade da árvore, o número total de nós é k+1 - 1 e o número total de folhas é 2k.


Arvores Binárias. Árvores de Busca Binária

Objetivo – Facilitar procura de determinado valor. Como - A partir da raíz de sabendo a informação a ser

procurada, determina se o caminho (galho) a ser percorrido verificando se o valor procurado é maior, menor ou igual ao nó onde se esta posicionado.

Não existe uma única forma de organizar conjunto de informações em arvore de busca binária, depende da escolha do nó raiz.


Bibliografia

05/08/2011 Professor Leomir J. Borba- [email protected] –http://professorleomir.wordpress.com 11

BIBLIOGRAFIA BÁSICA

1 AZEREDO, Paulo A. Métodos de Classificação de Dados. Rio de Janeiro: Ed. Campus, 1996.

2 LAUREANO, M. Estrutura de Dados com Algoritmos e C. 1ª Ed. São Paulo: Brasport, 2008.

3 PEREIRA, Silvio do Lago. Estruturas de Dados Fundamentais – Conceitos e Aplicações. 7.ed. São Paulo: Érica, 2008.

BIBLIOGRAFIA COMPLEMENTAR

4 KOFFMANN, E.B. Objetos, Abstração, Estrutura de Dados e Projetos. 1ª Ed. Rio de Janeiro: LTC, 2008.

5 MORAES, Celso Roberto. Estruturas de Dados e Algoritmos.Uma abordagem didática. Edição revista e Ampliada. São Paulo: Editora Futura, 2003.

6 WIRTH, Niklaus. Algoritmos e estruturas de dados. Rio de Janeiro: Prentice Hall do Brasil, 1989.

7 ZIVIANI, N. Projeto de Algoritmos com implementações em Pascal e C , Editora Pioneira, 1999.

Documents

TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS ESTRUTURAS DE DADOS AVANÇADAS Aula 11