Arvore avl

5073 palavras 21 páginas

Árvores AVL

Letícia Rodrigues Bueno

27 de maio de 2012

Relembrando: árvores binárias de busca

Objetivo: minimizar tempo de acesso no pior caso.

Relembrando: árvores binárias de busca

Objetivo: minimizar tempo de acesso no pior caso. Idéia: Para cada chave, separe as restantes em maiores ou menores.

Relembrando: árvores binárias de busca

Objetivo: minimizar tempo de acesso no pior caso. Idéia: Para cada chave, separe as restantes em maiores ou menores. Estrutura hierárquica com divisão binária: uma árvore binária.

Relembrando: árvores binárias de busca

Objetivo: minimizar tempo de acesso no pior caso. Idéia: Para cada chave, separe as restantes em maiores ou menores. Estrutura hierárquica com divisão binária: uma árvore binária.

3 1 2 4 5 6 7

Relembrando: complexidade da busca em árvore binária

Busca em árvore binária = caminho da raiz até chave desejada (ou até uma folha, caso chave não exista).

3 1 2 4 5 6 h 7

Relembrando: complexidade da busca em árvore binária

Busca em árvore binária = caminho da raiz até chave desejada (ou até uma folha, caso chave não exista).

3 1 2 4 5
Pior caso: maior caminho da raiz até folha

6 h 7

Relembrando: complexidade da busca em árvore binária

Busca em árvore binária = caminho da raiz até chave desejada (ou até uma folha, caso chave não exista).

3 1 2 4 5
Pior caso: maior caminho da raiz até folha = altura da árvore

6 h 7

Relembrando: complexidade da busca em árvore binária

Busca em árvore binária = caminho da raiz até chave desejada (ou até uma folha, caso chave não exista).

3 1 2 4 5
Pior caso: maior caminho da raiz até folha = altura da árvore Complexidade pior caso: O (h)

6 h 7

Relembrando: complexidade da busca em árvore binária

Busca em árvore binária = caminho da raiz até chave desejada (ou até uma folha, caso chave não exista).

3 1 2 4 5
Pior caso: maior caminho da raiz até folha = altura da árvore Complexidade pior caso: O (h)

Relacionados

Arvore avl
668 palavras | 3 páginas

UNIVERSIDADE PRESIDENTE ANTÔNIO CARLOS – UNIPAC SISTEMAS DE INFORMAÇÃO GEOVANE ALVES DE CARVALHO ALISON DE OLIVEIRA SILVA aRVORE AVL IPATINGA – MG 2011 GEOVANE ALVES DE CARVALHO ALISON DE OLIVEIRA SILVA aRVORE bINÁRIA Trabalho apresentado ao Professor Filipe Costa Fernandes, da disciplina Estruturas de Dados II, da turma SINF3, turno noturno, do curso de Sistema de Informação UNIVERSIDADE PRESIDENTE ANTÔNIO CARLOS IPATINGA - 2011….

exibir mais
Arvore avl
840 palavras | 4 páginas

h> #include <stdlib.h> /* Estruturas para uma arvore de inteiros. */ typedef struct _no { int chave; /* Chave para busca */ int bal; /* Indicacao sobre balanceamento: */ /* -1 se esq. maior, 0 se balanceado, 1 se dir maior */ /* Outros campos de dados aqui */ struct _no *esq, *dir; /*Ponteiros para sub-arvores esq e direita*/ } no; /* Inicializa a arvore (NULL)*/ void inicializa(no **r) { (*r) = NULL; } /* Busca x em uma arvore binaria de busca. */ no *busca(int x, no *raiz) { while….

exibir mais
Árvore AVL
5925 palavras | 24 páginas

Comandos da Linguagem Clipper 5.2 ?/?? Propósito: Mostrar um ou mais valores na console (vídeo) ou impressora. Sintaxe: ?/?? Lista de expressões Exemplo: CLEAR / / limpa a tela ? “Exemplo do comando ?” / / exibe a informação no video ? date ( ) / / exibe a data ( nova linha ) ?” a data de hoje é..:” ?? date ( ) / / exibe na mesma posição anterior do cursor @... BOX Propósito: Construir um box (caixa) na tela. Sintaxe: @ Lin….

exibir mais
Arvore AVL
462 palavras | 2 páginas

#include "arvoreAVL.h" int altura(No* pRaiz) { if (pRaiz == NULL) return 0; int hesquerda = altura(pRaiz->esquerda); int hdireita = altura(pRaiz->direita); if(hesquerda > hdireita) { return hesquerda + 1; } else { return hdireita + 1; } } No* criarArvore(int elemento, No* esquerda, No* direita) { No* n = (No*) malloc (sizeof(No)); n->elemento = elemento; n->balancear = altura(direita) - altura(esquerda); n->esquerda = esquerda; n->direita =….

exibir mais
arvore avl
805 palavras | 4 páginas

Intolerância e racismo no futebol: a racialização do outro Em qualquer lugar do mundo onde um grupo de pessoas grande ou pequeno estiver reunido vai existir o preconceito e o racismo, seja por cor de pele, por etnia, por estilo do cabelo, por gosto musical, pelo jeito de se vestir ou pelo time de futebol. Poderíamos passar o dia aqui, escrevendo as diferenças entre as pessoas em que, talvez, resultariam em racismo. Bom, antes de continuarmos, vamos entender o que nos diferencia dos animais….

exibir mais
Arvore AVL
405 palavras | 2 páginas

preOrdem(raiz->FilhoEsq); preOrdem(raiz->FilhoDir); } } void inOrdem(tipo_arvore *Arvore) { if(Arvore != NULL) { inOrdem(Arvore->FilhoEsq); printf ("%d\n", Arvore->Dado); inOrdem(Arvore->FilhoDir); } } void posOrdem(tipo_arvore *Arvore) { if(Arvore != NULL) { posOrdem(Arvore->FilhoEsq); posOrdem(Arvore->FilhoDir); printf ("%d\n", Arvore->Dado); } } /* * */ int main(int argc, char** argv) {….

exibir mais
Arvore avl c++
1024 palavras | 5 páginas

Lista de Exercícios– Estruturas de Dados 1. Tente construir uma árvore com base nas informações abaixo:  O nodo C tem grau 3.  O nodo X é neto de C e filho de B.  O avô de B é A.  O nodo A tem altura 0 e T tem altura 1.  Os antepassados de P são A,T e K, que são também antepassados de H.  T tem grau 2, e um dos seus filhos é o nodo S.  O nodo G tem 2 sub-árvores que são netos de C.  D é irmão de G, que é uma folha.  E e F tem graus 0 e 1 respectivamente e são também netos do nodo C.  O….

exibir mais
Código de Árvore AVL
1448 palavras | 6 páginas

/* Árvore AVL Autor: Andrei Toledo Matrícula: 1011100003 e-mail: andreieu@hotmail.com Instruções de compilação e execução do programa no arquivo LEIA-ME.TXT anexado junto a esse arquivo. Arquivo arvore.c */ #include typedef struct sInfo{//Estrutura da informação contida no nó int cod; //variável do dado } info; typedef struct sNo{//Estrutura do nó struct sNo *dir, *esq, *pai; //ponteiros para os nós da direita, esquerda e pai info *dado; //ponteiro para o dado } no; no *criarNo….

exibir mais
Avl - arvore binaria
755 palavras | 4 páginas

Relat´rio Arvore Bin´ria AVL o ´ a Carlos Eduardo Domingues e Rafael Dantas 28/9/2012 Cap´ ıtulo 1 Inser¸˜o ca 1.1 Problema: Obtenha uma ´rvore AVL atrav´s da inser¸˜o da seguinte sequˆncia de valores: 14, 17, 11, 7, 53, a e ca e 4, 13, 12, 10 Inserindo: 1) 14, 17, 11, 7, 53; Para inserir esses 5 valores n˜o foi necess´rio efetuar nenhuma rota¸˜o, pois a diferen¸a entre a a a ca c altura do lado esquerdo e altura direita est´ entre -1 e 1, dif : [−1, 1]. a Figura 1.1: Inserindo….

exibir mais
Arvore avl
7567 palavras | 31 páginas

Student – Camilo Lopes School – skill /book – skill plus one Curso Inglês – English UNIT 1 Aula 1 – one 04/08/07 Study – pg 5,6,7 Audio – C pg.5 Declaration Paul in Make, to Paul in Robert Tom in Vicent Paul and Mike Paul and Robert Tom and Vicent Gettings Good morning Good afternoon Good night Dialog Teacher: - Marcelo, this is Thais ( Marcelo essa é thais.) - Thais, this is Marcelo. Marcelo:- Pleased to meet you Thais – (prazer conhecer você thais) Thais: - pleased to meet you too, Marcelo….

exibir mais

Outros Trabalhos Populares