Árvores Binárias de Pesquisa
(ABP)
Prof. Luiz José Hoffmann Filho
[email protected]
Roteiro
• Definição de ABP
• Operações sobre ABP
• Análise de Complexidade de ABPs
Roteiro
• Definição de ABP
• Operações sobre ABP
• Análise de Complexidade de ABPs
Definição
• Uma árvore binária de pesquisa (ou de
busca) obedece à seguinte propriedade:
o Seja x um nó de uma ABP. Se y é o nó raiz da
sae de x, então chave[y]  chave[x]. Se y é o nó
raiz da sad de x, então chave[y] > chave[x].
Roteiro
• Definição de ABP
• Operações sobre ABP
• Análise de Complexidade de ABPs
Operações sobre ABP
• As principais operações são:
o Consulta;
o Inserção;
o Remoção.
• As operações inserção e remoção devem ser
realizadas respeitando a propriedade das ABP.
Consulta de nós (1)
• Consulta com sucesso.
• Exemplo: Na ABP abaixo, consultar os dados
referenciados pelo nó de valor 3.
4
4
1
6
3
2
5
1
7
3
Consulta de nós (2)
• Consulta sem sucesso.
• Exemplo: Na ABP abaixo, consultar os dados
referenciados pelo nó de valor 9.
4
4
1
6
3
2
5
6
7
7
Inserção de nós (1)
• Esta operação identifica a posição correta e insere.
• A ordem em que os valores são inseridos é relevante.
o Exemplo 1: Inserir os nós 14 e 15.
o Exemplo 2: Inserir os nós 15 e 14.
raiz 10
raiz 10
16
4
2
1
8
3
7
2
12
9
Exemplo 1
11
16
4
1
14
15
8
3
7
12
9
Exemplo 2
11
15
14
Inserção de nós (2)
• Exemplo: Construir uma ABP a partir da seguinte lista de
valores: 4,1,6,5,3,2 e 7.
4
1
6
3
2
5
7
Remoção de nós
• Três casos distintos a serem tratados: nó a ser
removido tem zero, um ou dois filhos.
Remoção de nós – Caso 1
• Caso 1: nodo a ser removido tem zero filhos
o Simplesmente remove o nodo
raiz 10
raiz 10
16
4
2
1
8
3
7
2
12
9
11
16
4
1
8
3
7
12
9
Após a remoção
Remoção de nós – Caso 2
• Caso 2: nodo a ser removido tem um filho
o
Substitui o nodo por seu filho
raiz 10
raiz 10
16
4
2
1
8
3
7
2
12
9
11
16
4
1
8
3
7
11
9
Após a remoção
Remoção de nós – Caso 3
• Caso 3: nodo a ser removido tem dois filhos
Substitui o nodo por seu sucessor
o
raiz 10
raiz 10
16
4
2
1
8
3
7
nodo sucessor
2
12
9
11
16
7
1
8
3
11
9
Após a remoção
Pergunta: Poderíamos ter feito a substituição pelo nodo antecessor?
Nodo Sucessor e Antecessor
• Considerando que as chaves sejam todas
distintas:
o O sucessor de um nodo x é o nodo y, tal que
chave[y] é o menor valor maior que chave[x].
o O antecessor de um nodo x é o nodo y, tal que
chave[y] é o maior valor menor que chave[x].
Roteiro
• Definição de ABP
• Operações sobre ABP
• Análise de Complexidade de ABPs
Análise de complexidade (1)
• Com relação a pesquisa  Depende da quantidade
de nós internos que eu precise visitar.
• Qual é a complexidade de uma busca com sucesso?
Depende da ordem de inserção dos nós ao construir uma ABP.
4, 6, 2, 5, 1, 7, 3
1, 2, 3, 4, 5, 6, 7
Figura 1
Figura 2
Análise de complexidade (2)
• Complexidade de uma busca sem sucesso
o Melhor Caso:
• Árvore binária perfeita: O(log n)  Figura 1
• Árvore não balanceada: O(n)  Figura 2
4, 6, 2, 5, 1, 7, 3
1, 2, 3, 4, 5, 6, 7
Figura 1
Figura 2