Árvores Binárias

Prévia do material em texto

LÓGICA DE PROGRAMAÇÃO E 
ESTRUTURAS DE DADOS 
 
 
Professor Marcelo Ferreira Zochio 
 
 
 
 
 
 
 
 
 
2 
 
 
6 ÁRVORES BINÁRIAS 
Neste bloco, você irá aprender os principais conceitos e aplicações de árvores binárias, 
saberá como uma máquina decide qual o menor caminho entre um ponto e outro, e 
também como representar árvores binárias em Python. 
 
6.1 Árvores de busca 
Quando queremos representar hierarquicamente uma estrutura de dados com mais de 
uma dimensão, usamos um tipo de estrutura chamada árvore, que consiste em nós e 
arcos. 
Veja alguns exemplos de árvores na figura a seguir: 
 
 
Nota que uma árvore é composta pelo nó raiz, do qual saem todos os outros nós e/ou 
folhas. 
 
 
 
3 
 
Essa outra figura contém um exemplo de uma árvore que representa a hierarquia de 
uma empresa: 
 
 
 
Podemos representar valores através da estrutura em árvore. Quando uma árvore 
possui em todos os nós da subárvore esquerda valores numéricos inferiores ao nó raiz 
e todos os nós da subárvore direita, valores superiores ao nó raiz, e os nós possuem no 
máximo duas folhas, ela é definida como árvore binária de busca. Veja um exemplo: 
 
 
 
A busca em árvore binária normalmente é feita usando um processo recursivo. 
Essa busca começa examinando-se o nó raiz. Se o valor é igual ao valor armazenado na 
raiz, a busca se encerra. Se o valor é menor do que a raiz, a busca segue pela ramificação 
esquerda. Caso o valor seja maior do que a raiz, a busca segue pela ramificação direita. 
 
 
 
4 
 
Esse processo é repetido até que o valor seja encontrado. Se o valor não for encontrado, 
então o valor não deve estar presente na árvore. 
 
Uma árvore binária de busca aceita outras operações além de busca. Na inserção, a raiz 
é verificada e introduz-se um nó novo na subárvore da esquerda, se o novo valor for 
menor do que a raiz, ou na subárvore da direita, se o valor novo for maior do que a raiz. 
Na operação remoção, você deve considerar algumas regras: 
 Se for para remover apenas uma folha, basta removê-la simplesmente; 
 Se for para remover um nó com apenas uma folha, a folha passa a ocupar o lugar 
desse nó removido; 
 Se for para remover um nó com duas folhas, pode-se substituir o nó a ser retirado 
pelo nó sucessor (o nó mais à esquerda da ramificação direita) ou pelo nó antecessor 
(o nó mais à direita da ramificação esquerda). 
Veja exemplos nas figuras a seguir: 
Removendo uma folha 
 
 
 
 
 
 
 
5 
 
Removendo um nó com uma folha 
 
 
 
 
Removendo um nó com duas folhas 
 
 
 
SAIBA MAIS 
Neste vídeo, você aprenderá mais sobre árvores de busca. 
Vídeo: Árvore Binária de Busca 
GUERRA, Rodrigo. Árvore binária de busca. 2014. Disponível em: 
<https://www.youtube.com/watch?v=XZ0MEDhb4oE>. Acesso em: 15 fev. 2019. 
 
 
https://www.youtube.com/watch?v=XZ0MEDhb4oE
 
 
 
6 
 
6.2 Balanceamento de árvores binárias 
Dizemos que uma árvore está balanceada quando a altura das duas subárvores da raiz 
for igual a 1, -1 ou 0. Veja um exemplo de uma árvore desbalanceada: 
Árvore desbalanceada 
 
 
Note que a profundidade dessa árvore é desigual, medindo 2 na subárvore direita em 
relação à esquerda. Veja agora um exemplo de uma árvore balanceada: 
Árvore balanceada 
 
 
Quando uma árvore está desbalanceada, é preciso balanceá-la. Como? Através de 
rotações. Podemos definir rotação como operação que influencia no balanceamento de 
uma árvore, sem alterar a sequência de percurso. 
Há os seguintes tipos de rotações: esquerda simples, direita simples, esquerda dupla e 
direita dupla. Vejamos cada um deles: 
 
 
 
 
7 
 
Rotação à esquerda simples 
 
 
Rotação à esquerda dupla 
 
 
Rotação à direita simples 
 
 
 
 
 
 
8 
 
Rotação à direita dupla 
 
 
6.3 Algoritmo de Dijkstra 
O algoritmo de Dijkstra, desenvolvido pelo cientista da computação E.W. Dijkstra, é um 
algoritmo que calcula o caminho mais econômico em questão de custo entre vértices de 
um grafo. Escolhido um vértice como ponto de origem, o algoritmo calcula o custo desse 
vértice para todos os vértices do grafo, e escolhe o caminho mais curto e com menor 
custo. 
Veja os grafos a seguir expondo um problema a ser resolvido com esse algoritmo. Qual 
o caminho mais curto em ter os pontos A e F? 
 
 
 
 
 
 
 
 
9 
 
 
Vértice Passo 1 Passo 2 Passo 3 Passo 4 Passo 5 Passo 6 
A 0, A - - - - - 
B 5, A 5, B 5, B - - - 
C 3, A 3, A - - - - 
D ∞ 12, C 11, B 11, B - - 
E ∞ 14, C 14, C 14, D 14, D - 
F ∞ ∞ ∞ 17, D 17, E 17, E 
 
O melhor caminho, partindo de A para chegar até F, é C, B, D, E, F. 
 
6.4 Aplicações práticas de árvores binárias 
Podemos citar duas entre várias: jogos de xadrez e futebol de robôs. 
No xadrez, a estrutura em árvore permite analisar as possibilidades de movimentos e 
posições do tabuleiro em níveis de profundidade. Quando você escolhe os níveis de 
dificuldade para vencer seu adversário, jogando contra o computador, quanto mais 
elevado o nível, mais profunda é a análise das jogadas feitas pela máquina, ou seja, ela 
consegue prever seus próximos lances com mais precisão. Por isso, é mais difícil vencer 
a máquina em níveis mais altos, e mais ela demora para jogar, pois precisa analisar mais 
possibilidades. 
No futebol de robôs, veja a seguinte situação: a partir da figura apresentada a seguir, 
qual a melhor rota que o robô deve seguir para pegar a bola? 
 
 
 
 
10 
 
 
 
Transformaremos o cenário em um sistema de grafos: 
 
Para mapear o cenário, traçaremos uma reta entre o ponto inicial (robô) e o ponto final 
(bola) e também traçaremos retas perpendiculares à essa reta nos outros grafos: 
 
 
Traçaremos um círculo em torno de cada grafo com distância de 2r (2 vezes seu raio) 
para evitar colisões ao estabelecer a rota do robô. Os pontos de intersecção das retas 
perpendiculares e os círculos serão considerados grafos do nosso sistema. 
 
 
 
11 
 
 
 
Então ligamos os grafos uns com os outros a partir do ponto de origem: 
 
Os pontos que cruzarem a zona de segurança (os círculos) serão desconsiderados: 
 
Então ligamos os outros pontos sem passar pelos círculos: 
 
 
Este é nosso grafo, já com o cálculo dos custos de percurso entre os pontos, 
considerando a distância entre eles: 
 
 
 
12 
 
 
 
Aplicando o algoritmo de Dijkstra, chega-se a esta solução de percurso: 
 
 
Mostrando no cenário: 
 
 
6.5 Exemplos de árvores binárias em Python 
Como representar e montar uma árvore binária em Python? Veja a seguir. 
Nesse programa, usaremos conceito de orientação a objetos para representar a 
seguinte árvore binária: 
 
 
 
13 
 
 
Os valores estão em branco, pois iremos escolhê-los durante a execução do programa. 
Eis o código: 
# -*- coding: cp1252 -*- 
 
class Tree: 
 def __init__(self, cargo, left=None, right=None): 
 self.cargo = cargo 
 self.left = left 
 self.right = right 
 
def printTreeIndented(tree, level=0): 
 if tree == None: return 
 printTreeIndented(tree.right, level+1) 
 print ' '*level + str(tree.cargo) 
 printTreeIndented(tree.left, level+1) 
 
def abertura(): 
 a = input("Digite o valor da raiz da árvore: ") 
 b = input("Digite o valor de uma das folhas: ") 
 c = input("Digite o valor da outra folha: ") 
 
 if b > a and c < a: 
 tree = Tree(a, Tree(c), Tree(b)) 
 printTreeIndented(tree, level=0) 
 
 
 
14 
 
 elif b < a and c > a: 
 tree = Tree(a, Tree(b), Tree(c)) 
 printTreeIndented(tree, level=0) 
 else: 
 print "Os valores devem ser maiores ou menores que a raiz!" 
 abertura() 
abertura() 
 
A saída é mostrada na figura a seguir: 
 
 
O número mais à esquerda é a raiz; as folhas e nós da ramificação esquerda estão abaixo 
do número mais à esquerda; as folhas e nós da ramificação direita estão acima do 
número mais à esquerda. 
Para criarmosuma árvore com mais ramificações, é só alterarmos o código. Vejamos o 
trecho alterado para criarmos uma árvore com uma raiz e quatro elementos, com os 
seguintes formatos: 
 
 
 
 
 
15 
 
 
 
 
(…) 
def printTreeIndented(tree, level=0): 
 if tree == None: return 
 printTreeIndented(tree.right, level+1) 
 print ' '*level + str(tree.cargo) 
 printTreeIndented(tree.left, level+1) 
 
def printTreeIndented1(tree, level=0): 
 if tree == None: return 
 printTreeIndented1(tree.left, level+1) 
 print ' '*level + str(tree.cargo) 
 printTreeIndented1(tree.right, level+1) 
 
def abertura(): 
 a = input("Digite o valor da raiz da árvore: ") 
 b = input("Digite o valor de um nó: ") 
 c = input("Digite o valor de um nó: ") 
 
 
 
16 
 
 d = input("Digite o valor de uma das folhas: ") 
 e = input("Digite o valor de uma das folhas: ") 
 
 if b > a and c > b > a and d > c > a and e > d > a: 
 tree = Tree(a, Tree(b, Tree(c, Tree(d, Tree(e))))) 
 #tree = Tree(a, Tree(c), Tree(b)) 
 printTreeIndented(tree, level=0) 
 
 elif b < a and c < b < a and d < c < a and e < d < a: 
 tree = Tree(e, Tree(d, Tree(c, Tree(b, Tree(a))))) 
 printTreeIndented1(tree, level=0) 
 
 elif b < a and c < b < a and d < c < e and e > c < b and e > c > d and e > d: 
 tree = Tree(a, Tree(b, Tree(c, Tree(d), Tree(e)))) 
 printTreeIndented(tree, level=0) 
 
 elif b > a and c > b > a and d < c < e and e > c > b and e > c > d and e > d: 
 tree = Tree(a, Tree(b, Tree(c, Tree(d), Tree(e)))) 
 printTreeIndented1(tree, level=0) 
 
 elif a > b > d and b > d and a < c < e and c < e: 
 tree = Tree(a, Tree(c, Tree(e)), Tree(b, Tree(d))) 
 printTreeIndented1(tree, level=0) 
 
 else: 
 print "Os valores devem ser maiores ou menores que a raiz!" 
 
 
 
17 
 
 abertura() 
abertura() 
 
Conclusão 
Neste bloco, você aprendeu sobre como trabalhar com árvores binárias, seus principais 
conceitos e aplicações práticas e também como representá-las na linguagem Python. 
Por aqui terminamos esta disciplina. Nos vemos nas avaliações! 
 
 
 
 
 
18 
 
Referências 
CAPUTO, Rodrigo. Algoritmo de Dijkstra. 2012. Disponível em: 
<https://www.youtube.com/watch?v=J4TZgD 1As0Q>. Acesso em: 20 dez. 2018. 
DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++. Tradução de Roberto 
Enrique Romero Torrejon. São Paulo: CENGAGE, 2017. 
PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no 
desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.