ALGORITMOS AVANÇADO 1

Prévia do material em texto

Algoritmos AvanAlgoritmos Avanççadosados
Professor Alessandro Larangeiras
UNIDADE I ANÁLISE DE ALGORITMO: NOTAÇÃO O
1.1 Algoritmo
1.2 Estrutura de Dados
1.2.1 Revisão de Programas em C++ envolvendo Vetores, Matrizes, 
Ponteiros, Registros (Struct) e Funções.
1.3 O que é Analise de Algoritmos
1.4 Sobre o Elemento da Análise Assintótica - Notação O
1.4.1 Notação O
1.4.2 Sobre a função
1.4.3 Operações com a Notação O
CONTEÚDO
UNIDADE II RECURSIVIDADE
2.1 Definições recursivas
2.2 Como implementar recursividade
2.3 Quando não usar recursividade
2.4 Desenvolvendo algoritmos com recursividade
UNIDADE III ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO 
(MERGESORT)
3.1 Definição
3.2 Dividir para conquistar
3.3 Problema da intercalação
3.4 O algoritmo de ordenação por intercalação mergesort.
3.5 Análise da complexidade do algoritmo mergesort.
CONTEÚDO
UNIDADE IV ALGORITMO DE ORDENAÇÃO RÁPIDA (QUICKSORT)
4.1 Definição
4.2 Ordenação rápida
4.3 O algoritmo de ordenação rápida quicksort
4.4 Análise da complexidade do algoritmo quicksort
CONTEÚDO
UNIDADE V ESTRUTURAS DE DADOS DOS TIPOS ÁRVORE 
BINÁRIA E ÁRVORE AVL
5.1 Árvores, Árvores Binárias e Árvores Binárias de Busca
5.2 Implementando as Árvores Binária
5.3 Percorrendo uma Árvore Binária de Busca
5.4 Percurso em Árvore
5.5 Inserção
5.6 Remoção
5.7 Balanceando uma Árvore
5.7.1 O Algoritmo DSW
5.7.2 Árvores AVL
CONTEÚDO
UNIDADE VI ALGORITMOS EM GRAFOS
6.1 Conceitos de grafos.
6.2 Representação de grafo
6.3 Algoritmos de busca
6.4 Algoritmo do caminho mínimo
6.4.1 Encontrar o melhor caminho do vértice origem ao vértice 
destino
CONTEÚDO
[...] [Algoritmo é a descrição de] um procedimento para 
resolver um problema[, feita em determinada linguagem] [...].
SEDGEWICK; WAYNE, 2011, p. 4.
ALGORITMO
Algoritmo Euclidiano em Linguagem de Programação Java
public static int gcd(int p, int q) {
if(q == 0)
return p;
int r = p % q;
return gcd(q, r);
} SEDGEWICK; WAYNE, 2011, p. 4.
Algoritmo Euclidiano em Linguagem Natural
Calcule o máximo divisor comum de dois inteiros não-negativos P e Q do 
seguinte modo: se Q for 0, a resposta é P, se não, divida P por Q e 
obtenha o resto R; a resposta será o máximo divisor comum de Q e R.
ALGORITMO
Os tipos de dados manipulados por um algoritmo podem ser classificados em 
dois grupos: atômicos[, ou simples,] e complexos[,] ou compostos [...].
(LAUREANO, 2008, p. 2).
TIPOS DE DADOS
ATÔMICO
COMPLEXO
Se um tipo de dado pode ser decomposto, então o tipo de dado é
dito estruturado [...].
(LAUREANO, 2008, p. 2).
ESTRUTURA DE DADOS
TIPOS DE DADOS & ESTRUTURA DE DADOS
HOMOGÊNEAS
HETEROGÊNEAS
contêm um único tipo de dados
contêm diferentes tipos de dados
ESTRUTURAS DE DADOS POR TIPO DE CONTEÚDO
VETORES
(LAUREANO, 2008, p. 3/7).
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
#include <iostream>
int main()
{
cout << "Hello, World!" << endl;
}
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
#include <iostream>
using std::cout;
using std::endl;
int main()
{
//...
double nota[5];
nota[0] = 7.6;
nota[1] = 8;
nota[2] = 5.5;
nota[3] = 7.0;
nota[4] = 1.0;
for(int i = 0; i < 5; i++)
{
cout << "Nota do aluno n." << (i +1) << ": ";
cout << nota[i] << endl;
}
}
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
#include <iostream>
using std::cout;
using std::endl;
int main()
{
//...
// double peso[] = { 75, 85.2, 21.5, 90.5, 55.3 };
double peso[5] = { 75, 85.2, 21.5, 90.5, 55.3 };
for(int i = 0; i < 5; i++)
{
cout << "Peso do paciente n." << (i +1) << ": ";
cout << peso[i] << endl;
}
}
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
#include <iostream>
using std::cout;
using std::endl;
int main()
{
//...
int idade[3];
for(int i = 0; i < 3; i++)
{
cout << "Digite o valor da idade n." << (i +1) << ": ";
cin >> idade[i];
}
for(int i = 0; i < 3; i++)
{
cout << "Idade n." << (i +1) << ": " << idade[i] << endl;
}
}
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main()
{
//...
const int TAM_MAX_NOME = 3;
char letras[TAM_MAX_NOME];
for(int i = 0; i < TAM_MAX_NOME; i++)
{
cout << "Digite a letra n." << (i +1) << ": ";
cin >> letras[i];
}
for(int i = 0; i < TAM_MAX_NOME; i++)
{
cout << "Letra n." << (i +1) << ": " << letras[i] << endl;
}
}
ESTRUTURAS HOMOGÊNEAS UNIDIMENSIONAIS
MATRIZES
(LAUREANO, 2008, p. 3/7).
ESTRUTURAS HOMOGÊNEAS MULTIDIMENSIONAIS
#include <iostream>
int main()
{
//...
int matrizA[1][4];
matrizA[0][0] = 3;
matrizA[0][1] = 2;
matrizA[0][2] = 1;
matrizA[0][3] = 5;
for(int l = 0; l < 1; l++)
{
for(int c = 0; c < 4; c++)
{
cout << "Matriz A[" << (l +1) << "," << (c +1); 
cout << "]= " << matrizA[l][c] << endl;
}
}
}
ESTRUTURAS HOMOGÊNEAS MULTIDIMENSIONAIS
#include <iostream>
using std::cout;
using std::endl;
int main()
{
//...
int matrizB[2][4] = { {1, 2, 3, 4}, {5, 6, 7, 8} };
for(int l = 0; l < 2; l++)
{
for(int c = 0; c < 4; c++)
{
cout << "Matriz B[" << (l +1) << "," << (c +1);
cout << "]= " << matrizB[l][c] << endl;
}
}
}
ESTRUTURAS HOMOGÊNEAS MULTIDIMENSIONAIS
#include <iostream>
// using...
int main()
{
//...
int matrizC[2][4];
for(int l = 0; l < 2; l++)
for(int c = 0; c < 4; c++)
{
cout << "Digite o elemento [" << (l +1) << ",";
cout << (c +1) << "] da matriz C: ";
cin >> matrizC[l][c];
}
for(int l = 0; l < 2; l++)
for(int c = 0; c < 4; c++)
{
cout << "Matriz C[" << (l +1) << "," << (c +1);
cout << "]= " << matrizC[l][c] << endl;
}
}
ESTRUTURAS HOMOGÊNEAS MULTIDIMENSIONAIS
REGISTROS
(LAUREANO, 2008, p. 17).
ESTRUTURAS HETEROGÊNEAS
//...
struct Rectangle
{
int left;
int top;
int width;
int height;
};
int main()
{
Rectangle pool = { 30, 40, 70, 80 };
Rectangle yard;
yard.left = 0;
yard.top = 0;
yard.width = 100;
yard.height = 120;
cout << "Yard width = " << yard.width << endl;
cout << "Pool width = " << pool.width << endl;
}
ESTRUTURAS HETEROGÊNEAS
#include <iostream>
using std::cout;
using std::endl;
int main()
{
int numero, valor;
int* p; // "DataType*" = ponteiro para DataType.
// int *p;
numero = 55;
p = &numero; // "&VarName" = Address-Of operator.
cout<< "p = “ << p << "; " << "&numero = " << &numero <<endl;
cout<< "*p = " << *p << "; " << "numero = " << numero <<endl;
valor = *p; // "*VarName" = Indirection operator.
cout << "valor = " << valor << endl;
}
PONTEIROS EM C++
#include <iostream>
using std::cout;
using std::endl;
void troca(int a, int b)
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int a = 2;
int b = 3;
cout<< "Antes da troca: A = " << a << ", B = " << b <<endl;
troca(a, b);
cout<< "Depois da troca: A = " << a << ", B = " << b <<endl;
}
FUNÇÕES EM C++: PASSAGEM DE ARGUMENTOS POR VALOR
#include <iostream>
using std::cout;
using std::endl;
void troca(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int a = 2;
int b = 3;
cout<< "Antes da troca: A = " << a << ", B = " << b <<endl;
troca(a, b);
cout<< "Depois da troca: A = " << a << ", B = " << b <<endl;
}
FUNÇÕES EM C++: PASSAGEM DE ARGUMENTOS POR REFERÊNCIA
1. Desenvolva um programa em C++ que:
a) receba a quantidade de alunos matriculados em um curso de extensão da Estácio, 
informada pelo usuário;
b) receba a nota de cada aluno, informada pelo usuário;
c) calcule e exiba a média aritmética das notas dos alunos;
d) calcule e exiba quantas notas são maiores ou iguais e quantas são inferiores a esta 
média.
2. Desenvolva um programa em C++ que leia uma matriz 3 x 3 e mostre os elementos 
da mesma matriz multiplicado pelo maior número carregado na matriz.
EXERCÍCIOS
int main() // Resposta do exercício #1
{
int alunosQtd = 0;
cout << "Quantidade de alunos: "; cin >> alunosQtd;
double alunosNota[alunosQtd];
for(int i = 0; i < alunosQtd; i++)
{
cout << “Nota" << (i+1) << ": "; cin >> alunosNota[i];
}
double media = 0;
for(int i = 0; i < alunosQtd; i++)
media += alunosNota[i];
media /= alunosQtd; cout << "Media: " << media << endl;
int maioresQtd = 0; int menoresQtd = 0;
for(int i = 0; i < alunosQtd;i++)
{
if(alunosNota[i] >= media) maioresQtd++;
else menoresQtd++;
}
cout<< maioresQtd <<" maiores e "<< menoresQtd << " menores";
return 0;
}
ANÁLISE DE ALGORITMOS
Ciência da Computação não cuida só de programação; 
há ciência real envolvida. Entre as muitas coisas que os 
cientistas fazem está a análise. Algoritmos podem ser 
analisados [...].
TOAL, 2018a.
ANÁLISE DE ALGORITMOS
A compexidade de um algoritmo reflete o esforço computacional 
requerido para executá-lo. Esse esforço computacional mede a 
quantidade de trabalho, em termos de tempo de execução ou da 
quantidade de memória requerida. As principais medidas de 
complexidade são tempo e espaço, relacionadas à velocidade 
e à quantidade de memória, respectivamente, para a execução 
de um algoritmo.
TOSCANI; VELOSO, 2012, p. 14.
ANÁLISE DE ALGORITMOS
Análise de algoritmos é a ciência de se determinar a 
quantidade de tempo e espaço requeridos por computado-
res [(complexidade computacional)] para executar vários 
procedimentos.
VRAJITORU; KNIGHT, 2014, p. 1.
Ou seja, análise de algoritmos é o estudo da complexidade 
computacional de algoritmos, de modo a aprimorar sua 
eficiência.
ANÁLISE DE ALGORITMOS
É importante ser capaz de medir, ou no mínimo fazer afirmações educadas 
sobre, a complexidade de espaço e tempo de um algoritmo. Isto 
possibilitará comparar os méritos de duas abordagens alternativas para a 
solução de um problema e determinar também se uma solução proposta 
atenderá as restrições de recurso requeridas antes de se investir dinheiro e 
tempo de codificação.
TOAL, 2018a.
A análise é feita antes da codificação. A perfilação (também 
chamada de benchmarking [[análise comparativa]]) é feita 
depois de o código estar escrito.
TOAL, 2018a.
ANÁLISE DE ALGORITMOS
[...] [Uma maneira de se determinar a complexidade de um algoritmo] é a da medida 
empírica [(baseada na experiência)]. Podemos pensar em medir experimentalmente a 
quantidade de trabalho (tempo ou memória) requerida por um algoritmo executado em 
um computador específico. Entretanto, uma medida empírica é fortemente dependente, 
tanto do programa quanto da máquina usada para implementar o algoritmo. [...] Apesar 
de a comparação de programas reais, rodando em computadores reais, ser uma fonte 
de informação importante, os resultados são inevitavelmente afetados pela 
programação e pelas características das máquinas. Uma alternativa útil vem de se fazer 
uma análise matemática do algoritmo de maneira geral. Essa análise, além de ser 
independente da implementação, permite, muitas vezes, antecipar o cálculo da 
complexidade para a fase de projeto do algoritmo [e] [...] é útil para avaliar as 
dificuldades intrínsecas da resolução computacional de um problema.
TOSCANI; VELOSO, 2012, p. 14.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Algoritmo: procura o maior valor de um array A, com N
elementos, armazenando-o em M.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Instruções simples (executadas diretamente pela CPU, ou algo próximo 
disso):
• atribuição de valor a variável;
• acesso ao valor de determinado elemento de um array;
• comparação entre dois valores;
• incremento de um valor;
• operações aritméticas (adição, multiplicação etc.).

• as instruções possuem o mesmo custo;
• comandos condicionais possuem custo zero.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Algoritmo: procura o maior valor de um array A, com N
elementos, armazenando-o em M.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução: acessar o valor 
de a[0] e atribuir a m.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Algoritmo: procura o maior valor de um array A, com N
elementos, armazenando-o em M.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução: inicialização do for (i = 0).
1 instrução: comparação i < n, 
mesmo que o tamanho do array 
seja zero.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Algoritmo: procura o maior valor de um array A, com N
elementos, armazenando-o em M.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução: incremento, ao final do for (i++).
1 instrução: comparação i < n.
Custo de execução do loop for = 2n instruções.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Algoritmo: procura o maior valor de um array A, com N
elementos, armazenando-o em M.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução
2 instruções
2 instruções * N
Custo dominante, ou pior caso = 3 + 2n instruções.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Função matemática do custo de execução deste algoritmo, 
considerando o array de input e o loop vazio:
f(n) = 2n + 3
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução
1 instrução
Problema: o if sempre será executado, 
mas nem sempre o valor de m será alterado.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Antes (loop for vazio), bastava saber o tamanho do
array (n) para definir a função de custo: f(n) = 2n + 3.
Agora (atribuição de m, conforme o if), deve-se
considerar também o conteúdo do array.
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Por exemplo, considere dois arrays de mesmo tamanho:
int a1[] = { 1, 2, 3, 4 };
int a2[] = { 4, 3, 2, 1 };
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
• A1: mais instruções executadas 
(if sempre verdadeiro).
• A2: atribuição nunca executada 
(if sempre falso).
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
Custo dominante, ou pior caso,
de um algoritmo
maior número de instruções executadas.
=
ANÁLISE MATEMÁTICA: CONTAGEM DE INSTRUÇÕES DE UM ALGORITMO
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
Pior caso: array com valores em ordem crescente:
int a1[] = { 1, 2, 3, 4 };
1 instrução
2 instruções
2 instruções * N
1 instrução * N
1 instrução * N
Função matemática do custo de execução deste algoritmo (complexidade de 
tempo), considerando o array de input, no pior caso:
f(n) = 3 + 2n + 2n = 4n + 3
ANÁLISE ASSINTÓTICA
Para se analisar a complexidade de tempo deste algoritmo,
todos os termos da função f(n) = 4n + 3 são necessários?
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
Análise assintótica é um método que descreve o comportamento 
de limites, considerando entradas de tamanhos grandes o 
suficiente a ponto de evidenciar a ordem de crescimento do 
tempo de execução do algoritmo.
ANÁLISE ASSINTÓTICA
Devemos manter apenas os termos da função que indicam o que 
ocorre quando o tamanho dos dados de entrada (N) cresce muito.
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
Se um algoritmo for mais rápido que outro para um grande 
conjunto de dados de entrada, muito provavelmente continuará
sendo com um conjunto de dados de entrada menor.
ANÁLISE ASSINTÓTICA
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução
2 instruções
2 instruções * N
1 instrução * N
1 instrução * N
Devemos descartar os termos que crescem lentamente e manter 
apenas os que crescem rápido, à medida que o tamanho de N 
aumenta.
f(n) = 4n + 3
ANÁLISE ASSINTÓTICA
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
2 instruções * N
1 instrução * N
1 instrução * N
Devemos descartar também as constantes que multiplicam o termo N, porque são 
custos que variam conforme a linguagem. Por exemplo:
f(n) = 4n
// Pascal.
m := a[i];
// C.
if((i > = 0) && (i < n))
m = a[i];
=
• Pascal: 3 instruções (com etapa de verificação);
• C: 1 instrução (semetapa de verificação).
ANÁLISE ASSINTÓTICA
f(n) = n
Comportamento assintótico, comportamento de limite da 
função f(n), quando N tende ao infinito.
O termo que possui maior expoente domina o 
comportamento de f(n), quando N tende ao infinito.
ANÁLISE ASSINTÓTICA
g(n) = 1000n + 500
h(n) = n2 + n + 1
Apesar de a funApesar de a funçção g(n) possuir constantes maiores ão g(n) possuir constantes maiores 
multiplicando seus termos, h(n) possui um valor de N multiplicando seus termos, h(n) possui um valor de N 
sempre maior, tornando os demais termos e sempre maior, tornando os demais termos e 
constantes pouco importantes.constantes pouco importantes.
ANÁLISE ASSINTÓTICA
g(n) = n
h(n) = n2
Descartando os termos menos importantes das funções e 
mantendo apenas os termos de maior grau, temos:
ANÁLISE ASSINTÓTICA
Exemplos de funções de custo, com seu 
comportamento assintótico:
* Se a função não possuir nenhum termo multiplicado por N, seu 
comportamento assintótico será constante (= 1).
ANÁLISE ASSINTÓTICA
Obtemos a função de custo de um programa simples apenas contando os 
loopings aninhados. Ou seja:
• algoritmos sem looping: f(n) = 1 (número constante de instruções, 
exceto em caso de recursão);
• algoritmos com loopings de 1 a N: f(n) = n (um conjunto de instruções 
constante antes e/ou depois do looping e um conjunto de instruções 
constante dentro do looping);
• algoritmos com dois loopings aninhados: f(n) = n2; e assim por diante.
NOTAÇÃO O
A notação assintótica O (letra grega ômicron) é uma 
representação matemática que descreve a complexidade de 
tempo de um algoritmo no pior caso, definindo o limite 
superior do tamanho da entrada.
Ou seja, o comportamento do algoritmo não pode ultrapassar o 
limite definido.
NOTAÇÃO O
int m = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] >= m)
{
m = a[i];
}
}
1 instrução
2 instruções
2 instruções * N
1 instrução * N
1 instrução * N
Função matemática da complexidade de tempo deste algoritmo, 
no pior caso:
f(n) = 3 + 2n + 2n = 4n + 3
O(g(n)) = n
Assintoticamente, no pior caso (notação O):
1. Implemente e analise a seguinte função em C++:
int calculaMenor (int a[], int n)
{
int menor = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < menor)
{
menor = a[i];
}
}
return menor;
}
EXERCÍCIOS
RECURSIVIDADE
Conforme o dicionário Priberam, recursar significa 
“examinar de novo” (RECURSAR, 2018).
Recursão é o processo de definir algo em termos de si mesmo e é, algumas vezes, 
chamado de definição circular. Assim, pode-se dizer que o conceito de algo recursivo 
está dentro de si, que por sua vez está dentro de si e assim sucessivamente, 
infinitamente.
O exemplo a seguir define o ancestral de uma pessoa:
• Os pais de uma pessoa são seus ancestrais (caso base);
• Os pais de qualquer ancestral são também ancestrais da pessoa inicialmente 
considerada (passo recursivo).
(LAUREANO, 2008, p. 60).
RECURSIVIDADE
Definições como estas são normalmente encontradas na matemática. O 
grande apelo que o conceito da recursão traz é a possibilidade de dar uma 
definição finita para um conjunto que pode ser infinito [...]. Um exemplo 
aritmético:
O primeiro número natural é zero.
• O sucessor de um número natural é um número natural.
Na computação o conceito de recursividade é amplamente utilizado, mas difere 
da recursividade típica por apresentar uma condição que provoca o fim 
do ciclo recursivo. Essa condição deve existir, pois, devido às limitações 
técnicas que o computador apresenta, a recursividade é impedida de continuar 
eternamente.
(LAUREANO, 2008, p. 60).
RECURSIVIDADE
A função é recursiva se um comando no corpo da função a 
chama. Para uma linguagem de computador ser recursiva, uma 
função deve poder chamar a si mesma.
(LAUREANO, 2008, p. 61).
Possuem suporte a recursividade as linguagens C, C++, Java, 
Delphi, Visual Basic e muitas outras.
RECURSIVIDADE
Um exemplo simples [de recursividade] é a função fatorial, que calcula o 
fatorial de um inteiro. O fatorial de um número N é o produto de todos os 
números inteiros entre 1 e N. Por exemplo, 3 fatorial (ou 3!) é 1 * 2 * 3 = 6.
(LAUREANO, 2008, p. 61).
int fatorialI(int n)
{
int f = 1;
for(int i = 1; i <= n; i++)
f = f * i;
return f;
}
RECURSIVIDADE
int fatorialI(int n)
{
int f = 1;
for(int i = 1; i <= n; i++)
f = f * i;
return f;
}
int main()
{
int numero = 3;
cout << "O fatorial de " << numero << " e: " 
<< fatorialI(numero) << endl;
return 0;
}
RECURSIVIDADE
Mas multiplicar n pelo produto de todos os inteiros a partir de n-1 até 1 resulta no 
produto de todos os inteiros de n a 1. Portanto, é possível dizer que fatorial [de]:
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
Logo o fatorial de um número também pode ser definido recursivamente (ou por 
recorrência) através das seguintes regras (representação matemática) [...]:
n! = 1, se n = 0
n! = n * (n-1)! , se n > 0
(LAUREANO, 2008, p. 61).
RECURSIVIDADE
int fatorialR(int n)
{
// condição de parada.
if(n == 0)
return 1;
int f = fatorialR(n-1) * n; // chamada da função.
return f;
}
int main()
{
int numero = 3;
cout << "O fatorial de " << numero << " e: " 
<< fatorialR(numero) << endl;
return 0;
}
RECURSIVIDADE
int fatorialR(int n) { /* ... */ }
int main()
{
int numero;
cout<< "Informe o numero: "; cin>> numero; cout<<endl;
cout << "O fatorial de " << numero << " e: " 
<< fatorialR(numero) << endl;
return 0;
}
RECURSIVIDADE
A operação de fatorial recursiva é um pouco 
mais complexa. [...] Para calcular o fatorial de 6, 
[por exemplo,] o computador tem de calcular 
primeiro o fatorial de 5 e só depois é que faz a 
multiplicação de 6 pelo resultado (120). Por sua 
vez, para calcular o fatorial de 5, vai ter de 
calcular o fatorial de 4. Resumindo, aquilo que 
acontece internamente é uma expansão 
seguida de uma contração:
(LAUREANO, 2008, p. 62-63).
A versão não-recursiva de fatorial deve ser clara. Ela usa um laço que é executado de 1 
a n e multiplica progressivamente cada número pelo produto móvel.
(LAUREANO, 2008, p. 62).
fatorialR(6)
6 * fatorialR(5)
6 * 5 * fatorialR(4)
6 * 5 * 4 * fatorialR(3)
6 * 5 * 4 * 3 * fatorialR(2)
6 * 5 * 4 * 3 * 2 * fatorialR(1)
6 * 5 * 4 * 3 * 2 * 1
6 * 5 * 4 * 3 * 2
6 * 5 * 4 * 6
6 * 5 * 24
6 * 120
720
RECURSIVIDADE
Freqüentemente, soluções recursivas são mais fáceis de 
entender e implementar corretamente que as iterativas 
correspondentes. Existe uma certa elegância e economia 
de raciocínio nas soluções recursivas que as tornam 
mais atraentes. Como disse o cientista de computação (e 
criador do interpretador GhostScript para a linguagem de 
descrição de gráficas PostScript) L. Peter Deutsch: 
“Iterar é humano, usar recursividade é divino”.
(HORSTMANN, 2008, p. 513.).
RECURSIVIDADE: QUANDO NÃO USAR
O uso de algoritmos recursivos torna-se adequado quando o problema a ser 
resolvido, ou os dados tratados, são definidos em termos recursivos. Mas, 
definições de natureza recursiva, por si só, não garantem que um algoritmo 
recursivo seja o melhor caminho para resolver o problema. Quando o loop
recursivo é muito grande, isto consome muita memória nas chamadas 
a diversos níveis de recursão, pois cada chamada recursiva aloca 
memória para os parâmetros e as variáveis locais e de controle.
Em muitos casos, uma solução iterativa gasta menos memória 
e tem um desempenho mais eficiente do que uma solução 
recursiva.
1. Leia o artigo sobre recursividade, no website da TI EXPERT (disponível em: 
<http://www.tiexpert.net/programacao/c/recursividade.php>), e implemente o código da 
sequência de Fibonacci apresentado.
2. Implemente o algoritmo Euclidiano, descrito abaixo, em linguagem C++:
Calcule o máximo divisor comum de dois inteiros não-negativos P e Q do seguinte 
modo: se Q for 0, a resposta é P, se não, divida P por Q e obtenha o resto R; a resposta 
será o máximo divisor comum de Q e R.
3. Implemente uma função recursivaque some os elementos de um array de inteiros.
4. Implemente uma função recursiva que, dados dois números inteiros n e p, calcula o 
valor de np. Considere:
a) caso base: x0 = 1;
b) passo da recursão: xn = x * xn-1.
EXERCÍCIOS
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Ordenação [(sorting)] é o processo de arranjar um conjunto de informações 
semelhantes em uma ordem crescente ou decrescente [...].
(LAUREANO, 2008, p. 100).
Por exemplo, sua fatura do cartão de crédito apresenta transações por ordem 
de data - elas provavelmente foram postas assim por um algoritmo de 
ordenação.
(SEDGEWICK; WAYNE, 2011, p. 243).
Algoritmo de ordenação em ciência da computação é um algoritmo que 
coloca os elementos de uma dada sequência em uma certa ordem - em outras 
palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas 
são a numérica e a lexicográfica.
(LAUREANO, 2008, p. 100).
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Existem várias razões para se ordenar uma sequência, uma delas é a possibili-
dade [de] se acessar seus dados de modo mais eficiente.
(LAUREANO, 2008, p. 100).
Nos primórdios da computação, a sabedoria comum era que até 30% de 
todos os ciclos de computação eram gastos com ordenação. Se essa fração é
menor hoje, uma razão provável é que os algoritmos de ordenação se torna-
ram relativamente eficientes, não que a ordenação tenha diminuído em impor-
tância relativa. De fato, a ubiquidade do uso do computador nos inundou em 
dados e o primeiro passo para a organização dos dados é, muitas vezes, 
ordená-los [...].
(SEDGEWICK; WAYNE, 2011, p. 243).
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
[...] [O MergeSort] é um algoritmo de ordenação por intercala-
ção ou segmentação[, baseado no paradigma divisão e conquista
(divide-and-conquer)]. A idéia básica é a facilidade de criar uma 
seqüência ordenada a partir de duas outras também ordenadas. 
Para isso, o algoritmo divide a seqüência original em pares de 
dados, ordena-as; depois as agrupa em sequências de quatro 
elementos, e assim por diante, até ter toda a seqüência dividida 
em apenas duas partes.
(LAUREANO, 2008, p. 115).
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Os passos do algoritmo MergeSort são:
1. divisão: divide uma sequência em duas novas;
2. recursão: ordena recursivamente cada uma das sequências (dividindo 
novamente, se possível);
3. conquista: mescla (merge) as subsequências, para obter o resultado final.
(GOODRICH; TAMASSIA, 2007, p. 432.; LAUREANO, 2008, p. 115).
(MERGE SORT, 2018.).
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Os passos do algoritmo MergeSort são:
1. divisão: divide uma sequência em duas novas;
2. recursão: ordena recursivamente cada uma das sequências (dividindo 
novamente, se possível);
3. conquista: mescla (merge) as subsequências, para obter o resultado final.
(GOODRICH; TAMASSIA, 2007, p. 432.; LAUREANO, 2008, p. 115).
(MERGE SORT, 2018.).
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
5 2 9
0 1 2
5 2 9
0 1 2
5 2
0 1
2 5
0 1
2
0
5
1
9
2
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Simulação do funcionamento do algoritmo MergeSort:
<http://math.hws.edu/eck/js/sorting/xSortLab.html>.
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
Merge Sort in 3 minutes:
<https://www.youtube.com/watch?v=4VqmGXwpLqc>.
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
void mergeSort(int vetor[], int indiceEsquerdo, 
int indiceDireito)
{
if(indiceEsquerdo < indiceDireito)
{
int indiceMeio = ((indiceEsquerdo +
indiceDireito) /2);
mergeSort(vetor, indiceEsquerdo, indiceMeio);
mergeSort(vetor, (indiceMeio +1),
indiceDireito);
merge(vetor, indiceEsquerdo, indiceMeio,
indiceDireito);
}
}
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
void merge(int vetor[], int indiceEsquerdo, int indiceMeio, int 
indiceDireito)
{
int tamanhoEsquerdo = indiceMeio – indiceEsquerdo +1;
int vetorEsquerdo[tamanhoEsquerdo];
int tamanhoDireito = indiceDireito – indiceMeio;
int vetorDireito[tamanhoDireito];
int i, j;
// Carrega os elementos do vetor esquerdo.
for(i = 0; i < tamanhoEsquerdo; i++)
vetorEsquerdo[i] = vetor[indiceEsquerdo + i];
// Carrega os elementos do vetor direito.
for(j = 0; j < tamanhoDireito; j++)
vetorDireito[j] = vetor[indiceMeio + 1 + j];
//...
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
//...
i = 0;
j = 0;
int k = indiceEsquerdo;
// Faz a ordenação entre os vetores esquerdo e direito, e
// carrega o elemento ordenado no vetor principal.
while((i < tamanhoEsquerdo) && (j < tamanhoDireito))
{
if(vetorEsquerdo[i] <= vetorDireito[j])
{
vetor[k] = vetorEsquerdo[i];
i++;
}
else
{
vetor[k] = vetorDireito[j];
j++;
}
k++;
}
//...
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
//...
// Se restarem elementos no vetor esquerdo, carrega-os para o
// vetor principal.
while(i < tamanhoEsquerdo)
{
vetor[k] = vetorEsquerdo[i];
i++;
k++;
}
// Se restarem elementos no vetor direito, carrega-os para o
// vetor principal.
while(j < tamanhoDireito)
{
vetor[k] = vetorDireito[j];
j++;
k++;
}
}
MERGESORT: ALGORITMO DE ORDENAÇÃO POR INTERCALAÇÃO
#include <iostream>
using std::cout;
using std::endl;
void imprimeVetor(int vetor[], int tamanho)
{
for(int i = 0; i < tamanho; i++)
cout << " |" << vetor[i] << "| " << endl;
}
int main()
{
int n[3] = { 5, 2, 9 };
imprimeVetor(n, 3);
cout << endl;
mergeSort(n, 0, 2);
imprimeVetor(n, 3);
return 0;
}
1. Dada a sequência de números: 3 4 9 2 5 1 8, ordene-a de modo crescente, utilizando 
o algoritmo MergeSort.
2. Considerando o programa implementado para responder a questão 1, modifique o 
algoritmo MergeSort para fazer a ordenação decrescente.
3. No algoritmo MergeSort, o que acontece se trocarmos "(indiceEsquerdo + 
indiceDireito) / 2" por "(indiceEsquerdo + indiceDireito - 1) / 2"? E o que 
acontece se trocarmos "(indiceEsquerdo + indiceDireito) / 2" por 
"(indiceEsquerdo + indiceDireito + 1) / 2"? Implemente e teste essas 
mudanças.
EXERCÍCIOS
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
O QuickSort é um algoritmo de ordenação in-place
(in loco, ou seja, trabalhando sobre o próprio vetor), 
também baseado no paradigma divisão e conquista
(divide-and-conquer).
(LAUREANO, 2008, p. 111; SEDGEWICK; WAYNE, 2011, p. 288).
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
O quicksort [...] funciona particionando um array em dois subarrays e, então, 
ordenando-os independentemente.
O quicksort é complementar ao mergesort: no mergesort, nós 
quebramos o array em dois subarrays a serem ordenados e, então, os 
combinamos para formar um array ordenado inteiro; no no quicksortquicksort, n, nóós s 
reorganizamos o reorganizamos o arrayarray de tal modo que, quando os dois de tal modo que, quando os dois subarrayssubarrays
estiverem ordenados, o estiverem ordenados, o arrayarray inteiro tambinteiro tambéém estarm estaráá ordenadoordenado. No caso do 
mergesort, nós fazemos duas chamadas recursivas, antes de manipular o 
array inteiro; no caso do no caso do quicksortquicksort, fazemos as chamadas recursivas , fazemos as chamadas recursivas 
depois de manipular o depois de manipular o arrayarray inteirointeiro. No mergesort, o array é dividido no 
meio; no no quicksortquicksort, a posi, a posiçção da quebra depende do conteão da quebra depende do conteúúdo do do do arrayarray.
(SEDGEWICK; WAYNE, 2011, p. 288).
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
No quicksort, nós não buscamos mais o valor médio [(como no 
mergesort)], em vez disso, selecionamos um elemento, 
conforme uma estratégia (às vezes, aleatoriamente, 
às vezes, o da extrema esquerda, às vezes, o do 
meio), para particionar um array em subarrays.
(HEINEMAN; POLLICE; SELKOW, 2009, p. 85).
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
Os passos do QuickSort são:
1. Divisão: selecione um elemento da sequência (S), chamado de pivô (P). Retire P de 
S e particione os demais elementos em duas subsequências distintas, L e G, contendo,respectivamente, os elementos <= a P e os elementos >= a P;
2. Recursão: ordene as subsequências L e G, recursivamente.
3. Conquista: coloque de volta os elementos de S em ordem, inserindo: os elementos 
de L, o P e os elementos de G.
(GOODRICH; TAMASSIA, 2007, p. 442-443;
LAUREANO, 2008, p. 111-112).
(QUICKSORT, 2018.).
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
Simulação do funcionamento do algoritmo QuickSort:
<http://math.hws.edu/eck/js/sorting/xSortLab.html>.
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
Método de Ordenação - QuickSort:
<https://www.youtube.com/watch?v=oYmHH1-f_L0>.
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
void quickSort(int vetor[], int indiceEsquerdo, 
int indiceDireito)
{
int limiteEsquerdo = indiceEsquerdo;
int limiteDireito = indiceDireito;
int meio = ((limiteEsquerdo + limiteDireito) /2);
int pivo = vetor[meio];
// ...
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
while(limiteDireito > limiteEsquerdo)
{
// Se conteúdo vetor no limite esquerdo < pivô,
// não faz nada, porque ele está no lugar certo. 
while(vetor[limiteEsquerdo] < pivo)
limiteEsquerdo++; // Incrementa p/ continuar verificação.
// Se conteúdo vetor de limite direito > pivô,
// não faz nada, porque ele está no lugar certo. 
while(vetor[limiteDireito] > pivo)
limiteDireito--; // Decrementa p/ continuar verificação.
if(limiteEsquerdo <= limiteDireito) // Se se cruzarem...
{
int temp = vetor[limiteEsquerdo]; // Realiza inversão.
vetor[limiteEsquerdo] = vetor[limiteDireito];
vetor[limiteDireito] = temp;
limiteEsquerdo++; // Reajusta os limites.
limiteDireito--;
}
}
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
// Utiliza recursão p/ continuar ordenando
// (atualiza a faixa que está sendo analisada).
if(indiceEsquerdo < limiteDireito)
quickSort(vetor, indiceEsquerdo, limiteDireito);
if(limiteEsquerdo < indiceDireito)
quickSort(vetor, limiteEsquerdo, indiceDireito);
}
QUICKSORT: ALGORITMO DE ORDENAÇÃO RÁPIDA
#include <iostream>
using std::cout;
using std::endl;
void imprimeVetor(int vetor[], int tamanho)
{
for(int i = 0; i < tamanho; i++)
cout << " |" << vetor[i] << "| " << endl;
}
int main()
{
int n[3] = { 5, 2, 9 };
imprimeVetor(n, 3);
cout << endl;
quickSort(n, 0, 2);
imprimeVetor(n, 3);
return 0;
}
1. Dada a sequência de números: 3 4 9 2 5 1 8, ordene-a de modo crescente, utilizando 
o algoritmo QuickSort.
EXERCÍCIOS
LINEAR
Lista Linear
RECAPITULAÇÃO: TIPOS DE ESTRUTURAS DE DADOS
SEQUENCIAL
ENCADEADO
NÃO-LINEAR
SEQUENCIAL
Adaptado de BALIEIRO, 2015, p. 19.
nó
RECAPITULAÇÃO: TIPOS DE ESTRUTURAS DE DADOS
ENCADEADO
Adaptado de BALIEIRO, 2015, p. 136.
SIMPLESMENTE
ENCADEADA
RECAPITULAÇÃO: TIPOS DE ESTRUTURAS DE DADOS
RECAPITULAÇÃO: TIPOS DE ESTRUTURAS DE DADOS
// EXEMPLO DE LISTA LINEAR
// SIMPLESMENTE ENCADEADA.
struct No
{
int info;
struct No* proximo;
};
No* cabeca = new No;
cabeca->proximo = NULL;
No* primeiro = new No;
primeiro->info = 11;
primeiro->proximo = NULL;
cabeca->proximo = primeiro;
No* segundo = new No;
segundo->info = 12;
segundo->proximoNo = NULL;
primeiro->proximo = segundo;
No* noDeTeste;
noDeTeste = cabeca->proximo;
int indice = 1;
while(noDeTeste != NULL)
{
cout << "No numero: " << indice;
cout << ", info: " 
<< noDeTeste->info 
<< endl;
noDeTeste = noDeTeste->proximo;
indice++;
}
Adaptado de BALIEIRO, 2015, p. 137-138.
LINEAR
RECAPITULAÇÃO: TIPOS DE ESTRUTURAS DE DADOS
SEQUENCIAL
ENCADEADO
NÃO-LINEAR
ÁRVORES
As estruturas de dados do tipo ÁRVORE são não lineares, ou 
seja, os elementos que as compõem não estão armazenados de 
forma sequencial [ou encadeada] [...].
(ASCENCIO; ARAÚJO, 2010, p. 278).
ÁRVORES
Esquemas em árvores são utilizados para 
representar estruturas hierárquicas (árvores 
genealógicas, campeonatos de futebol ou 
organizações). Na ciência da computação, as 
árvores podem ser utilizadas para representar 
decisões, definições formais de linguagem ou 
mesmo [...] hierarquia entre elementos.
[...] [Este tipo de estrutura de dados] herda as 
características das topologias em árvore[,] onde 
os dados estão dispostos de forma hierárquica 
([ou seja,] um conjunto de dados é
hierarquicamente subordinado a outro).
(LAUREANO, 2008, p. 125).
Árvore genealógica
de Abraão, conforme
Gênesis (GOODRICH; 
TAMASSIA, 2007, p. 246).
ÁRVORES
Uma árvore é composta por um elemento principal[,] chamado raiz, que possui 
ligações para outros elementos, [...] denominados galhos ou filhos. Estes galhos levam 
a outros elementos que também possuem outros galhos. O elemento que não possui 
galhos é conhecido como folha ou nó terminal.
(LAUREANO, 2008,
p. 125-126).
ÁRVORES
(BARANAUSKAS, 2007, slide 10).
ÁRVORES
(BARANAUSKAS, 2007, slide 11).
(galhos)
ÁRVORES
(BARANAUSKAS, 2007, slide 12).
ÁRVORES
(BARANAUSKAS, 2007, slide 13-14).
ÁRVORES
(BARANAUSKAS, 2007, slide 15).
ÁRVORES
(BARANAUSKAS, 2007, slide 16).
ÁRVORES
(BARANAUSKAS, 2007, slide 19).
ÁRVORES
(BARANAUSKAS, 2007, slide 20).
ÁRVORES
(BARANAUSKAS, 2007, slide 29).
ÁRVORES
(BARANAUSKAS, 2007, slide 26).
ÁRVORES
(BARANAUSKAS, 2007, slide 41).
ÁRVORES BINÁRIAS
Árvore binária é uma estrutura de dados do tipo árvore, com grau 2.
Uma árvore binária é um conjunto finito de elementos[, que] [...] pode estar vazio ou 
ser particionado em três subconjuntos distintos, sendo eles: [nó raiz, sub-árvore 
direita e sub-árvore esquerda] [...]. 
(ASCENCIO; ARAÚJO, 2010, p. 278).
Árvore binária, representando a expressão:
[a + (b / c)] * [d – (e * f)].
ÁRVORES BINÁRIAS
As árvores binárias podem ser ilustradas de três formas 
distintas, conforme [abaixo] [...].
(ASCENCIO; ARAÚJO, 2010, p. 279).
ÁRVORES BINÁRIAS
Toda árvore binária possui as seguintes propriedades:
a) Todos os nós de uma sub-árvore direita são maiores que o nó raiz.
b) Todos os nós de uma sub-árvore esquerda são menores que o nó raiz.
c) Cada sub-árvore é também uma árvore binária.
d) O grau de um nó representa o seu número de sub-árvores [...].
e) Em uma árvore binária, o grau máximo de um nó é 2.
(ASCENCIO; ARAÚJO, 2010, p. 279-280).
ÁRVORES BINÁRIAS
h) Nó pai [...]: nó acima e com ligação direta a outro nó.
i) Nó filho [...]: nó abaixo e com ligação direta a outro nó. São raízes das sub-árvores.
j) Nós irmãos [...]: são os nós que possuem o mesmo nó pai.
k) Nó folha ou terminal [...]: nó que não possui filhos.
(ASCENCIO; 
ARAÚJO, 
2010, p. 280).
ÁRVORES BINÁRIAS
s) Árvore estritamente binária [...]: árvore em que todos os nós têm 0 ou 2 filhos.
t) Expressão que representa o número de nós de uma árvore estritamente binária = 
2n - 1, onde n é o número de nós folha [...].
(ASCENCIO; ARAÚJO, 2010, p. 283).
ÁRVORES BINÁRIAS
u) Árvore completa [...]: árvore em que 
todos os nós com menos de dois filhos 
ficam no último e no penúltimo nível.
(ASCENCIO; ARAÚJO, 2010, p. 284).
v) Árvore cheia [...]: árvore 
estritamente binária e completa.
(ASCENCIO; ARAÚJO, 2010, p. 284).
1. Represente uma árvore binária, conforme a expressão aritmética: 
{[(3 + 6) * (4 - 1)] + 5}. Observação: os nós-folha representam os 
operandos e os nós internos, os operadores.
2. Para a árvore binária abaixo, responda:
a) Qual o grau desta árvore?
b) Quantos níveis possui essa árvore?
c) Quantos nós e arestas possui 
esta árvore?
d) Quantos nós não-folha 
possui esta árvore?
e) Informe o grau de cada 
um dos nós.
f) Indique os 
nós-folha.
EXERCÍCIOS
ÁRVORES BINÁRIAS DE BUSCA
Uma árvore de busca binária (Binary search tree) é uma árvore binária onde a 
informação que o nó esquerdo possui é menor ou igual à informação da chave 
[e] [...] a informação que o nó direito possui é maior ou igual à informação da 
chave. O objetivo de organizar dados em árvores de busca binária é facilitar a 
tarefa de procura de um determinado valor. A partir da raiz e de posse da 
informação a ser encontrada, é possível saber qual o caminho (galho) a ser 
percorrido até encontrar o nó desejado. Para tanto, basta verificar se o valorprocurado é maior, menor ou igual ao nó que se está posicionando.
(LAUREANO, 2008, p. 129).
ÁRVORES BINÁRIAS DE BUSCA
Deve-se observar que não existe uma única forma de organizar um conjunto de 
informações em uma árvore de busca binária, ainal, dependendo da escolha do nó raiz, 
obtêm-se árvores diferentes. Na figura [abaixo,] [...] os valores ({ 2, 3, 5, 5, 7, 8}) são 
organizados em árvores de busca de duas maneiras diferentes.
(LAUREANO, 2008, p. 129).
ÁRVORES BINÁRIAS DE BUSCA
As duas árvores contêm exatamente os mesmos valores, porém possuem estruturas 
diferentes. Enquanto a árvore A está enraizada em um dos nós de valor 5, a árvore B 
está enraizada no nó de valor 2. Supondo que se está buscando o valor 8 nas árvores, 
as comparações seriam como se segue na tabela [ao lado] [...].
(LAUREANO, 2008, p. 130).
ÁRVORES BINÁRIAS DE BUSCA
Na árvore A, são realizadas menos comparações em relação à utilizada na árvore B. O 
melhor caso irá ocorrer quando a árvore estiver cheia, neste caso a procura de um 
item terá tempo proporcional a log n, enquanto o pior caso ocorrerá quando todos os 
nós da árvores apontarem somente para um dos lados, caso em que o tempo de 
processamento da procura será proporcional a n.
(LAUREANO, 2008, p. 130).
IMPLEMENTANDO ÁRVORES BINÁRIAS
// Cada nó da árvore binária.
struct No
{
int num;
No* esq;
No* dir;
}
void main()
{
No* raiz = NULL;
No* novo = new No();
novo->num = 11;
novo->dir = NULL;
novo->esq = NULL;
raiz = novo;
}
ASCENCIO; ARAÚJO, 2010, p. 303-305.
PERCURSO EM ÁRVORE
Existem três ordens para se percorrer uma árvore:
• Pré-ordem (preorder): r, e, d;
• Em ordem (inorder): e, r, d;
• Pós-ordem (postorder): e, d, r
PERCURSO EM ÁRVORE
INSERÇÃO & REMOÇÃO
Vide “Estácio Algoritmos 
Avançados Aula10.txt”.
1. Explique, por meio de desenho, como funciona o percurso em árvores.
EXERCÍCIOS
ÁRVORES AVL
A árvore AVL, criada em 1962 por Adelson-Velsky e Landis, é uma árvore binária 
balanceada, ou seja, é uma árvore que obedece a todas as propriedades da árvore 
binária e em que cada nó apresenta diferença de altura entre as sub-árvores direita e 
esquerda de 1, 0 ou -1, como ilustra a [figura abaixo] [...].
(ASCENCIO; ARAÚJO, 2010, p. 329).
GRAFOS
Um grafo G é formado pelo par de conjuntos V [(vértices/nós)] e [A (arestas)] [...]. 
Dois vértices ligados por uma aresta são denominados adjacentes [...]. A 
representação geométrica dos grafos é feita marcando pontos distintos no plano para 
representar os vértices, e uma linha ligando dois pontos para representar a aresta. 
Três exemplos de grafos são apresentados na [figura abaixo] [...]. Os vértices podem 
ou não possuir nomes. Quando recebem nomes, estes podem ser números ou letras. 
Quando são nomeados por letras, é necessário fazer um mapeamento de cada nome de 
vértice para um número correspondente [...].
(ASCENCIO; ARAÚJO, 2010, p. 368).
GRAFOS
Laços, arestas múltiplas e multigrafo
É possível encontrar em um grafo arestas [...] com as extremidades [...] iguais. 
Quando isso ocorre, a aresta é denominada laço. É também possível a existência de 
mais de uma aresta entre o mesmo par de vérticas, chamadas de arestas paralelas ou 
arestas múltiplas. Um grafo que possui arestas paralelas é denominado multigrafo. Na 
Figura 8.2(a) é apresetnado um grafo com laço, e nas Figura 8.2(b) é apresentado um 
multigrafo.
(ASCENCIO; ARAÚJO, 2010, p. 369).
GRAFOS
Grafo trivial e grafo simples
Um grafo com apenas um vértice é chamado de grafo trivial. Um grafo G é chamado 
grafo simples se não possui laço ou aresta múltipla. Os grafos da Figura 8.2 não são 
grafos simples, já os grafos da Figura 8.1 são.
(ASCENCIO; ARAÚJO, 2010, p. 369).
GRAFOS
Grafo completo
Um grafo G é chamado grafo completo quando existe uma aresta para cada par de 
vérticas distintos de G. Na Figura 8.3 são apresentados exemplos de grafos completos 
com 3, 4 e 5 vértices, respectivamente.
(ASCENCIO; ARAÚJO, 2010, p. 369).
GRAFOS
Um grafo G(V,A) com |V| = n pode ser representado adequadamente por meio de 
matrizes ou listas. [...] Dado um grafo G(V,A), uma matriz de adjacências M é formada 
por n linhas e n colunas, sendo n o número de vértices do grafo. A matriz é preenchida 
da seguinte forma:
A Figura 8.14 apresenta um grafo não direcionado e sua matriz de adjacências.
(ASCENCIO; ARAÚJO, 2010, p. 375).
ASCENCIO, Ana Fernanda G.; ARAÚJO, Graziela S. Estruturas de Dados: 
Algoritmos, Análise de Complexidade e Implementações em Java e C++. São 
Paulo: Pearson Prentice Hall, 2010.
BALIEIRO, Ricardo. Estrutura de Dados. Rio de Janeiro: SESES, 2015.
BARANAUSKAS, José Augusto. Árvores. Universidade de São Paulo, Departamento 
de Física e Matemática, 2007. 74 slides: color. Disponível em: 
<http://dcm.ffclrp.usp.br/~augusto/teaching/aedi/AED-I-Arvores.pdf>. Acesso em: 18 set. 
2018.
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em 
Java. Tradução Bernardo Copstein, Leandro Bennto Pompermeier. 4. ed. Porto Alegre: 
Bookman, 2007.
HEINEMAN, George T.; POLLICE, Gary; SELKOW, Stanley. Algorithms in a Nutshell.
Sebastopol: O’Reilly, 2009.
HORSTMANN, Cay. Conceitos de Computação com o Essencial de C++. Tradução 
Carlos Arthur Lang Lisbôa e Maria Lúcia Blanck Lisbôa. 3. ed. São Paulo: Bookman, 
2008.
REFERÊNCIA BIBLIOGRÁFICA
LAUREANO, Marcos. Estrutura de Dados com Algoritmos e C. Rio de Janeiro: 
Brasport, 2008.
MERGE SORT. Wikipédia. Disponível em: <https://pt.wikipedia.org/wiki/Merge_sort>. 
Acesso em: 03 set. 2018.
QUICKSORT. Wikipédia. Disponível em: <https://pt.wikipedia.org/wiki/Quicksort>. 
Acesso em: 11 set. 2018.
RECURSAR. Dicionário Priberam da Língua Portuguesa online, 2008-2013. Disponível 
em: <https://www.priberam.pt/dlpo/recursar>. Acesso em: 28 ago. 2018.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4th ed. Boston: Addison-Wesley, 
2011.
TOAL, Ray. Algorithm Analysis. Notes. Loyola Marymount University, College of 
Science and Engineering, Computer Science Division. Disponível em: 
<http://cs.lmu.edu/~ray/notes/alganalysis/>. Acesso em: 15 ago. 2018a.
TOSCANI, Laira V.; VELOSO, Paulo A. S. Complexidade de Algoritmos: Análise, 
Projeto e Métodos. 3. ed. Porto Alegre: Bookman, 2012. 13 v.
REFERÊNCIA BIBLIOGRÁFICA
VRAJITORU, Dana; KNIGHT, William. Practical Analysis of Algorithms. [S.l.]: 
Springer, 2014.
REFERÊNCIA BIBLIOGRÁFICA