Árvores Binárias
Profa. Patrícia A. Jaques
Luiz Gonzaga Jr
Contribuições
Algumas transparências são da profa. Renata Galante da II/UFRGS
com permissão
Árvore Binária
• É uma árvore onde cada nó pode conter nenhum, 1
ou 2 filhos apenas
– Grau=2.
• Uma árvore binária é formada por nós onde cada nó
contém um valor, um ponteiro esquerdo e um
ponteiro direito.
A
B
D
C
E
F
G
Nivelamento - PIPCA 2012/1
2
Árvore Binária
• O nó A é a raiz da árvore. Como B é a raiz da sua
sub-árvore esquerda dizemos que B é o filho
esquerdo de A, do mesmo modo, C é o filho
direito de A. Por isso A é o pai dos nós B e C e estes
dois são irmãos.
A
filho esquerdo de A
B
D
C
E
filho direito de A
F
G
Nivelamento - PIPCA 2012/1
3
Tipos de Árvores Binárias: Estritamente Binária
• Ocorre quando todo nó que não é
folha tiver sub-arvores
esquerda e direita não vazias.
– todo nó tem 0 ou 2 filhos.
• Número de nós em uma árvore
estritamente binária com n folhas:
– 2n-1
Estritamente
Binária
bibliografia:Szwarcfiter, J. & Markenzon,
Lilian. Estrturas de Dados e seus
Algoritmos. Rio de Janeiro: LTC, 1994
Nivelamento - PIPCA 2012/1
4
Tipos de Árvores Binárias: Binária Completa
• É uma árvore estritamente
binária onde todos os nós
folhas se encontram ou no
último ou no penúltimo nível
da árvore.
Binária
Completa
bibliografia:Szwarcfiter, J. & Markenzon,
Lilian. Estrturas de Dados e seus
Algoritmos. Rio de Janeiro: LTC, 1994
Nivelamento - PIPCA 2012/1
5
Tipos de Árvores Binárias: Binária Cheia
bibliografia:Szwarcfiter, J. & Markenzon,
Lilian. Estrturas de Dados e seus
Algoritmos. Rio de Janeiro: LTC, 1994
Binária
Cheia
•
•
•
•
Árvore estritamente binária onde os nós folhas se encontram no último
nível.
O número total de nós em (tn) em uma árvore binária cheia de altura h é:
– tn=2h-1
Assim, pela mesma fórmula podemos afirmar que, numa árvore binária
completa, a altura h de uma árvore é dada por:
– h= log2(tn+1)
Embora a árvore binária completa possua muitos nós, a distância da raiz até
qualquer folha (profundidade) é relativamente pequena.
Nivelamento - PIPCA 2012/1
6
Árvores Binárias: representação
Endereço da raiz
A
B
referência
para filho
esquerdo
referência
para filho
direito
A
C
B
D
E F
C
G
D
E
F
G
chave
do nó
Nivelamento - PIPCA 2012/1
7
Aplicação de Árvores Binárias
• Representação de expressões aritméticas em
árvores binárias
– Dada uma expressão aritmética, sua representação em
árvore binária é feita de tal forma que a ordem de prioridade
das operações fica implícita.
Regra:
• O operador de menor prioridade aparece na raiz;
• A sub-expressão à esquerda desse operador dá
origem à sub-árvore esquerda;
• A sub-expressão à direita do operador dá origem
à sub-árvore direita.
Nivelamento - PIPCA 2012/1
8
Representação de expressões aritméticas
em árvores binárias
+
A
*
B
C
Ex: A + B * C
Obs. Operandos sempre aparecem como folhas; operadores, nunca.
Nivelamento - PIPCA 2012/1
9
Representação de expressões aritméticas
em árvores binárias
• Caminhamentos:
• Em pos-ordem  Notação polonesa pós fixada.
– Ex: A B C * + (na primeira expressão);
• Em in-ordem  Forma original (infixada) sem
parênteses.
– Ex: A + B * C (primeira expressão);
• Em pré-ordem  Notação polonesa prefixada (sem
grande utilidade).
– Ex: + A * B C (primeira expressão);
• Obs. A notação polonesa pós fixada é muito útil
(principalmente para as máquinas), pois exibe os
operadores na ordem de execução das operações.
Nivelamento - PIPCA 2012/1
10
Algoritmo para gerar uma árvore binária a partir de
uma expressão aritmética em notação infixa
Procedimento Interpretar(string)->ponteiro
COMEÇO
1. fazer uma árvore com a string como único nó;
2. procurar por operadores de MENOR precedência (+ ou -) que não
estejam dentro de “(“ e “)”, pois estes serão considerados um
operando.
se tem, substitua a árvore por uma com o operador no nó raiz e com os
operandos nos nós folha. (se você procurar o PRIMEIRO operando com
menor precedência, basta dividir a árvore como explicado e aplicar esse
procedimento de procurar operador de menor precedência recursivamente
no nó da DIREITA). Lembre-se que um operando é um número, uma
variável uma expressão entre parêntesis ou uma função.
3. repetir o procedimento 2 com operadores de MÉDIA precedência (* e /)
SÓ EM NÓS FOLHA;
4. repetir o procedimento para operadores com MAIOR precedência (só o
^);
5. percorrer os nos folha (todos contém operandos)
se o operando é número ou variável, não mexe.
se o operando é expressão entre parêntesis, substituir esse nó por
Interpretar(expressão sem os parêntesis);
FIM Interpretar.
Nivelamento - PIPCA 2012/1
11
Algoritmo para avaliar a árvore (calcular a expressão)
Algoritmo eval (BinaryTreeNode v) {
/* recebe nó raiz como parâmetro: a classe BinaryTreeNode, além
dos ponteiros para filhos esquerdo e direito, também contém
outros dois atributos:
1) char operador;
2) double operando;
real retorno 0;
if v == null { não tem árvore - devolve valor zero }
then retorno
0;
else if v.operador==’’ /* se operando é igual ‘’, então nó
guarda operando*/
then return v.operando; //devolve valor contido no nodo
else switch a.operador { //operador - executa operação
case “+”: retorno eval(v.left) + eval(v.right);
case “-” : retorno eval(v.left) - eval(v.right);
case “*” : retorno eval(v.left) * eval(v.right);
case “/” : retorno eval(v.left) / eval(v.right);
}
return retorno;
}
Nivelamento - PIPCA 2012/1
12
Árvore Binária de Pesquisa
• Também chamada de:
– árvore binária de busca
– ou árvore binária ordenada
• apresentam uma relação de ordem entre os nodos
• ordem é definida por um campo denominado chave
• não permite chaves duplicadas, ou seja, cada nó
tem um valor de chave diferente
esq chave dir
Nivelamento - PIPCA 2012/1
13
Árvore Binária de Pesquisa
não há chaves duplicadas
raiz
500
filho da esquerda:
valor da chave
menor que o valor da
chave do nó pai
150
300
800
400
600
filho da direita:
valor da chave maior
que o valor da chave
do nó pai
900
fazer exercício: criar árvore inserindo nós na seguinte ordem:
f, a, t, b, e, u, i, c, d, a, e
Nivelamento - PIPCA 2012/1
14
Classe representando um nó
public class BSTNode {
protected int key;
protected BSTNode left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(int num) {
this(num,null,null);
}
public BSTNode(int num, BSTNode lt, BSTNode rt)
{
this.key = num; left = lt; right = rt;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public BSTNode getLeft() {
return left;
}
public void setLeft(BSTNode left) {
this.left = left;
}
public BSTNode getRight() {
return right;
}
public void setRight(BSTNode right) {
this.right = right;
}
}
Nivelamento - PIPCA 2012/1
15
Classe representando árvore
public class BST {
private BSTNode root = null;
public BST() {
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public BSTNode getRootNode (){
return root;
}
Nivelamento - PIPCA 2012/1
16
Busca de um valor
• A procura de um valor em uma árvore binária é algo mais rápido do
que a procura em listas encadeadas ou vetores.
• Para cada nó, compare a chave a ser localizada com o valor
armazenado no nó correntemente apontado.
– Se a chave for menor, vá para a sub-árvore esquerda e tente
novamente,
– senão vá para a sub-árvore direita.
• A busca pára quando for encontrado o nó ou quando não há mais
meios de continuar (nó folha), pois a chave não está na árvore.
• A complexidade pode ser medida pelo número de comparações
feitas durante o processo de busca. Isso depende do número de nós
encontrados no único caminho que leva da raiz ao nó procurado.
Então a complexidade, depende da forma da árvore e da posição do
nó procurado na árvore. O número médio de comparações em uma
busca é  (lg n), pois a altura de uma árvore binária completa
(perfeitamente balanceada) é h=lg (n+1) .
Nivelamento - PIPCA 2012/1
17
Busca
public BSTNode search (int el) {
return search(root,el);
}
private BSTNode search (BSTNode p, int el) {
while (p != null) {
/* se valor procurado == chave do nó, retorna referência ao nó */
if (el==p.key) return p;
/* se valor procurado < chave do nó,
procurar na sub-árvore esquerda deste nó */
else if (el<p.key) p = p.left;
/* se valor procurado > chave do nó,
procurar na sub-árvore direita deste nó */
else p = p.right;
}
// caso chave não foi achada, retorna null
return null;
}
Nivelamento - PIPCA 2012/1
18
Inserindo uma nova chave
public boolean insert (int el) {
BSTNode p = root, prev = null;
// caso o valor já exista na árvore, não inserir e retornar false
if (search(el)!=null) return false;
// procurando um lugar para colocar o novo nó
while (p != null) {
prev = p;
if (el<p.key) p = p.left;
else p = p.right;
}
// se árvore vazia
if (root == null) root = new BSTNode(el);
else if (prev.key<el) prev.right = new BSTNode(el);
else prev.left = new BSTNode(el);
return true;
}
Nivelamento - PIPCA 2012/1
19
Caminhamento (percurso)
em árvore binária de pesquisa
• É o processo de visitar cada nó da árvore exatamente
uma vez.
• Visitar: Fazer algo com o nó como exibi-lo, gravá-lo,
etc.
• O percurso pode ser interpretado como colocar todos
os nós em uma linha ou a linearização da árvore.
• Os percursos podem ser em extensão ou em
profundidade.
– Percursos em extensão: visitam todos os nós de cada
nível, nível por nível (indo do mais alto ao mais baixo, ou
vice-versa).
– Percursos em profundidade: percorre os caminhos das
árvores. Percorre primeiramente todo o caminho mais a
esquerda, e assim por diante.
Nivelamento - PIPCA 2012/1
20
Caminhamento (percurso)
em árvore binária de pesquisa
• Os três mais comuns tipos de percursos em
profundidade, definidos recursivamente, são:
– PRÉ-ORDEM (raiz-esquerda-direita):
• visita o nó;
• percorre a sub-árvore esquerda;
• percorre a sub-árvore direita;
– PÓS-ORDEM (esquerda-direita- raiz):
• percorre a sub-árvore esquerda;
• percorre a sub-árvore direita;
• visita o nó;
– IN-ORDEM (esquerda-raiz-direita):
• percorre a sub-árvore esquerda;
• visita o nó;
• percorre a sub-árvore direita.
Nivelamento - PIPCA 2012/1
21
Percurso in-ordem
public void inorder() {
inorder(root);
}
private void inorder (BSTNode p) {
if (p != null) {
inorder(p.left);
System.out.print(p.key + " ");
inorder(p.right);
}
}
Nivelamento - PIPCA 2012/1
22
Percurso em pre-ordem
public void preorder() {
preorder(root);
}
private void preorder(BSTNode p) {
if (p != null) {
System.out.print(p.key + " ");
preorder(p.left);
preorder(p.right);
}
}
Nivelamento - PIPCA 2012/1
23
Percurso em pós-ordem
public void postorder() {
postorder(root);
}
private void postorder(BSTNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.key + " ");
}
}
Nivelamento - PIPCA 2012/1
24
Remoção de um nó
•
Na remoção 3 situações podem ocorrer :
Caso 1: Exclusão de uma folha
O nó é uma folha e não tem filhos: O ponteiro do seu pai é
ajustado para nulo.
antes
depois
50
30
15
80
40
60
50
30
90
80
40
Nivelamento - PIPCA 2012/1
60
90
25
Remoção de um nó
Caso 2: O nó tem um filho: o ponteiro do pai aponta
para o filho deste
antes
depois
50
30
80
40
60
50
40
90
Nivelamento - PIPCA 2012/1
80
60
90
26
Remoção de um nó
• Caso 3: O nó tem 2 filhos. Neste caso podemos
fazer a remoção de duas maneiras:
– remoção por cópia;
– remoção por fusão
antes
50
30
15
80
40
60
90
Nivelamento - PIPCA 2012/1
27
Remoção por cópia
• remove uma chave k1 (chave do nó que se quer
remover):
– sobrescrevendo-a por uma outra chave k2 (o maior
valor na sub-árvore esquerda, pois este vai ser maior
que todos os valores da sub-árvore esquerda)
– e então removendo o nó que contem k2 (que será um
dos casos simples: folha, ou nó com apenas um filho).
Nivelamento - PIPCA 2012/1
28
Remoção por cópia
1
2
3
Final
Nivelamento - PIPCA 2012/1
29
Nó que retorna referência ao nó pai de uma chave
protected BSTNode searchFather (int el) {
BSTNode p = root;
BSTNode prev = null;
// acha o nó p com a chave el
while (p != null && !(p.key==el)) {
prev = p;
if (p.key<el)
p = p.right;
else p = p.left;
}
if (p!=null && p.key==el) return prev;
return null;
}
Remoção por cópia
public void deleteByCopying (int el) {
BSTNode node, father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
if (node!=root) father = searchFather (el); // procura pai do nó a ser deletado
if (node.right == null){
// nó não tem filho direito (caso 2 ou caso 1);
if (node==root) root= node.left;
else if (father.left == node) father.left = node.left;
else father.right = node.left;
}
else if (node.left == null) {
// nó não tem filho esquerdo (caso 2)
if (node==root) root= node.right;
else if (father.left == node) father.left = node.right;
else father.right = node.right;
}
else {
// nó tem ambos os filhos: fazer remoção por cópia
BSTNode tmp = node.left;
// 1. pegando sub-arvore esquerda
while (tmp.right != null)
// 2. acha a posição mais a direita da sub-árvore esquerda do nó
tmp = tmp.right;
deleteByCopying (tmp.key);
// remove por copia o nó que possui o maior valor
// da sub-arvore esquerda do nó a ser deletado
node.key = tmp.key;
// copia o valor da chave do maior nó da subárvore esquerda
}
}
else if (root != null) System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
Nivelamento - PIPCA 2012/1
31
Remoção por fusão
• A solução consiste em fusionar as duas subárvores do nó a ser deletado em uma.
• Para tanto, como na organização da árvore binária,
todos os valores da sub-árvore a esquerda são
menores que os valores da sub-árvore a direita, deve
se encontrar o maior valor na sub-árvore
esquerda e torná-lo a raiz da sub-árvore
direita. Também pode-se procurar o nó com menor
valor da sub-árvore direita.
• Remove a chave, removendo o nó que contém a
chave. E o pai do nó removido passa a apontar para
a nova sub-árvore.
Nivelamento - PIPCA 2012/1
32
Remoção por fusão
1
2
3
Final
Nivelamento - PIPCA 2012/1
33
Remoção por fusão
public void deleteByMerging (int el) {
BSTNode tmp, node,father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
// procura pai do nó a ser removido
if (node!=root) father = searchFather (el);
if (node.right == null){
// nó não tem filho direito (caso 2);
if (root==node) root=node.left;
else if (father.left == node) father.left = node.left;
else father.right = node.left;
}
else if (node.left == null) { // nó não tem filho esquerdo (caso 2)
if (root==node) root=node.right;
else if (father.left == node) father.left = node.right;
else father.right = node.right;
}
else { // se tem dois filhos, faz deleção por fusão
tmp = node.left;
// pega sub-arvore esquerda
while (tmp.right != null) tmp = tmp.right; // pega filho mais a direita da sub-arvore esquerda
tmp.right = node.right;
// o filho mais a direita da sub-arvore esquerda passa a ter
// como filho direito o filho direito do nó a ser deletado
if (root==node) root = node.left;
else if (father.left == node) father.left = node.left;
else father.right = node.left;
}
}
else if (root != null) System.out.println("el " + el + " is not in the tree");
Nivelamento - PIPCA 2012/1
34
else System.out.println("the tree is empty");
}
Heap
• É uma estrutura de dados baseada em árvore
(especializada)
• Propriedade do heap
se B é filho de um nó A, então a chave(A) >= chave
(B) (maior elemento na raiz). Chamada max heap.
Pode-se comparar ao contrário, dai temos o min
heap.
• Usado para implementar priority queues
• Applet: vamos ver o funcionamento
http://people.ksp.sk/~kuko/bak/index.html
Max HEAP
Demo: construção da heap
• http://students.ceid.upatras.gr/~perisian/data_struct
ure/HeapSort/heap_applet.html
Implementação
• A remoção do heap é feita ordenando os elementos.
• Implementação do heap através de array a:
• Indexação
– filhos a[2i+1] e a[2i+2]
– pais a[floor((i−1)/2)]
Heap binário -> usa-se árvore binária
Heap binário
• É um heap criado usando-se árvore binária, com
duas restrições:
– Propriedade de shape: árvore completa (todos os níveis da
árvores preenchidos, exceto possivelmente o último...) preenchimento da esquerda para a direita
– Propriedade de heap: cada né á maior do que seus filhos
• Operações:
– Inserção
– Remoção
Nivelamento - PIPCA 2012/1
40
Exemplos
• Inserção
• Remoção da raiz do heap (maior elemento)
Nivelamento - PIPCA 2012/1
41
Outros tipos
Kd-tree
2-d
3-d
BSP
Quadtree
Octree
Nivelamento - PIPCA
42