EDB2 06 rvore Binria de Busca

Prévia do material em texto

Árvore Binária de Busca 
Árvore Binária de Busca 
Uma árvore binária de busca é uma árvore binária tal 
que: 
 
i) A raiz possui uma chave 
ii) As chaves dos nós da subárvore esquerda da raiz são 
menores que a chave da raiz. 
iii) As chaves dos nós da subárvore direita da raiz são 
maiores que a chave da raiz. 
iv) As subárvores esquerda e direita são árvores binárias 
de busca 
Árvore Binária de Busca 
40 
20 
60 
10 
15 50 30 
Set 
Jun 
Mar 
Jan Ago 
Fev 
Exemplos 
Árvore Binária de Busca 
Operações básicas: 
 
- Busca 
- Inserção 
- Remoção 
Árvore Binária de Busca 
Busca 
 
Considere S = {s1,...,sn} um conjunto de n chaves tais que 
s1 < ... < sn. 
 
Dado um valor x, verificar se x  S. 
 
Caso x = si, si  S, retornar i. 
Árvore Binária de Busca 
Qual a complexidade da busca em um lista linear? 
 
 
Qual a complexidade da busca em uma árvore binária de 
busca? 
Árvore Binária de Busca 
40 
20 
60 
10 
15 50 30 
Exemplo Busca 
 
Chaves de busca: 15, 35 
raiz 
Busca_arvbb(pont_no pt, int x, int f) 
 se (pt  ) 
 se (pt.chave = x) f  1 
 senão 
 se (x < pt.chave) 
 se (pt.esq = ) f  2 
 senão pt  pt.esq 
 senão 
 se (pt.dir = ) f  3 
 senão pt  pt.dir 
 se (f < 1) 
 Busca_arvbb(pt, x, f) 
Árvore Binária de Busca 
Algoritmo Busca 
Busca_arvbb(raiz, x, 0) 
f = 0, árvore vazia 
 
f = 1, chave encontrada e pt 
aponta para nó onde a chave 
se encontra 
 
f = 2, chave não encontrada e 
pt aponta para nó cuja árvore 
esquerda é vazia 
 
f = 3, chave não encontrada e 
pt aponta para nó cuja árvore 
direita é vazia 
Árvore Binária de Busca 
Complexidade da Busca 
 
Melhor Caso: 
Árvore Binária de Busca 
Complexidade da Busca 
 
Melhor Caso: Chave é encontrada na raiz 
Árvore Binária de Busca 
Complexidade da Busca 
 
Pior Caso: 
Oh, não! 
Árvore Binária de Busca 
Complexidade da Busca 
 
Pior Caso: Chave encontrada ou não encontrada no maior 
caminho entre a raiz e uma folha 
= 
h(T) 
Quais são os casos para h(T)? 
70 
50 
35 
25 90 65 40 
80 30 
Árvore Binária Completa 
Árvore Binária de Busca 
Árvore Zig-zag 
Árvore Binária de Busca 
50 
5 
30 
39 
32 
h(T) = n 
Árvore Binária de Busca 
Complexidade da Busca 
 
A complexidade da busca depende da altura da árvore. 
Sendo assim, é interessante construir a árvore com a 
menor altura possível. Como visto anteriormente, a árvore 
que possui altura mínima para um conjunto de n chaves é 
a árvore completa. Nesse caso, a complexidade do 
algoritmo é O(log n). 
Árvore Binária de Busca 
Inserção 
O novo nó é inserido no lugar de uma subárvore vazia. 
inserção(x, pt, f) 
 pt ← ptraiz 
 busca_árvore(x, pt, f) 
 se (f = 1) então “Elemento já existe” 
 senão 
 ocupar(pt1); pt1↑.chave ← x; pt1↑.esq = ; pt1↑.dir=  
 se (f = 0) então ptraiz ← pt1 
 senão 
 se (f = 2) então pt↑.esq = pt1 
 senão pt↑.dir = pt1 
Árvore Binária de Busca 
Inserção 
 
Complexidade? 
6 
Árvore Binária de Busca 
Inserção 
 
Complexidade? 
 
Dominada pela complexidade da busca 
Exercício 
Dada uma lista com n chaves, 
construir a árvore de busca 
binária de altura mínima 
utilizando o algoritmo de 
inserção. 
 
Qual a complexidade do seu 
método? 
Árvore Binária de Busca 
Remoção 
 
Caso 1. Deseja-se remover uma chave que está 
numa folha. 
70 
50 
35 
25 90 65 40 
80 30 
70 
50 
35 
25 90 65 
80 30 
Remoção do 40 
Árvore Binária de Busca 
Remoção 
 
Caso 2. A chave removida não é uma folha, mas 
possui uma subárvore vazia. 
70 
50 
35 
25 90 65 
80 30 
Remoção do 35 
70 
50 
25 
90 65 
80 
30 
Árvore Binária de Busca 
Remoção 
 
Caso 3. A chave removida não é uma folha e possui 
duas subárvores não vazias. 
 
Neste caso, transformar na remoção de uma folha. 
 
Isto é feito substituindo o elemento a ser removido 
pelo maior elemento da subárvore esquerda ou o 
menor da subárvore direita. 
70 
50 
35 
25 90 65 40 
80 30 
Remoção do 50 
(troca pelo 40) 
Árvore Binária de Busca 
Remoção 
 
Caso 3. A chave removida não é uma folha e possui 
duas subárvores não vazias. 
70 
40 
35 
25 90 65 
80 30 
Árvore Binária de Busca 
Remoção 
 
Complexidade? 
6 
Árvore Binária de Busca 
Remoção 
 
Complexidade? 
 
Dominada pela complexidade da busca 
Exercício 
Escrever o algoritmo de remoção 
em árvore binária de busca. 
Árvore Binária de Busca 
Comprimento de Caminho Interno 
Para buscar uma chave, sk, o algoritmo percorre um caminho da raiz 
até o nó sk. 
 
Dado um conjunto de n chaves {s1,...,sk} devemos considerar 
quantas comparações no total o algoritmo efetuará para localizar 
todas as chaves. 
 
Para cada chave sk o algoritmo fará nível(sk) comparações. 
 
O algoritmo fará comparações. 
 
Este valor é denominado comprimento do caminho interno de T, 
I(T). 
 

n
k
ksnível
1
Árvore Binária de Busca 
Comprimento de Caminho Interno 
I(T) = 1(1) + 2(2) + 3(3) + 2(4) = 22 
Número de comparações para localizar todas as chaves 
70 
50 
35 
25 90 65 
80 30 
R1 R2 
70 
50 
35 
25 90 65 
80 30 R0 
R3 
R4 R5 
R6 R7 
R8 
Árvore Binária de Busca 
Árvore com nós externos 
Comprimento de Caminho Externo 
Quando se efetua uma busca sem sucesso de uma chave sk o algoritmo 
percorre um caminho da raiz até um nó externo Rk e o número de 
comparações é nível(Rk) – 1. 
 
Assim, analogamente ao comprimento de caminho externo define-se 
comprimento de caminho externo como 
   


n
k
kRnívelTE
0
1
Árvore Binária de Busca 
Comprimento de Caminho Externo 
Árvore Binária de Busca 
R1 R2 
70 
50 
35 
25 90 65 
80 30 R0 
R3 
R4 R5 
R6 R7 
R8 
E(T) = 1(2) + 4(3) + 4(4) = 30 
Exercício 
Prove que 
E(T) = I(T) + n 
E(T) e I(T) servem para avaliar a “qualidade” da árvore binária de 
busca. 
 
Os valores I(T)/n e E(T)/(n+1) representam o número médio de 
comparações que é necessário efetuar em operações de busca com e 
sem sucesso, respectivamente, quando todas as entradas são 
equiprováveis. 
 
Exemplo: Na árvore dada como exemplo são necessárias 18/7 
comparações para localizar uma chave e 25/8 comparações para 
concluir que uma chave não se encontra na árvore. 
 
Naturalmente, deseja-se que I(T) e E(T) sejam mínimos. 
Árvore Binária de Busca 
Considere que cada chave si, i = 1, ...,n, possui probabilidade de 
acesso pi, tal que p1, p2, ..., pn, se distribuem de forma qualquer. 
 
 
Além disso, os nós externos R0, ..., Rn, possuem probabilidades 
p0’, p1’, ..., pn’. Dadas as probabilidades, deseja-se construir a 
Árvore Ótima para efetuar a busca. 
Obs. Se p1= p2= ... = pn= p0’= p1’= ...= pn’, então a árvore ótima é 
 a árvore completa. 
Frequências de Acesso Diferenciadas 
Árvore Binária de Busca 
Árvore Binária de Busca 
Busca com Sucesso 
 
São necessárias nível(sk) comparações para encontrar sk. 
 
A probabilidade de acesso a sk é pk. 
 
A contribuição deste nó é pk nível(sk). 
 
 
Para todos osnós internos tem-se: 
 
 Comprimento de Caminho 
 Interno Ponderado  

n
i
ii snívelp
1
Árvore Binária de Busca 
  


n
i
ii Rnívelp
0
, 1
Busca sem Sucesso 
Comprimento de Caminho 
Externo Ponderado 
Sua construção minimiza a expressão (c(T) é o custo da árvore) 
      


n
i
ii
n
i
ii RnívelpsnívelpTc
0
,
1
1
Árvore Ótima 
Árvore Binária de Busca 
Exemplo 
 Dados s1, s2 e s3, tais que s1 < s2 < s3 e p1 = 0,8, p2 = 0,1, p3=0,1, 
 p0’ = p1’ = p2’ = p3’ = 0 
 
- Árvore Completa - Árvore Zig-zag 
 
 
 
 
 
c(T) = 0,8(2) + 0,1(1) + 0,1(2) = 1,9 c(T) = 0,8(1) + 0,1(2) + 0,1(3) = 1,3 
s1 
s2 
s3 
s1 
s2 
s3 
      


n
i
ii
n
i
ii RnívelpsnívelpTc
0
,
1
1
Árvore Ótima 
Árvore Binária de Busca 
Considere o conjunto de chaves {s1, ..., sn} si, i = 1, ...,n. 
 
Suponha que a raiz sk da árvore ótima é conhecida. 
Árvore de Custo Mínimo 
sk 
T’ T” 
T’ → subárvore binária de busca {s1, ..., sk-1} 
T” → subárvore binária de busca {sk+1, ..., sn} 
Árvore Binária de Busca 
Lema. As subárvores de uma árvore binária de busca ótima, 
 são também ótimas. 
 
 
Prova. Se isso não ocorresse, então a substituição da subárvore não 
ótima pela ótima, resultaria em uma diminuição do custo total, o que 
é uma contradição com o fato da árvore ser ótima. Portanto, T’ e T” 
são árvores ótimas. 
Árvore de Custo Mínimo 
Árvore Binária de Busca 
- Para resolver 1, a ideia é tentar todas as O(n) alternativas. 
Árvore de Custo Mínimo 
Árvore Binária de Busca 
Questões: 
 
1. Como determinar sk? 
 
2. Como construir T’ e T”? 
- Para resolver 2, usar a recursão. 
 
Seja c(T) o custo da árvore T. 
 
É necessário encontrar uma relação entre os custos c(T), c(T’) e 
c(T”). 
 
Sabe-se que: 
 
      


n
i
ii
n
i
ii RnívelpsnívelpTc
0
,
1
1
Árvore Binária de Busca 
 
 
 
 
Chamando de: 
 li → nível(si) 
 li’ → nível(Ri) 
 T(i,j) → a árvore de busca ótima para as chaves {si+1, ..., sj}, i ≤ j. 
 T(i,i) = 0 e T(0,n) = árvore ótima final 
 c(i,j) → custo da árvore T(i,j) 
 P(i,j) → a soma das probabilidades relativas as chaves {si+1, ..., sj} 
      


n
i
ii
n
i
ii RnívelpsnívelpTc
0
,
1
1
  


j
ik
k
j
ik
k ppjiP
,
1
,
Árvore Binária de Busca 
Lema. Se sk é a raiz de T, então para i < j, tem-se: 
 
 c(i,j) = c(i, k-1) + c(k,j) + P(i,j) 
 
 
Prova: Exercício 
 
Árvore Binária de Busca 
O lema leva a recorrência: 
 
 
 c(i,i) = 0 
        jiPjkckicjic
jki
,,1,min, 

Número de pares distintos = n(n+1)/2 → O(n2) 
Árvore Binária de Busca 
Algoritmo 
Para j ← 0 até n faça 
 c[j,j] ← 0; F[j,j] ← f’j 
 
Para d ← 1 até n faça 
 para i ← 0 até n-d faça 
 j ← i + d 
 F[i,j] ← F[i,j-1] + fj + f’j 
 c[i,j] ← min { c[i,k-1] + c[k,j]} + F[i,j] 
 i < k  j 
Complexidade? 
Árvore Binária de Busca 
Algoritmo 
Para j ← 0 até n faça 
 c[j,j] ← 0; F[j,j] ← f’j 
 
Para d ← 1 até n faça 
 para i ← 0 até n-d faça 
 j ← i + d 
 F[i,j] ← F[i,j-1] + fj + f’j 
 c[i,j] ← min { c[i,k-1] + c[k,j]} + F[i,j] 
 i < k  j 
Complexidade? (n3) 
Árvore Binária de Busca 
Exemplo: j 0 1 2 3 4 
fj - 10 1 3 2 
f’j 2 1 1 1 1 
2 
- 1 
- - 1 
- - - 1 
- - - - 1 
F = 
0 
- 0 
- - 0 
- - - 0 
- - - - 0 
c = 
Árvore Binária de Busca 
Lema. Se sk é a raiz de T, então para i < j, tem-se: 
 
 c(i,j) = c(i, k-1) + c(k,j) + P(i,j) 
 
       





1
,,
1
1
1111,
k
im
mm
k
im
mmk lplppjic
   


j
km
mm
j
km
mm lplp 111
,,
1
T(i, k-1) 
T(k, j) 
contribuição 
da raiz 
Nível de sm 
em T(i,k-1) 
Árvore Binária de Busca 
    

 



1
1
,,
1
1
1,
k
im
j
km
mmmm
k
im
mmk lplplppjic
   

 



1
1 1
,
1
,
1
,, 1
k
im
j
km
m
k
im
m
j
km
mm
j
km
mm pppplp
I 
II III IV 
V VI VII VIII IX 
P(i,j) = I + VI + VII + VIII + IX 
c(i,k-1) = II + III 
c(k,j) = IV + V 
c(i,j) = c(i, k-1) + c(k,j) + P(i,j)