10_Arvore binaria de busca (BST)

Prévia do material em texto

1
Árvore Binária de Busca
1
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Árvore (Exemplo)
2
Como seria pesquisar
a localização de um arquivo no
windows explorer se não 
tivéssemos diretórios?
Para entradas realmente grandes, o acesso
linear é proibitivo!
Precisamos de alguma estrutura não-linear de 
acesso mais eficiente.
2
Árvore
3
� Estrutura não-linear com tempo de acesso em
média O(log n).
� Coleção de nós em hierarquia
� Vazia ou
� Raiz (root) e zero ou mais subárvores
� Raiz da subárvore é um nó filho do nó raiz
� A raiz de uma árvore é unica!
� Não possui ciclos
� N nós, N-1 arestas
Árvore (Ilustração)
4
raiz
...
raiz
root
3
Árvore (Ilustração)
5
raiz
...
folha (leaf)
Árvore
raiz
...
Nível 0
Nível 1
Nível k
Nível k + 1
Altura = k+1
4
Árvore
7
� Uma árvore binária é uma estrutura de dados 
caracterizada por:
� Ou não tem elemento algum (árvore vazia)
� Ou tem um elemento distinto, denominado raiz, com 
duas referências para duas estruturas diferentes, 
denominadas sub-árvore (filho) esquerda e sub-árvore 
(filho) direita
� Cada nó pode ter grau: 0, 1 ou 2
Árvore
8
� A ligação entre os nós são vistas como 
apontadores direcionados do pai para os filhos.
� Por questões de implementação, apontadores podem 
existir também dos filhos para o pai
� O número de filhos por nó diferenciam os vários 
tipos de árvores existentes.
� Propriedade fundamental: só existe um caminho 
da raiz para um outro nó da árvore.
5
Árvore
9
� A profundidade de um nó é a distância deste nó até 
a raiz. 
� Um conjunto de nós com a mesma profundidade é 
denominado nível da árvore. 
� Cada nó da árvore encontra-se em determinado 
nível. 
� A raiz encontra-se no nível zero.
� Altura de uma árvore: comprimento do caminho 
mais longo da raiz até as folhas.
� A maior profundidade de um nó, é a altura da 
árvore.
Árvore (Aplicabilidade)
10
� Representação de expressões aritméticas
� 5*3 + 4/2
+
* /
5 3 4 2
6
Exercício
11
� Qual a profundidade do 
nó 6?
� Qual a altura da árvore?
� Os nós 6 e 9 estão no 
mesmo nível? e 7 e 11?
� Qual o grau do nó 7? E 
de 9? E de 4?
Árvores Estritamente Binárias
12
� Cada nó possui grau 0 ou 2
� Quantos nós terá uma AEB com n folhas?
7
4
9 1
6
3 2
Desenhe diversas árvores
e tente deduzir.
7
Exercício
13
� A árvore a seguir é estritamente binária? Justifique.
Árvore Binária Completa
14
� Todos os níveis são completos (folhas estão no 
mesmo nível)
� Qual a relação que existe entre a altura de uma árvore 
binária completa e o número de elementos em cada nível?
� Qual a relação que existe entre a altura de uma árvore 
binária completa e o número de elementos no total?
nível 0 – nos:1 – total:1
nível 1 – nos:2 – total:3
nível 2 – nos:4 – total:7
nível 3 – nos:8 – total:15
8
Árvore Binária Completa
15
� Todos os níveis são completos (folhas estão no 
mesmo nível)
� Qual a relação que existe entre a altura de uma árvore 
binária completa e o número de elementos em cada nível?
� Qual a relação que existe entre a altura de uma árvore 
binária completa e o número de elementos no total?
nível 0 – nos:1 – total:1
nível 1 – nos:2 – total:3
nível 2 – nos:4 – total:7
nível 3 – nos:8 – total:15
h 2h 2h+1 - 1
Árvores Binárias (Percursos)
16
� Formas de percurso em árvore binárias:
� Pré-ordem (RAIZ, ESQ, DIR)
� Visita raiz
� Percorre sub-árvore esquerda em pré-ordem
� Percorre sub-árvore direita em pré-ordem
� Em-ordem (simétrica) (ESQ, RAIZ, DIR)
� Percorre sub-árvore esquerda em ordem simétrica
� Visita raiz
� Percorre sub-árvore direita em ordem simétrica
� Pós-ordem (ESQ, DIR, RAIZ)
� Percorre sub-árvore esquerda em pós-ordem
� Percorre sub-árvore direita em pós-ordem
� Visita raiz
� Applet:
� http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.ht
ml
9
Arvores binárias
17
� Impressão em pré-ordem (R,E,D):
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Arvores binárias
18
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8
10
Arvores binárias
19
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4
Arvores binárias
20
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2
11
Arvores binárias
21
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1
Arvores binárias
22
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3
12
Arvores binárias
23
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6
Arvores binárias
24
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5
13
Arvores binárias
25
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7
Arvores binárias
26
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12
14
Arvores binárias
27
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12,10
Arvores binárias
28
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12,10,9
15
Arvores binárias
29
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12,10,9,11
Arvores binárias
30
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12,10,9,11,14
16
Arvores binárias
31
� Impressão em pré-ordem:
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
8,4,2,1,3,6,5,7,
12,10,9,11,14,13
Exercício
32
� Qual a saída do caminhamento em pré ordem da 
árvore binária a seguir?
17
Arvores binárias
33
� Impressão em ordem simétrica (E,R,D):
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
1,2,3,4,5,6,7,8,9
10,11,12,13,14,15
Exercício
34
� Qual a saída do percurso em ordem da árvore 
binária a seguir?
18
Arvores binárias
35
� Impressão em pós-ordem (E,D,R):
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
1,3,2,5,7,6,4,9,11,10
13,15,14,12,8
Exercício
36
� Qual a saída do caminhamento em pós ordem da 
árvore binária a seguir?
19
Árvore Binária (Implementação)
37
� De que é composta uma árvore binária?
� Como implementar uma árvore binária?
Árvore Binária (Implementação)
38
� De que é composta uma árvore binária?
� Como implementar uma árvore binária?
public class BTNode<T> {
protected T data;
protected BTNode<T> left;
protected BTNode<T> right;
protected BTNode<T> parent;
public boolean isEmpty(){
return this.data == null;
}
//getters, setters, equals, toString
}
20
Árvore Binária (Implementação)
39
� De que é composta uma árvore binária?
� Como implementar uma árvore binária?
public interface BT<T> {
public BTNode<T> getRoot();
public boolean isEmpty();
public int height();
public BTNode<T> search(T elem);
public void insert(T value);
public void remove(T key);
public T[] preOrder();
public T[] order();
public T[] postOrder();
public int size();
}
Árvore Binária (Implementação)
40
� Como representar uma árvore vazia?
� O construtor default de BTNode já gera uma árvore
vazia?
data = null
null null
null
21
Árvore Binária (Implementação)
41
� Como representar uma árvore vazia?
� O construtordefault de BTNode já gera uma árvore
vazia?
data = null
null null
null
= NIL
O nó sentilena de 
uma árvore 
binária não 
contém dados
Árvore Binária (Implementação)
42
� Como representar uma árvore contendo apenas um 
nó?
data
NIL NIL
null
data
null
null
null null
null
null null
folha / raiz folha / raiz
22
Árvore Binária (Implementação)
43
� Como representar uma árvore contendo apenas um 
nó?
data
NIL NIL
null
data
null
null
null null
null
null null
folha / raiz folha / raiz
Árvore Binária (Implementação)
44
� Como representar uma árvore contendo apenas um 
nó?
data
NIL NIL
data
null
null null
null
null null
null
null null NIL
folha / raiz folha / raiz
23
Árvore Binária de Busca
45
� Árvore binária de busca ou árvore binária de 
pesquisa é uma árvore binária onde todos os nós 
armazenam dados comparáveis
� todos nós da sub-árvore à esquerda contêm valores 
menores do que o nó raiz
� todos os nós da subárvore à direita contêm valores 
maiores do que o nó raiz. 
� A principal utilização de árvores binárias são as 
árvores binária de busca
x
< x > x
Exemplo
46
>
>>
<
<
O quanto isso reduz o espaço da busca a cada passo?
24
Árvore Binária de Busca (Implementação)
47
� Uma BST é uma BT?
� Como implementar isso em Java?
Árvore Binária de Busca (Implementação)
48
� Uma BST é uma BT?
� Como implementar isso em Java?
public class BSTNode<T extends Comparable<T>> 
extends BTNode<T> {
}
25
Árvore Binária de Busca (Implementação)
49
� Uma BST é uma BT?
� Como implementar isso em Java?
public interface BST<T extends Comparable<T>>
extends BT<T> {
public BTNode<T> maximum();
public BTNode<T> minimum();
public BTNode<T> successor(BTNode<T> node);
public BTNode<T> predecessor(BTNode<T> node);
}
Pesquisa Binária
50
� Como saber se um dado/valor/chave está na
árvore?
� Se o nó é não-vazio
� Verifica se o dado do nó é igual à chave dada
� Se não for
� Se a chave dada for menor que o dado do nó, pesquisa na
sub-árvore a esquerda
� Senão pesquise na sub-árvore a direita
26
Pesquisa Binária (Implementação)
51
Qual o custo dos algoritmos?
Árvores Binárias
52
� A árvore binária garante busca em tempo O(n)?
27
Árvore Desbalanceada
53
� O que ocorre com a pesquisa binária se a árvore
estiver desbalanceada?
42
88
94
95
x
< x
> x
Árvore Desbalanceada
54
� O que ocorre com a pesquisa binária se a árvore
estiver desbalanceada?
42
88
94
95
O(n)
Solução: Outras árvores, como
AVL, que veremos depois.
x
< x
> x
28
Minimum
55
� Como buscar o elemento mínimo de uma BST?
� Descer pela esquerda até que um NIL seja encontrado
Maximum
56
� Como buscar o elemento máximo de uma BST?
� Descer pela direita até que um NIL seja encontrado
29
Sucessor
57
� Como buscar o sucessor de um elemento em
uma BST?
� Sucessor é a menor das chaves maiores (menor
descendente a direita)
Sucessor
58
� Como buscar o sucessor de um elemento em
uma BST?
� Sucessor é a menor das chaves maiores (primeiro
ascendente maior)
30
Predecessor
59
� Como buscar o predecessor de um elemento em
uma BST?
� Predecessor é a maior das chaves menores (maior
descendente à esquerda). Simétrico ao sucessor
Tree-Predecessor(x)
if left[x] != NIL
then return Tree-Maximum(left[x])
y = p[x]
while y != NIL and x = left[y]
do x = y
y = p[y]
return y
Predecessor
60
� Como buscar o predecessor de um elemento em
uma BST?
� Predecessor é a maior das chaves menores (primeiro
ascendente maior). Simétrico ao sucessor
Tree-Predecessor(x)
if left[x] != NIL
then return Tree-Maximum(left[x])
y = p[x]
while y != NIL and x = left[y]
do x = y
y = p[y]
return y
31
Árvore Binária (Inserção)
61
� Acontece pela raiz (admitir elementos diferentes)
� Processar apenas chaves diferentes da raiz
� Se a chave for menor, insere no filho a esquerda
� Se a chave for maior insere no filho a direita
� Inserção sempre acontece em uma nova folha
Exercício 1
62
� Insira as chaves 46, 47, 44, 45
32
Exercício 1
63
� Insira as chaves 46, 47, 44, 45
46
Exercício 1
64
� Insira as chaves 46, 47, 44, 45
46
47
33
Exercício 1
65
� Insira as chaves 46, 47, 44, 45
46
4744
Exercício 1
66
� Insira as chaves 46, 47, 44, 45
46
4744
45
34
Árvore Binária (Inserção)
67
x guarda o nó onde inserir
e
y guarda o pai
� O procedimento recebe um nó, 
mas poderia receber um valor
Árvore Binária (Inserção)
68
� O procedimento recebe um nó mas poderia receber 
V
Para que serve?
35
Árvore Binária (Inserção)
69
� O procedimento recebe um nó mas poderia receber 
V
Se a árvore é inicialmente
vazia ou então adiciona z
como filho correto de y
Árvore Binária (Inserção)
70
� O que o método a seguir faz?
XYZ(BSTNode node, T element){
if(node=NIL){
node.data = element
node.left = NIL
node.right = NIL
}else{
if(element< node.data){
XYZ(node.left, element)
}else if (element > node.data){
XYZ(node.right, element)
}
}
}
36
Árvores Binárias (Remoção)
71
� Remoções em árvores binárias:
� Se o nó y (a ser removido) for uma folha então 
remova-o. 
� Se o nó y tem apenas um filho, então ligamos o pai de 
y ao filho de y
� Se tem dois filhos então traz o sucessor de y para o 
lugar dele e remove o sucessor
12
10 14
9 11 13 15
12
10 15
9 11 13
Árvore Binária (Remoção) 
72
Tem ao máximo 1 filho
37
Árvore Binária (Remoção) 
73
Tem 2 filhos
Árvore Binária (Remoção) 
74
Guarda o filho à direita 
ou à esquerda
38
Árvore Binária (Remoção) 
75
Conecta o filho ao pai de y
(assume que não há ligações duplas
entre folhas e sentinelas)
Árvore Binária (Remoção) 
76
Se y é root então x é novo root
39
Árvore Binária (Remoção) 
77
Senão seta x sendo o filho
correto do pai de y
Árvore Binária (Remoção) 
78
Se o sucessor de z foi um 
nó diferente então copia 
o conteúdo dele para z.
40
Árvores Binárias (Remoção)
79
� Outras abordagens trabalham da seguinte forma:
� Se for folha remove
� Senão sobe o menor descendente a direita (sucessor)
� Se não existir menor descendente a direita então sobe o 
maior descendente a esquerda (predecessor)
� Remove recursivamente o nó movido.
Arvores Binárias (Remoção)
80
remover 20
41
Arvores Binárias (Remoção)
81
Arvores Binárias (Remoção)
82
remover 30
42
Arvores Binárias (Remoção)
83
remover 30
40
Arvores Binárias (Remoção)
84
remover 50
40
43
Arvores Binárias (Remoção)
85
remover 90
40
90
Arvores Binárias (Remoção)
86
40
90
100
44
Árvore Binária (Remoção)
87
XYZ(value) {
BSTNode node = search(value)
if(node != NIL){
if(node is leaf){
node = NIL
}else if (node has one child){
if node != root
if(node is left child){
if(node.left != NIL)
node.left is left child of node.parent
else
node.right is left child of node.parent
else //node is right child
if(node.left != NIL)
node.left is right child of parent
else
node.right is right child of parent 
else
root = not NIL child of root
}else{
BSTNode sucessor = sucessor(node);
node.value = sucessor.value;
XYZ(sucessor);
}
}
}
O que o metodo faz?
Árvore Binária (Percurso)
88
� Algoritmo do percurso em pré-ordem
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Como seria o algoritmo?
45
Árvore Binária (Percurso)
89
� Algoritmo do percurso em pre-ordempreOrder(BSTNode node){
if(node != NIL){
visit(node);
preOrder(node.left);
preOrder(node.right);
}
}
visit(BSTNode){
print(node.key);
}
Poderia fazer qualquer outro
processamento
Árvore Binária (Percurso)
90
� Algoritmo do percurso em ordem
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Como seria o algoritmo?
46
Árvore Binária (Percurso)
91
� Algoritmo do percurso em ordem
order(BSTNode node){
if(node != NIL){
order(node.left);
visit(node);
order(node.right);
}
}
Árvore Binária (Percurso)
92
� Algoritmo do percurso em pós-ordem
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Como seria o algoritmo?
47
Árvore Binária (Percurso)
93
� Algoritmo do percurso em pós-ordem
postOrder(BSTNode node){
if(node != NIL){
postOrder(node.left);
postOrder(node.right);
visit(node);
}
}
Árvore Binária
94
� Como seria para calcular recursivamente o tamanho
(quantidade de elementos) de uma árvore binária
1
size size
size(root) = 1 + size(left) + size(right)
48
Árvore Binária
95
� Como seria para calcular recursivamente o tamanho
(quantidade de elementos) de uma árvore binária
int size(){
return size(root)
}
int size(BSTNode node){
if(node.isEmpty)
return 0
else
return 1 + size(node.left) + size(node.right)
}
POSCOMP 2009
96
Não
necessariamente
balanceada! 
49
POSCOMP 2009
97
POSCOMP 2009
98
50
POSCOMP 2009
99
Referências
100
� Capítulo 13