1 Árvores Binárias de Pesquisa (ABP)Prof. Luiz José Hoffmann Filho

2 Roteiro Definição de ABP Operações sobre ABPAnálise de Complexidade de ABPs

3 Roteiro Definição de ABP Operações sobre ABPAnálise de Complexidade de ABPs

4 Definição Uma árvore binária de pesquisa (ou de busca) obedece à seguinte propriedade: 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].

5 Roteiro Definição de ABP Operações sobre ABPAnálise de Complexidade de ABPs

6 Operações sobre ABP As principais operações são:Consulta; Inserção; Remoção. As operações inserção e remoção devem ser realizadas respeitando a propriedade das ABP.

7 Consulta de nós (1) Consulta com sucesso.Exemplo: Na ABP abaixo, consultar os dados referenciados pelo nó de valor 3.

8 Consulta de nós (2) Consulta sem sucesso.Exemplo: Na ABP abaixo, consultar os dados referenciados pelo nó de valor 9.

9 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. Exemplo 1: Inserir os nós 14 e 15. Exemplo 2: Inserir os nós 15 e 14. 12 16 10 9 1 7 2 8 4 3 raiz 11 12 16 10 9 1 7 2 8 4 3 raiz 11 14 15 15 14 Exemplo 1 Exemplo 2

10 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.

11 Remoção de nós Três casos distintos a serem tratados: nó a ser removido tem zero, um ou dois filhos.

12 Remoção de nós – Caso 1 Caso 1: nodo a ser removido tem zero filhosSimplesmente remove o nodo 12 16 10 9 1 7 2 8 4 3 raiz 11 12 16 10 raiz 9 1 7 2 8 4 3 Após a remoção

13 Remoção de nós – Caso 2 Caso 2: nodo a ser removido tem um filhoSubstitui o nodo por seu filho 12 16 10 9 1 7 2 8 4 3 raiz 11 11 16 10 raiz 9 1 7 2 8 4 3 Após a remoção

14 Remoção de nós – Caso 3 Caso 3: nodo a ser removido tem dois filhosSubstitui o nodo por seu sucessor 16 10 9 1 7 2 8 4 3 raiz 11 12 11 16 10 raiz 9 1 2 8 7 3 Após a remoção nodo sucessor Pergunta: Poderíamos ter feito a substituição pelo nodo antecessor?

15 Nodo Sucessor e AntecessorConsiderando que as chaves sejam todas distintas: O sucessor de um nodo x é o nodo y, tal que chave[y] é o menor valor maior que chave[x]. O antecessor de um nodo x é o nodo y, tal que chave[y] é o maior valor menor que chave[x].

16 Roteiro Definição de ABP Operações sobre ABPAnálise de Complexidade de ABPs

17 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. Figura 1 Figura 2 4, 6, 2, 5, 1, 7, , 2, 3, 4, 5, 6, 7

18 Análise de complexidade (2)Complexidade de uma busca sem sucesso Melhor Caso: Árvore binária perfeita: O(log n)  Figura 1 Árvore não balanceada: O(n)  Figura 2 Figura 1 Figura 2 4, 6, 2, 5, 1, 7, , 2, 3, 4, 5, 6, 7