Aula24 25 PesquisaArvoreAVL

Pesquisa em Memória Primária – Árvores AVL David Menotti Algoritmos e Estruturas de Dados I v DECOM – UFOP 6 8 3 4 z Árvore AVL   Árvore binária de busca tal que, para qualquer nó interno v, a diferença das alturas dos filhos de v é no máximo 1. Árvores AVL são balanceadas 44 2 4 17 78 32 1 2 1 48 3 88 50 62 1 1 Exemplo: números próximo dos nós são suas alturas. © David Menotti Algoritmos e Estrutura de Dados Árvores Binárias Balanceadas e AVL Inserindo os nós 30, 20, 40, 10, 25, 35 e 50 nesta ordem, teremos: 30 20 10 © David Menotti 40 25 35 50 Algoritmos e Estrutura de Dados Árvores Binárias Balanceadas e AVL Inserindo os nós 10, 20, 30, 40 e 50 nesta ordem, teremos: 10 20 30 40 50 © David Menotti Algoritmos e Estrutura de Dados Árvores Binárias Balanceadas • • • Existem ordens de inserção de nós que conservam o balanceamento de uma árvore binária. Na prática é impossível prever essa ordem ou até alterá-la. Algoritmos para balanceamentos. © David Menotti Algoritmos e Estrutura de Dados Árvores Binárias Balanceadas • • • A vantagem de uma árvore balanceada com relação a uma degenerada está em sua eficiência. Por exemplo: numa árvore binária degenerada de 10.000 nós são necessárias, em média, 5.000 comparações (semelhança com arrays ordenados e listas encadeadas). Numa árvore balanceada com o mesmo número de nós essa média reduz-se a 14 comparações. © David Menotti Algoritmos e Estrutura de Dados AVL • • • Algoritmo…

Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estrutura de Dados I – CIC102 Professor: David Menotti (menottid@gmail.com) Lista de Exercícios 03a – Algoritmos – Repetição 1) Escreva um algoritmo em PORTUGOL que imprima todos os números inteiros de 0 a 50. algoritmo L3P001; var inteiro: C; início para C de 0 até 50 faça imprima(C); fim-para fim program l3p001; var C: integer; begin for C := 0 to 50 do writeLn(C);…

Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estrutura de Dados I – CIC102 Professor: David Menotti (menottid@gmail.com) Lista de Exercícios 03b – Algoritmos – Repetição 61) Escreva um algoritmo em PORTUGOL que receba números do usuário e imprima o triplo de cada número. O algoritmo deve encerrar quando o número –999 for digitado. algoritmo L3P061; var real : N; início leia(N); enquanto ( N ≠…

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estrutura de Dados I – CIC102 Professor: David Menotti (menottid@gmail.com) Lista de Exercícios 02 – Algoritmos – Estrutura Condicional 1) Escreva um algoritmo em PORTUGOL que leia um número e o imprima caso ele seja maior que 20. algoritmo L2P01; var real: NUM; início leia(NUM); se ( NUM > 20 ) então imprima(NUM); fim-se…

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estruturas de Dados I – CIC102 Professor: David Menotti (menottid@gmail.com) Trabalho Prático 2 Listas / Filas / Pilhas Valor: 1,2 pontos (12% da nota total) Documentação em Latex: 0,1 pontos extra Data de entrega: 22/10/2008 Este trabalho prático é divido em 3 partes principais. A primeira parte está relacionada com Listas…

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Programação de Computadores I – BCC701 Professor: David Menotti (menottid@gmail.com) Lista de Exercícios 02 – Estrutura Condicional 1) Escreva um programa que leia um número e o imprima caso ele seja maior que 20. 2) Construa um programa que leia dois valores numéricos inteiros e efetue a adição; caso o resultado seja maior que 10, apresentá-lo. 3)…

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Programação de Computadores I – BCC701 Professor: David Menotti (menottid@gmail.com) UFOP – ICEB – DECOM – 1º. Sem 2012 – David Menotti 1 Lista de Exercícios 02 –Estrutura Condicional 4) Escreva um programa para determinar se um dado número N (recebido através do teclado) é POSITIVO, NEGATIVO ou NULO. N=input(“Entre com um numero: “); …

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estrutura de Dados I – CIC102 / 20091 Professor: David Menotti (menottid@gmail.com) Trabalho Prático 6 Árvores Digitais - Código Morse Valor: 0,5 pts (5% da nota total) Documentação não-Latex: -0,1 pts Impressão não Frente-Verso: -0,05 pts (não ecologicamente correto) Interface gráfica: +0,1 pts Data de entrega: 30/06/2009 …

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estruturas de Dados I – CIC102 Professor: David Menotti (menottid@gmail.com) Trabalho Prático 3 Algoritmos de Ordenação Interna Valor: 0,6 pontos (6% da nota total) Documentação não-Latex: -0,1 pontos Data de entrega: 08/11/2008 O objetivo deste trabalho é comparar o desempenho dos algoritmos de ordenação vistos em sala.…

Universidade Federal do Amazonas - UFAM Instituto de Computação ALGORITMOS E ESTRUTURAS DE DADOS II Árvore Trie Marcelo Cabral Thaíssa Gomes Raylissandra Paixão Profº César Melo Manaus-AM 15 de Abril de 2013 Resumo Problema: a tarefa deste trabalho será desenvolver um sistema capaz de ler um arquivo de texto com palavras dispostas de forma aleatória e construir um índice para as palavras…