Pesquisa em Memória Primária (cont.) Livro "Projeto de Algoritmos" – Nívio Ziviani Capítulo 5 http://www2.dcc.ufmg.br/livros/algoritmos/
#1
Pesquisa em Memória Primária (cont.) Livro "Projeto de Algoritmos" – Nívio Ziviani Capítulo 5 http://www2.dcc.ufmg.br/livros/algoritmos/
#2
Árvores Binárias de Pesquisa Com Balanceamento Árvore completamente balanceada ⇒ nós externos aparecem em no máximo dois níveis adjacentes. Minimiza tempo médio de pesquisa para uma distribuição uniforme das chaves, onde cada chave é igualmente provável de ser usada em uma pesquisa. Contudo, custo para manter a árvore completamente balanceada após cada inserção é muito alto. Algoritmos e Estrutura de Dados II
#3
Árvores Binárias de Pesquisa Com Balanceamento Para inserir a chave 1 na árvore do exemplo à esquerda e obter a árvore à direita do mesmo exemplo é necessário movimentar todos os nós da árvore original. Algoritmos e Estrutura de Dados II
#4
Uma Forma de Contornar este Problema Procurar solução intermediária que possa manter árvore "quase-balanceada", em vez de tentar manter a árvore completamente balanceada. Objetivo: Procurar obter bons tempos de pesquisa, próximos do tempo ótimo da árvore completamente balanceada, mas sem pagar muito para inserir ou retirar da árvore. Heurísticas: existem várias heurísticas baseadas no princípio acima. Algoritmos e Estrutura de Dados II
#5
Uma Forma de Contornar este Problema Gonnet e Baeza-Yates (1991) apresentam algoritmos que utilizam vários critérios de balanceamento para árvores de pesquisa, tais como restrições impostas: na diferença das alturas de subárvores de cada nó da árvore, na redução do comprimento do caminho interno ou que todos os nós externos apareçam no mesmo nível. Arvores SBB: todos nos externos aparecem no mesmo nivel Algoritmos e Estrutura de Dados II
#6
Uma Forma de Contornar este Problema Comprimento do caminho interno: corresponde à soma dos comprimentos dos caminhos entre a raiz e cada um dos nós internos da árvore. Por exemplo, o comprimento do caminho interno da árvore à esquerda na figura da transparência anterior é 8 = (0 + 1 + 1 + 2 + 2 + 2). Algoritmos e Estrutura de Dados II
#7
Algoritmos e Estrutura de Dados II Árvores SBB Árvores B : estrutura para memória secundária (Bayer R. e McCreight E. M., 1972) Árvore 2-3 : caso especial de árvore B Cada nó tem duas ou três subárvores Mais apropriada para memória primária
#8
Algoritmos e Estrutura de Dados II Árvores SBB Exemplo: Uma árvore 2-3 e a árvore B binária correspondente (Bayer, R. 1971)
#9
Algoritmos e Estrutura de Dados II Árvores SBB Árvore 2-3: árvore B binária (assimetria inerente) 1 - Apontadores à esquerda apontam para um nó no nível abaixo. 2 - Apontadores à direita podem ser verticais ou horizontais Eliminação da assimetria nas árvores B binárias: árvores B binárias simétricas (Symmetric Binary B-trees – SBB) Árvore SBB é uma árvore binária com 2 tipos de apontadores: verticais e horizontais, tal que: 1 – todos os caminhos da raiz até cada nó externo possuem o mesmo número de apontadores verticais , e 2 – não podem existir dois apontadores horizontais sucessivos.
#10
Algoritmos e Estrutura de Dados II Árvores SBB
#11
Algoritmos e Estrutura de Dados II Transformações para Manutenção da Propriedade SBB O algoritmo para árvores SBB usa transformações locais no caminho de inserção ou retirada para preservar o balanceamento. A chave a ser inserida ou retirada é sempre inserida ou retirada após o apontador vertical mais baixo na árvore Dependendo da situação anterior à inserção ou retirada, podem, aparecer dois apontadores horizontais sucessivos Neste caso: é necessário realizar uma transformação
#12
Algoritmos e Estrutura de Dados II Transformações para Manutenção da Propriedade SBB Transformações propostas por Bayer R. 1972
#13
Algoritmos e Estrutura de Dados II Estrutura de Dados Árvore SBB para Implementar o TAD Dicionário #include #include #include #define TRUE 1 #define FALSE 0 #define max 10 typedef int TipoChave; typedef struct Registro { /* outros componentes */ TipoChave Chave; } Registro;
#14
Algoritmos e Estrutura de Dados II Estrutura de Dados Árvore SBB para Implementar o TAD Dicionário typedef enum { Vertical, Horizontal } Inclinacao; typedef struct No* Apontador; typedef struct No { Registro Reg; Apontador Esq, Dir; Inclinacao BitE, BitD; } No;
Algoritmos e Estrutura de Dados II Procedimentos para Inserir na Árvores SBB void Insere(Registro x, Apontador *Ap) { short Fim; Inclinacao Iap; IInsere(x, Ap, &IAp, &Fim); }
#18
Algoritmos e Estrutura de Dados II Procedimentos para Inserir na Árvores SBB void IInsere(Registro x, Apontador *Ap, Inclinacao *IAp, short *Fim) { if (*Ap == NULL) { *Ap = (Apontador)malloc(sizeof(No)); *IAp = Horizontal; (*Ap)->Reg = x; (*Ap)->BitE = Vertical; (*Ap)->BitD = Vertical; (*Ap)->Esq = NULL; (*Ap)->Dir = NULL; *Fim = FALSE; return; }
#19
Algoritmos e Estrutura de Dados II Procedimentos para Inserir na Árvores SBB if (x.Chave < (*Ap)->Reg.Chave) { IInsere(x, &(*Ap)->Esq, &(*Ap)->BitE, Fim); if (*Fim) return; if ((*Ap)->BitE != Horizontal) { *Fim = TRUE; return; } if ((*Ap)->Esq->BitE == Horizontal) { EE(Ap); *IAp = Horizontal; return; } if ((*Ap)->Esq->BitD == Horizontal) { ED(Ap); *IAp = Horizontal; } return; }
#20
Algoritmos e Estrutura de Dados II Procedimentos para Inserir na Árvores SBB if (x.Chave <= (*Ap)->Reg.Chave) { printf("Erro: Chave ja esta na arvore\n"); *Fim = TRUE; return; } IInsere(x, &(*Ap)->Dir, &(*Ap)->BitD, Fim); if (*Fim) return; if ((*Ap)->BitD != Horizontal) { *Fim = TRUE; return; } if ((*Ap)->Dir->BitD == Horizontal) { DD(Ap); *IAp = Horizontal; return; } if ((*Ap)->Dir->BitE == Horizontal) { DE(Ap); *IAp = Horizontal; } }
Comments