AEDSII_aula_021_arvores_binarias_de_pesquisa_SBB

Prévia do material em texto

Árvores binárias de pesquisa 
com balanceamento 
Algoritmos e Estruturas de Dados II 
Árvores binárias de pesquisa 
2 
}  Pior caso para uma busca é O(n) 
3 
1 
4 
5 
6 
2 
Ordem de inserção: 
1 3 2 4 5 6 
Árvore completamente balanceada 
3 
}  Nós folha (externos) aparecem em no máximo dois 
níveis diferentes 
}  Minimiza o tempo médio de pesquisa 
}  Assumindo distribuição uniforme das chaves 
}  Problema: manter árvore completamente balanceada 
após cada inserção é muito caro 
Árvore completamente balanceada 
4 
}  Para inserir a chave 1 na árvore à esquerda e manter 
a árvore completamente balanceada precisamos 
movimentar todos os nós 
Árvores “quase balanceadas” 
5 
}  Objetivo: 
}  Funções para pesquisar, inserir e retirar eficientes 
}  O(lg(n)) 
}  Solução intermediária que mantém a árvore “quase 
balanceada”, em vez de tentar manter a árvore 
completamente balanceada 
Árvores “quase balanceadas” 
6 
}  Várias formas de definir e construir uma árvore 
“quase balanceada” 
}  Exemplos de restrições aplicadas a árvores para fazê-
las “quase balanceadas” 
}  Restringir a diferença entre as alturas das subárvores de 
cada nó 
}  Minimizar o comprimento do caminho interno da árvore 
8 = 0 + 1 + 1 + 2 + 2 + 2 
Árvores SBB 
7 
}  Uma árvore SBB é uma árvore binária com 
apontadores verticais e horizontais, tal que: 
}  Todos os caminhos da raiz até cada nó externo possuem o 
mesmo número de apontadores verticais 
}  Não podem existir dois apontadores horizontais sucessivos 
Árvores SBB – estrutura 
8 
#define SBB_VERTICAL 0 
#define SBB_HORIZONTAL 1 
 
struct sbb { 
 struct registro reg; 
 struct sbb *esq; 
 struct sbb *dir; 
 int esqtipo; 
 int dirtipo; 
} 
Pesquisa em árvore SBB 
9 
}  Idêntica à pesquisa em uma árvore de busca binária 
não balanceada 
}  Ignoramos a direção dos apontadores 
Inserção numa árvore SBB 
10 
}  A chave a ser inserida é sempre inserida após o 
apontador vertical mais baixo na árvore 
}  Dependendo da situação anterior à inserção podem 
aparecer dois apontadores horizontais 
 
}  Transformação local para manter as propriedades da 
árvore SBB 
Inserção do 4, 6, 8, 11? 
Criação de um nó 
11 
struct sbb *cria_no(struct registro reg) { 
 
 struct sbb *no = malloc(sizeof(struct sbb)); 
 no->reg = reg; 
 no->esq = NULL; 
 no->dir = NULL; 
 no->esqtipo = SBB_VERTICAL; 
 no->dirtipo = SBB_VERTICAL; 
 return no; 
} 
}  Métodos para reorganizar casos onde aparecem dois 
ponteiros horizontais consecutivos 
}  Esquerda-esquerda (e direita-direita) 
}  Esquerda-direita (e direita-esquerda) 
Transformações para manter 
propriedadas da árvore SBB 
12 
Transformações para manter 
propriedadas da árvore SBB - código 
13 
void ee(struct sbb **ptr) { 
struct sbb *no = *ptr; 
struct sbb *esq = no->esq; 
 
 no->esq = esq->dir; 
 esq->dir = no; 
 esq->esqtipo = SBB_VERTICAL; 
 no->esqtipo = SBB_VERTICAL; 
 *ptr = esq; 
} 
ptr 
no esq 
x 
x 
ptr 
Transformações para manter 
propriedadas da árvore SBB - código 
14 
void dd(struct sbb **ptr) { 
struct sbb *no = *ptr; 
struct sbb *dir = no->dir; 
 
 no->dir = dir->esq; 
 dir->esq = no; 
 dir->dirtipo = SBB_VERTICAL; 
 no->dirtipo = SBB_VERTICAL; 
 *ptr = dir; 
} ptr 
1 2 3 
x 
ptr 
dir no 
x 
Transformações para manter 
propriedadas da árvore SBB - código 
15 
void ed(struct sbb **ptr) { 
struct sbb *no = *ptr; 
struct sbb *esq = no->esq; 
struct sbb *dir = esq->dir; 
 
 esq->dir = dir->esq; 
 no->esq = dir->dir; 
 dir->esq = esq; 
 dir->dir = no; 
 esq->dirtipo = SBB_VERTICAL; 
 no->esqtipo = SBB_VERTICAL; 
 *ptr = dir; 
} 
ptr 
no esq dir 
x y 
x y 
ptr 
Transformações para manter 
propriedadas da árvore SBB - código 
16 
void de(struct sbb **ptr) { 
struct sbb *no = *ptr; 
struct sbb *dir = no->dir; 
struct sbb *esq = dir->esq; 
 
 no->dir = esq->esq; 
 dir->esq = esq->dir; 
 esq->esq = no; 
 esq->dir = dir; 
 dir->esqtipo = SBB_VERTICAL; 
 no->dirtipo = SBB_VERTICAL; 
 *ptr = esq; 
} 
esq 
1 2 3 
x 
ptr dir no 
y 
ptr 
x y 
Exemplo de inserção em árvore SBB 
17 
}  Inserir chaves 7, 10, 5, 2, 4, 9, 3, 6 
Exemplo de inserção em árvore SBB 
18 
}  Inserir chaves 7, 10, 5, 2, 4, 9, 3, 6 
Inserção em árvores SBB 
19 
void iinsere(struct registro reg, struct sbb **ptr, 
 int *incli, int *fim) { 
 /* adiciona, pois encontrou uma folha */ 
 if(*ptr == NULL) 
 iinsere_aqui(reg, ptr, incli, fim); 
 
 /* busca na sub-árvore esquerda */ 
 } else if (reg.chave < *ptr->reg.chave) { 
 iinsere(reg, &(*ptr->esq), &(*ptr->esqtipo), fim); 
 if (*fim) return; 
 if (*ptr->esqtipo == SBB_VERTICAL) { 
 *fim = TRUE; 
 } else if (*ptr->esq->esqtipo == SBB_HORIZONTAL) { 
 ee(ptr); *incli = SBB_HORIZONTAL; 
 } else if (*ptr->esq->dirtipo == SBB_HORIZONTAL) { 
 ed(ptr); *incli = SBB_HORIZONTAL; 
 } 
 } 
 /* continua */ 
Inserção em árvores SBB 
20 
 /* busca na sub-árvore direita */ 
 } else if (reg.chave > (*ptr)->reg.chave) { 
 iinsere (reg, &(*ptr->dir), &(*ptr->dirtipo), fim); 
 if (*fim) return; 
 if (*ptr->dirtipo == SBB_VERTICAL) { 
 *fim = TRUE; 
 } else if (*ptr->dir->dirtipo == SBB_HORIZONTAL) { 
 dd(ptr); *incli = SBB_HORIZONTAL; 
 } else if (*ptr->dir->esqtipo == SBB_HORIZONTAL) { 
 de(ptr); *incli = SBB_HORIZONTAL; 
 } 
 
 /* chave já existe */ 
 } else { 
 printf(“erro: chave já está na árvore.\n”); 
 *fim = TRUE; 
 } 
} 
Inserção em árvores SBB 
21 
void iinsere_aqui(struct registro reg, struct sbb **ptr, 
 int *incli, int *fim) { 
 
 struct sbb *no = malloc(sizeof(struct sbb)); 
 no->reg = reg; 
 no->esq = NULL; 
 no->dir = NULL; 
 no->esqtipo = SBB_VERTICAL; 
 no->dirtipo = SBB_VERTICAL; 
 *ptr = no; 
 *incli = SBB_HORIZONTAL; 
 *fim = FALSE; 
} 
Inserção em árvores SBB 
22 
void insere(struct registro reg, struct sbb **raiz) 
{ 
 int fim = FALSE; 
 int inclinacao = SBB_VERTICAL; 
 iinsere(reg, raiz, &inclinacao, &fim); 
} 
 
void inicializa(struct sbb **raiz) 
{ 
 *raiz = NULL; 
} 
Exemplo de inserção em árvore SBB 
23 
}  Inserir a chave 5.5 na árvore a seguir 
SBBs – análise 
24 
}  Dois tipos de altura 
}  Altura vertical h: conta o número de apontadores verticais 
da raiz até as folhas 
}  Altura k: o número de ponteiros atravessados (comparações 
realizadas) da raiz até uma folha 
}  A altura k é maior que a altura h sempre que 
existirem apontadores horizontais na árvore 
}  Para qualquer árvore SBB temos hkh 2≤≤
SBBs – análise 
25 
}  Bayer (1972) mostrou que 
}  Custo para manter a propriedade SBB depende da 
altura da árvore O(lg(n)) 
}  Número de comparações em uma pesquisa com 
sucesso numa árvore SBB 
}  Melhor caso: C(n) = O(1) 
}  Pior caso: C(n) = O(lg(n)) 
}  Caso médio: C(n) = O(lg(n)) 
2221 −+≤≤+ )lg()lg( nkn
Exercícios 
26 
}  Desenhe a árvore SBB resultante da inserção das 
chaves Q U E S T A O F C I L em uma árvore vazia. 
}  Dê a lista de inserções que gera a árvore SBB abaixo: 
6 
8 5 
4 
2 
Retirada numa árvore SBB 
27 
}  Usaremos três procedimentos auxiliares 
}  EsqCurto: chamado quando o nó (referenciado por um 
apontador vertical) é retirado à esquerdae diminui a altura 
da árvore 
}  DirCurto: chamado quando um nó (referenciado por um 
apontador vertical) é retirado à direita e diminui a altura da 
árvore 
}  Antecessor: chamado quando um nó possui dois filhos 
Retirada em árvore SBB – exemplos 
28 
Retirando 7, 5 e 9: 
Retirada em árvore SBB – exemplos 
29 
Retirada em árvore SBB – exemplos 
30 
Retirada em árvore SBB – exemplos 
31 
Retirada em árvore SBB – exemplos 
32 
Retirada de árvore SBB – código 
33 
void iretira(struct registro reg, struct sbb **ptr, int *fim) 
{ 
 /* chegou a um nó vazio e não encontrou chave */ 
 if (*ptr == NULL) { 
 *fim = TRUE; 
 return; 
 } 
 /* busca na sub-árvore esquerda */ 
 if (reg.chave < *ptr->reg.chave) { 
 iretira(reg, &(*ptr->esq), fim); 
 if(!(*fim)) 
 EsqCurto(ptr, fim); 
 } 
 /* busca na sub-árvore direita */ 
 else if (reg.chave > *ptr->reg.chave) { 
 iretira(reg, &(*ptr->dir), fim); 
 if(!(*fim)) 
 DirCurto(ptr, fim); 
 } 
 /* continua */ 
Retirada de árvore SBB – código 
34 
 else { /* encontrou o registro */ 
 *fim = FALSE; 
 struct sbb *no = *ptr; 
 if (no->dir == NULL) { /* sem filho direito */ 
 *ptr = no->esq; 
 free(no); 
 if (*ptr != NULL) { *fim = TRUE; } 
 } 
 else if (no->esq == NULL) { /* sem filho esquerdo */ 
 *ptr = no->dir; 
 free(no); 
 if (*ptr != NULL) { *fim = TRUE; } 
 } 
 } else { /* com dois filhos */ 
 antecessor(ptr, &(*ptr->esq), fim); 
 if (!(*fim)) 
 EsqCurto(ptr, fim); 
 } 
 } 
} 
Retirada de árvore SBB – código 
35 
void antecessor(struct sbb **q, struct sbb **ptr, int *fim) { 
 /* busca pelo maior elemento */ 
 if (*ptr->dir != NULL) { 
 antecessor (q, &(*ptr->dir), fim); 
 if (!(*fim)) { 
 DirCurto(ptr, fim); 
 return; 
 } 
 } 
 /* encontrou o maior elemento */ 
 *q->reg = *ptr->reg; 
 q = ptr; 
 *ptr = *ptr->esq; 
 free(*q); 
 if (*ptr != NULL) 
 *fim = TRUE; 
Retirada de árvore SBB – código 
36 
void EsqCurto(struct sbb **ptr, int *fim) { 
 if (*ptr->esqtipo == SBB_HORIZONTAL) { 
 *ptr->esqtipo = SBB_VERTICAL; *fim = TRUE; 
 } else if (*ptr->dirtipo == SBB_HORIZONTAL) { 
 struct sbb *dir = *ptr->dir; 
 *ptr->dir = dir->esq; 
 dir->esq = *ptr; 
 *ptr = dir; 
 if (*ptr->esq->dir->esqtipo == SBB_HORIZONTAL) { 
 de(&(*ptr->esq)); *ptr->esqtipo = SBB_HORIZONTAL; 
 } else if (*ptr->esq->dir->dirtipo == SBB_HORIZONTAL) 
{ 
 dd(&(*ptr->esq)); *ptr->esqtipo = SBB_HORIZONTAL; 
 } 
 *fim = TRUE; 
 } else { 
 *ptr->dirtipo = SBB_HORIZONTAL; 
 if(*ptr->dir->esqtipo == SBB_HORIZONTAL) { 
 de(ptr); *fim = TRUE; 
 } else if(/* checa outro lado */) { ... } 
 }}} 
Retirada de árvore SBB – código 
37 
void DirCurto(struct sbb **ptr, int *fim) { 
 if(*ptr->dirtipo == SBB_HORIZONTAL) { 
 *ptr->dirtipo = SBB_VERTICAL; *fim = TRUE; 
 } if (*ptr->esqtipo == SBB_HORIZONTAL) { 
 struct sbb *esq = *ptr->esq; 
 *ptr->esq = esq->dir; 
 esq->dir = *ptr; 
 *ptr = esq; 
 if(*ptr->dir->esq->dirtipo == SBB_HORIZONTAL) { 
 ed(&(*ptr->dir)); *ptr->dirtipo = SBB_HORIZONTAL; 
 } else if(*ptr->dir->esq->esqtipo == SBB_HORIZONTAL) { 
 ee(&(*ptr->dir)); *ptr->dirtipo = SBB_HORIZONTAL; 
 } 
 *fim = TRUE; 
 } 
 *ptr->esqtipo = SBB_HORIZONTAL; 
 if(*ptr->esq->dirtipo == SBB_HORIZONTAL) { 
 ed(ptr); *fim = TRUE; } 
 if(*ptr->esq->esqtipo == SBB_HORIZONTAL) { 
 ee(ptr); *fim = TRUE; } 
}}}