Estruturas de Dados - Alterando Árvores Binárias

Prévia do material em texto

Alterando Árvores Binárias
Estruturas de Dados
Profa. Carla Koike
   
Criando uma árvore binária
● Cria nó raiz
● Adiciona elementos a esquerda ou a direita
   
Adicionando Elementos em uma 
Árvore Binária
● Busque a posição na árvore onde o elemento 
seria encontrado
● Insira o elemento nessa posição, como uma 
folha
● Complexidade: O(n) no pior caso
   
...
struct tree *stree( struct tree 
*root,struct tree *r, char info)
{
  if(!r) {
    r = (struct tree *) 
malloc(sizeof(struct tree));
    if(!r) {
      printf("sem memoria\n");
      exit(0);
    }
    r­>left = NULL;
    r­>right = NULL;
    r­>info = info;
    if(!root) return r; 
/* primeira entrada na arvore*/
    if(info<root­>info)
        root­>left = r;
    else root­>right = r;
    return r;
  }
  if(info<r­>info) stree(r, r­
>left, info);
  else
    stree(r, r­>right, info);
}
#include <stdlib.h>
#include <stdio.h>
struct tree {
  char info;
  struct tree *left;
  struct tree *right;
};
struct tree *root; 
/* primeiro no da arvore */
struct tree *stree(struct tree 
*root, struct tree *r, char 
info);
void main(void)
{
  char s[80];
  root = NULL; /* inicializa a 
ra¡z */
  do {
    printf("Entre uma letra: 
");
    gets(s);
    if(!root) root = 
stree(root, root, *s);
    else stree(root, root, *s);
  } while(*s);
}
...
   
Inserindo elementos na árvore 
recursivamente:
void Insere(Registro x, Apontador *p)
{ if (*p == NULL) 
 { *p = (Apontador)malloc(sizeof(No));
 (*p)->Reg = x; 
 (*p)->Esq = NULL; 
 (*p)->Dir = NULL;
 return;
 }
 if (x.Chave < (*p)->Reg.Chave) 
 { Insere(x, &(*p)->Esq); return; }
 if (x.Chave > (*p)->Reg.Chave)
 Insere(x, &(*p)->Dir);
 else
 printf("Erro : Registro ja existe na 
arvore\n");
} 
   
Removendo Elementos em uma 
Árvore Binária, vários casos...
● Remover é mais difícil que inserir:
– o nó a ser removido pode ser uma folha, uma raiz, 
um nó esquerdo ou direito.
– a retirada da raiz pode significar buscar outra raiz 
para a árvore.
● Situações típicas: o nó a ser removido tem...
– um filho;
– dois filhos;
– nenhum filho.
   
Removendo Elementos sem filhos
● Se o nó a ser removido não tem filhos:
– o nó é simplesmente retirado, e seu pai recebe nulo 
no lugar do ponteiro para aquele filho
   
Removendo Elementos sem filhos
● Remover o nó 1: uma folha, sem filhos.
   
Removendo Elementos sem filhos
● Remover o nó 1: uma folha, sem filhos.
   
Removendo Elementos com um 
único filho
● Se o nó a ser removido tem um único filho:
– o nó é retirado e em seu lugar toda a sub­árvore 
cuja raiz é seu filho toma seu lugar: o pai do nó a 
ser retirado recebe o ponteiro do filho do nó a ser 
retirado
   
Removendo Elementos com um 
único filho
● Remover o nó 2: um único filho.
   
Removendo Elementos com um 
único filho
● Remover o nó 2: um único filho.
   
Removendo Elementos com dois 
filhos
● Se o nó a ser removido tem dois filhos, existem 
dois algoritmos de retirada, com igual resultado:
– por fusão
– por cópia
   
Remoção por fusão
● Extrai uma árvore das duas sub­árvores do nó 
a ser eliminado: essa árvore vai substituir o nó 
e seus descendentes após sua remoção
● Como fundir duas sub­árvores?
– o maior nó da sub­árvore a esquerda passa a ser 
raiz da sub­árvore a direita; OU
– o menor nó da sub­árvore a direita passa a ser a 
raiz da sub­árvore a esquerda
   
Remoção por fusão
● Remover o nó 5 significa fundir a sub­árvore 
cuja raiz é 3 e a sub­árvore cuja raiz é 7
   
Remoção por fusão
● Remover o nó 5 significa fundir a sub­árvore 
cuja raiz é 3 e a sub­árvore cuja raiz é 7
   
Remoção por fusão
● O maior nó da sub­árvore a esquerda passa a 
ser raiz da sub­árvore a direita
   
Remoção por fusão
● O maior nó da sub­árvore a esquerda passa a 
ser raiz da sub­árvore a direita
   
Remoção por fusão
● O menor nó da sub­árvore a direita passa a ser 
raiz da sub­árvore a esquerda
   
Remoção por fusão
● O menor nó da sub­árvore a direita passa a ser 
raiz da sub­árvore a esquerda
   
Desvantagens: ex. Remover o nó 15 
   
Remover o nó 15 
   
Remover o nó 15 
Altura = 4
Altura = 6!!!
   
Desvantagens: ex. Remover o nó 15 
   
Desvantagens: ex. Remover o nó 15 
   
Desvantagens: ex. Remover o nó 15 
Altura = 4
Altura = 3!!!
   
Desvantagens: 3 sub­árvores!
   
Remoção por fusão: 3 sub­árvores!
Rotação!
   
Remoção por cópia
● Se o nó a ser removido tem dois filhos:
– o nó não é retirado, mas tem seu conteúdo alterado 
pelo nó sucessor ou antecessor. Este nó é retirado, 
seguindo uma das opções de antes.
– Para encontrar o nó sucessor, desce para a sub­
árvore da direita do nó a ser retirado, e caminha até 
o final da sub­árvore esquerda. 
– Para encontrar o nó antecessor, desce para a sub­
árvore da esquerda, e caminha até o final da sub­
árvore da direita.
   
Remoção por cópia
● Remover o nó 5, significar escolher entre nó 4 ou nó 
6 como nova raiz
   
Remoção por cópia
● Escolhendo o nó 4 como nova raiz:
   
Remoção por cópia
● Escolhendo o nó 4 como nova raiz:
   
Remoção por cópia
● Escolhendo o nó 4 como nova raiz:
   
Remoção por cópia
● Escolhendo o nó 4 como nova raiz:
   
...
  if (x.Chave < (*p)­>Reg.Chave) 
  { Retira(x, &(*p)­>Esq); return; }
  if (x.Chave > (*p)­>Reg.Chave)
  { Retira(x, &(*p)­>Dir); return; }
  if ((*p)­>Dir == NULL) 
  { Aux = *p;
    *p = (*p)­>Esq;
    free(Aux);
    return;
  }
  if ((*p)­>Esq != NULL) 
  { Antecessor(*p, &(*p)­>Esq);
    return;
  }
  Aux = *p;
  *p = (*p)­>Dir;
  free(Aux);
}  
void Antecessor(Apontador q,
 Apontador *r)
{ if ((*r)­>Dir != NULL) 
  { Antecessor(q, &(*r)­>Dir);
    return;
  }
  q­>Reg = (*r)­>Reg;
  q = *r;
  *r = (*r)­>Esq;
  free(q);
} 
void Retira(Registro x, 
 Apontador *p)
{  Apontador Aux;
  if (*p == NULL) 
  { printf("Erro : Registro 
     nao esta na arvore\n");
    return;
  }
...
   
Remoção por cópia
● Se aplicado várias vezes (inserção/remoção) a 
árvore terá um dos lados maior que o outro: ou 
seja a árvore ficará desbalanceada.
● O algoritmo pode ser alterado para se tornar 
simétrico. Apesar de melhorias significativas, a 
árvore ainda se tornará desbalanceada após 
muitas operações.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36