2-ABB

Prévia do material em texto

Estruturas de Dados
Lineares
Lista	
Estática (com array)
Dinâmica (encadeada)
Filas, Pilhas, Deque
Hierárquicas
Árvores
Árvores Binárias
Árvores Binárias de Busca
Árvores Binárias de Busca Balanceada
Árvores B
Elements [ ] 
	null	null	null	null	null
capacity
next
next
next
next
O1
next
O2
O3
O4
O0
head
Estática (Lista com Array)
Dinâmica (Lista Encadeada)
Listas
Variações de Listas Encadeadas
next
previous
O0
next
previous
O1
next
previous
O2
next
previous
O3
next
previous
O4
Listas Duplamente Encadeada Circular
head
next
previous
O0
next
previous
O1
next
previous
O2
next
previous
O3
next
previous
O4
Listas Duplamente Encadeada
head
next
next
next
next
next
Listas Encadeada Circular
O1
O2
O3
O4
O0
head
3
next
next
next
next
O1
next
O2
O3
O4
O0
front
rear
Filas
next
next
next
next
O1
next
O2
O3
O4
O0
top
Pilhas
Tipos Especiais de Listas
inserção
remoção
remoção
inserção
Árvores
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Árvores (definições)
Toda árvore possui um único nó raiz
Todo nó (exceto o nó raiz) possui um único pai
Um nó pode ter um número arbitrário de filhos
Nós que não possuem filhos são chamados de nós folha
Nós que possuem o mesmo pai são chamados de irmãos
Relações do tipo avô, neto e primos podem ser definidas de forma similar 
 
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Pai(A,B)
Pai(D,H)
Irmão(D,E)
Primo(H,I)
Avô(A,I)
raiz
folha
folha
folha
folha
folha
folha
folha
folha
folha
folha
Árvores (mais definições)
Uma árvore é uma coleção de N nós e N-1 arestas.
O caminho do nó n1 até o nó nk é definido como a sequência dos nós n1, n2,...,nk de tal forma que ni é pai de ni+1 para 1≤i ≤k
O comprimento de um caminho é igual ao número de arestas entre os nós extremos 
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Caminho(A,Q)=A,E,J,Q
Comprimento(Caminho(A,Q))=3
Comprimento(Caminho(A,A))=0
Árvores (mais definições)
A profundidade de um nó ni é o comprimento do único caminho entre o nó raiz e o nó ni (a profundidade do nó raiz é 0)
A altura de um nó ni é o comprimento do maior caminho entre o nó ni e um nó folha (a altura dos nós folhas é 0)
A altura de uma árvore é igual a altura do nó raiz
A profundidade de uma árvore é igual a maior profundidade entre os nós folhas
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Profundidade(A)=?
Profundidade(E)=?
Profundidade(J)=?
Profundidade(P)=?
Altura(A)=?
Altura(E)=?
Altura(J)=?
Altura(P)=?
Árvores (mais definições)
A profundidade de um nó ni é o comprimento do único caminho entre o nó raiz e o nó ni (a profundidade do nó raiz é 0)
A altura de um nó ni é o comprimento do maior caminho entre o nó ni e um nó folha (a altura dos nós folhas é 0)
A altura de uma árvore é igual a altura do nó raiz
A profundidade de uma árvore é igual a maior profundidade entre os nós folhas
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
Profundidade(A)=0
Profundidade(E)=1
Profundidade(J)=2
Profundidade(P)=3
Altura(A)=3
Altura(E)=2
Altura(J)=1
Altura(P)=0
Árvores de Busca Binária
Árvores Binárias
Definição
Uma árvore binária é uma coleção de zero ou mais elementos. Para árvores binárias não vazias, a árvore é formada por um nó especial (raiz) e zero, uma ou duas sub-árvores binárias. Cada sub-árvore possui uma ligação direta com o nó raiz.
Raiz
AE
AD
Árvore de Busca Binária
Uma importante aplicação de árvores binárias é o processo de busca.
Uma árvore binária de busca possui a seguinte propriedade:
Para qualquer elemento X na árvore:
 os elementos na sub-árvore esquerda são menores que X
 os elementos na sub-árvore direita são maiores que X. 
6
8
2
4
3
1
6
8
2
4
3
1
7
Árvore Binária de Busca
Árvore Binária
<6
>6
<2
>2
<4
<6
12
Operações em Árvore de Busca Binária
Esvaziar a árvore
Testar se a árvore está vazia
Procurar um elemento na árvore
Procurar o menor elemento na árvore
Procurar o maior elemento na árvore
Inserir um elemento na árvore
Remover um elemento da árvore
Imprimir a árvore
13
Especificação do TAD Árvore de Busca Binária
class BinarySearchTree {
BinarySearchTree( )
 // Efeito: Inicializa this como uma arvore vazia de Objects
void clear( )
 // Efeito: Esvazia a árvore
bool isEmpty( )
 // Efeito: testa se a árvore está vazia
bool find(x)
 // Efeito :Retorna o elemento true caso x esteja na árvore e false, caso contrário
int findMin( )
 // Efeito: Retorna o elemento com o menor valor na árvore
int findMax( )
 // Efeito: Retorna o elemento com o maior valor na árvore 
void insert(x)
 // Efeito: Insere um nó com o elemento x na árvore
void remove(x)
 // Efeito: Remove o nó contendo o elemento x na árvore
void print( ) 
 // Efeito: Imprime os elementos da árvore em ordem crescente
}
14
Criação de Árvores de Busca Binária
MinhaABB
root
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	
	
	
	return 0;
}
15
Inserção em Árvores de Busca Binária
MinhaABB
root
6
L
R
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	MinhaABB.insert(6);
	
	return 0;
}
16
Inserção em Árvores de Busca Binária
MinhaABB
root
6
L
R
8
L
R
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	MinhaABB.insert(6);
 	MinhaABB.insert(8);
	
	return 0;
}
17
Inserção em Árvores de Busca Binária
MinhaABB
root
6
L
R
8
L
R
2
L
R
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	MinhaABB.insert(6);
 	MinhaABB.insert(8);
	
	MinhaABB.insert(2);
	return 0;
}
18
Inserção em Árvores de Busca Binária
MinhaABB
root
6
L
R
8
L
R
2
L
R
4
L
R
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	MinhaABB.insert(6);
 	MinhaABB.insert(8);
	
	MinhaABB.insert(2);
 MinhaABB.insert(4);
	return 0;
}
19
6
8
2
4
3
1
MinhaABB
root
Busca em Árvores Binárias (Mínimo)
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	...
	MinhaABB.findMin()
	return 0;
}
20
Busca em Árvores Binárias (Máximo)
6
8
2
4
3
1
MinhaABB
root
int main(int argc, char** argv) {
	BinarySearchTree MinhaABB=BinarySearchTree();
 	...
	MinhaABB.findMax()
	return 0;
}
21
Remoção em Árvore de Busca Binária
Caso 1 – O nó a ser removido é um nó folha
6
8
2
4
3
1
6
8
2
4
1
remove(3)
22
Remoção em Árvore de Busca Binária
Caso 2 – O nó a ser removido possui um único filho
6
8
2
4
3
1
remove(4)
6
8
2
4
3
1
23
Remoção em Árvore de Busca Binária
Caso 3 – O nó a ser removido possui dois filhos
6
8
2
4
3
1
remove(2)
6
8
3
4
3
1
A estratégia é simples: 
Troca o elemento do nó a ser removido com o menor nó da sub-árvore direita
Recursivamente, remove o nó remanejado da sub-árvore
24
Percurso em Árvores
A estratégia para se percorrer uma árvore binária é dividida em três grandes grupos:
Percurso em pré-ordem
Nós pais são processados antes dos seus filhos
Percurso em pós-ordem 
Nós filhos são processados antes dos seus pais
Percurso em ordem 
O processamento é feito na ordem filho esquerdo-pai-filho direito
Um Exemplo
8 4 3 6 5 7 15 12 16 10 14 9 11
8
4
15
3
6
5
7
12
16
10
14
9
11
Percurso Pós-Ordem
Nós filhos são processados antes dos seus pais
8
4
3
6
5
7
15
16
12
14
10
9
11
3 5 7 6 4 9 11 10 14 12 16 15 8
Percurso Pré-Ordem
Nós pais são processados antes dos seus filhos
8
4
3
6
5
7
15
16
12
14
10
9
11
8 4 3 6 5 7 15 12 10 9 11 14 16
29
Percurso em Ordem
O processamento é feito na ordem filho esquerdo-pai-filho direito
8
4
3
6
5
7
15
16
12
14
10
9
11
3 4 5 6 7 8 9 10 11 12 14 15 16
Propriedades de Árvores Binárias
A complexidade da maioria das operações em árvores é proporcional a profundidade da árvore.
Em geral as árvores binárias possuem profundidade menor do que n.
No pior caso, a árvore possui profundidade n-1
Em média, a profundidade das árvores binárias é O(√n) 
Em alguns casos especiais (árvores binárias de busca) a profundidade é em média O(logn)
A
B
C
D
E
F
G
Pior Caso
A
C
B
D
E
G
FMelhor Caso