Árvore Binária de Busca - Análise da Complexidade do Custo

Prévia do material em texto

Árvore Binária de Busca
análise de complexidade do custo
Bruno Marques
Danielly Queiroz
UFRPE – Ciência da Computação
Revisando a ideia
1. Possui uma raiz
2. O filho esquerdo de um nó é menor do que seu pai
3. O filho direito de um nó é maior do que seu pai
4. Um nó que não tem filhos é chamado de folha
5. O nível de um nó é definido como o número de nós no caminho 
da raiz até ele
6. A altura de um nó é o número de nós do maior caminho dele até 
seus descendentes
2
Revisando a ideia - Inserção
3
1. Se a árvore estiver vazia, cria um novo nó com os dados 
satélites e define como raiz 
2. Senão, compara a chave a ser inserida com a chave do nó 
analisado
3. Se for maior insere na sub-árvore da direita
Se for menor insere na sub-árvore da esquerda
Revisando a ideia - Inserção
4
3
1
2 4
6
7
5
Exemplo:
Entrada: {3,6,1,2,4,7,5}
h
Revisando a ideia - Balanceamento
5
Para cada nó, define–se um fator de balanceamento, que deve ser 
-1, 0 ou 1. Ele é responsável por caracterizar uma árvore 
balanceada ou desbalanceada.
FB = altura(subárvore direita)– altura(subárvore esquerda)
Toda folha tem FB = 0
Revisando a ideia - Balanceamento
6
Revisando a ideia - Busca
7
1. Se a chave for igual a chave de um nó (começando pela raiz), 
retorne o nó existente 
2. a) Senão se a chave for maior, deve-se buscar na sub-árvore 
direita
b) Senão, deve-se buscar na sub-árvore esquerda
Algoritmo Árvore binária- Busca
8
Algoritmo Árvore binária- Busca
9
A análise de complexidade do custo
10
Buscar em uma árvore é verificar os nós do caminho da raiz até o nó 
desejado.
O seu pior caso, é quando buscamos um nó no último nível, ou seja, 
na “copa da árvore” ou um nó que tenha uma chave inexistente na 
árvore.
A análise de complexidade do custo
11
3
1
2 4
6
7
5
h
Suponha que a busca 
seguirá até o último nível 
de uma árvore balanceada
A análise de complexidade do custo
12
3
1
2 4
6
7
5
h
Logo, custo = O(h)
A análise de complexidade do custo
13
3
1
2
4
6
7
5
h
Detalhe:
Quando não balanceada
seu pior caso se transforma 
numa lista ordenada, tornando o 
custo igual ao da lista
A análise de complexidade do custo
14
Como calcular a altura de uma árvore com n nós?
A análise de complexidade do custo
15
1º Vamos imaginar uma árvore binária completa
Digamos que cada nó 
é um problema com 
duas opções
A análise de complexidade do custo
16
2º Montemos uma árvore recursiva que represente a ideia
“Problema” = T(n)
T(n) = T(𝑛
2
)
A análise de complexidade do custo
17
2º Montemos uma árvore recursiva que represente a ideia
Pelo algoritmo, cada nível 
tem uma verificação que 
ocorre em tempo 
constante c
T(n) = T(𝑛
2
) + c
A análise de complexidade do custo
18
3º Resolvemos a equação recursiva
a. T(n) = T(𝑛
2
) + c
b. T(𝑛
2
) = T(
𝑛
2
2
) + c + c = T(𝑛
4
) + 2c
c. T(
𝑛
4
) = T(
𝑛
4
2
) + c + c + c = T(
𝑛
8
) + 3c
d. T(i) = T(
𝑛
2𝑖
) + ic
𝑛
22
𝑛
23
𝑛
21
A análise de complexidade do custo
19
4º Pela ideia, a busca 
segue até encontrar o nó 
ou ver que na árvore não
existe a chave.
Então, acha-se o caso
base: T(1) = 1
T(1) = 1 1 1 1 1 1 1 1
A análise de complexidade do custo
20
5º Podemos concluir a árvore recursiva até o tamanho do 
subproblema chegar a 1.
T(1) = 1;
1 = 
𝑛
2𝑖
2𝑖 = n “Aplicando a propriedade do logaritmo”
i = log n
2
A análise de complexidade do custo
21
5º Podemos concluir a árvore recursiva até o tamanho do 
subproblema chegar a 1.
T(1) = 1;
T(i) = T(
𝑛
2𝑖
) + (log n)c
T(i) = 1 + (log n)c
Como i é o último nível, ou seja, maior caminho da raiz 
até a “copa da árvore”, então i = h (altura)
2
Substituindo i por log n, T(
𝑛
2𝑖
) = 1
2
2
A análise de complexidade do custo
22
6º Por fim, queríamos O(h)
O(1 + (log n)c); “Pela propriedade do O(), vemos a função que cresce mais rápido”
então O((log n)c); “Constante sai do O()”
onde cO(log n)
por fim: O(log n)
2
2
2
Dúvidas?