Árvores Binárias de Busca

Prévia do material em texto

1 
Estruturas de Dados Básicas 
Árvores 
2 
Ávores 
n  Organizam os dados de forma hierárquica 
n  Acontecem com frequência na natureza 
n  Fáceis de representar e manipular com 
computadores 
n  Úteis para várias tarefas 
Exemplos 
3 
Exemplos 
4 
Terminologia 
5 
Terminologia 
6 
Terminologia 
7 
Terminologia 
8 
Terminologia 
9 
Terminologia 
10 
Terminologia 
11 
Terminologia 
12 
Terminologia 
13 
Terminologia 
14 
Propriedades 
n  Existe um único caminho da raiz para qualquer 
nó da árvore. 
n  Portanto, podemos definir a altura de todas as 
árvores como sendo o comprimento do 
caminho mais longo da raiz até uma das 
folhas. 
n  Por definição, a altura de uma árvore que possui 
somente um elemento é zero. 
15 
Exemplo de altura em árvores 
A
B C D
E F
L
G H I J
M N
Qual a altura da árvore A1? 
árvore A1 
My Documents My Computer
3½ Floppy(A:)
Network
Apostila
Parte I Parte II Parte III
Recycle Bin
Desktop
Local Disk (C:) Local Disk (D:)
Compact Disk (E:)
Removable Disk (F:) Local Disk (I:) Local Disk (J:) Control Panel
Qual a altura da 
árvore A2? 
árvore A2 
Árvores Binárias 
n  Qualquer árvore pode ser transformada numa árvore 
binária 
¨  Focaremos em árvore binárias pois elas são mais fáceis de 
armazenar e manipular 
n  Uma árvore binária é constituída de um conjunto finito 
de nós. 
n  Cada nó pode ter no máximo dois filhos. 
17 
Árvores Binárias 
n  De maneira recursiva, podemos definir uma árvore 
binária como sendo: 
¨  uma árvore vazia; ou 
¨  um nó raiz tendo duas sub-árvores, identificadas como a sub-
árvore da direita e a sub-árvore da esquerda. 
18 
Exemplo Árvore Binária 
8 
9 7 
1 
13 5 11 
4 3 
2 
 
 raiz da árvore 
Percursos em Árvores Binárias 
n  Muitas operações em árvores binárias envolvem o 
percurso de todas as suas sub-árvores, executando 
alguma ação de tratamento em cada nó. 
n  É comum percorrer uma árvore em uma das 
seguintes ordens: 
¨  Pré-Ordem: visitia a raiz, percorrer subárvore da 
esquerda, percorrer subárvore da direita; 
¨  Em-Ordem (ordem simétrica): percorrer subárvore da 
esquerda, visita raiz, percorrer subárvore da direita;; 
¨  Pós-Ordem: percorrer subárvore da esquerda, percorrer 
subárvore da direita, visita raiz. 
Caminhamento pré-ordem 
21 
Visita a raiz 
Percorre a subárvore da esquerda 
Percorre a subárvore da direita 
Caminhamento pré-ordem 
22 
Caminhamento pré-ordem 
23 
Caminhamento pré-ordem 
24 
Caminhamento pré-ordem 
25 
Caminhamento pré-ordem 
26 
Caminhamento pré-ordem 
27 
Caminhamento pré-ordem 
28 
Caminhamento pré-ordem 
29 
Caminhamento Central 
30 
Caminhamento Central 
31 
Caminhamento Central 
32 
Caminhamento Central 
33 
Caminhamento Central 
34 
Caminhamento pós-ordem 
35 
Caminhamento pós-ordem 
36 
Caminhamento pós-ordem 
37 
Caminhamento pós-ordem 
38 
Caminhamento pós-ordem 
39 
Caminhamento pós-ordem 
40 
Caminhamento pós-ordem 
41 
Caminhamento pós-ordem 
42 
Exemplo: caminhamento pós-
ordem 
43 
Árvores de Busca ou Pesquisa 
n  Até agora consideramos árvores que organizam 
os dados em forma hierárquica sem inspecionar 
os elementos 
n  Árvores binárias de busa ou pesquisa mantém 
uma ordem entre seus elementos 
¨  Raiz é maior que os elementos na árvore à esquerda 
¨  Raiz é menor que os elementos na árvore à direita 
44 
Exemplo de árvore de pesquisa 
n  O que imprime o caminhamento em ordem central? 
 
45 
Criando uma árvore vazia 
46 
Funções para árvore de busca 
47 
Inserindo um elemento em uma 
árvore binária de pesquisa 
n  O elemento vai ser inserido como uma folha da 
árvore binária de pesquisa\ 
 
n  Vamos procurar o lugar de inserção navegando 
da raiz até a folha onde ele será inserido 
48 
Inserindo um elemento em uma 
árvore binária de pesquisa 
49 
Inserindo um elemento em uma 
árvore binária de pesquisa 
50 
Inserindo um elemento em uma 
árvore binária de pesquisa 
51 
Inserindo um elemento em uma 
árvore binária de pesquisa 
52 
Inserindo um elemento em uma 
árvore binária de pesquisa 
53 
Inserindo um elemento em uma 
árvore binária de pesquisa 
54