APOSTILA - PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO - UNIDADE 4 (ANHEMBI MORUMBI UAM) CURTA SE LHE AJUDOU! ;D

•
UAM

Franklin Ferreira Moreira
10/09/2022
E aí, curtiu este material?
Ajude a incentivar outros estudantes a melhorar o conteúdo
Gostou desse material? Compartilhe! 🧡
Técnicas de Pesquisa e Ordenação I

94 Materiais compartilhados
Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Prévia do material em texto
PESQUISA,	ORDENAÇÃO	E	TÉCNICAS	DE
ARMAZENAMENTO
UNIDADE 4 - TE� CNICAS DE PESQUISAS
SEQUENCIAL E BINA� RIA
Keila Barbosa Costa
Introdução
A busca por uma palavra-chave ou por elementos, valores ou dados especı́�icos (informações) é a base de
muitos aplicativos de computação. Serve para visualizar o saldo de uma conta bancária a partir de um
mecanismo de pesquisa na internet, por exemplo, ou para procurar um arquivo no computador. Este,
inclusive, lida com muitos dados, por isso, precisamos de algoritmos e�icientes para a pesquisa.
No entanto, que tipos de algoritmos podem ser e�icientes? Como os computadores precisam buscar
informações em coleções de dados muito grandes, é essencial usar o algoritmo certo para pesquisar, mas
como de�inir o algoritmo adequado para cada situação? Será que podemos aplicar métodos de pesquisas
binária ou sequencial com os dados organizados de qualquer forma?
A pesquisa é o processo de encontrar o elemento em determinada lista. Neste processo, veri�icamos que o
item está disponı́vel ou não. A pesquisa está em toda parte, desde encontrarmos o endereço de uma pessoa até
um número de telefone em uma lista telefônica. Neste contexto, ao longo desta última unidade, iremos
explorar algoritmos comuns que são usados para procurar dados em computadores.
Aprenderemos sobre pesquisa binária em vetores e pesquisa sequencial. Veremos a respeito das
particularidades de cada uma e como são aplicadas no dia a dia dos pro�issionais da área. Também
estudaremos a respeito das tabelas de dispersão e das árvores de busca.
Vamos, então, nos aprofundar a respeito desses assuntos? Acompanhe!
4.1 Técnicas de pesquisas
Podemos de�inir como dado um conjunto de elementos, em que cada um é identi�icado por uma chave. O
objetivo da pesquisa é localizar, dentro desse conjunto, o elemento que corresponde a uma chave especı́�ica.
Assim, uma tarefa bastante importante, hoje — não só na computação como também em outras áreas —, é a
pesquisa de informação contida em coleções de dados. De forma geral, é desejado que o procedimento seja
realizado de forma que não tenha a necessidade de se veri�icar toda a coleção (VIANA; CINTRA; NOBRE 2015).
A busca é muito comum na área da computação, sendo que podemos usar métodos e estruturas de dados para
se encontrar o elemento esperado. A busca em vetor, por exemplo, pode ser feita por ı́ndice ou valor.
A busca realizada pelo índice é considerada uma busca direta, ou seja, vai direto na posição da memória.
Podemos tomar como exemplo o quadro a seguir com o vetor “nome”. Passando no ı́ndice 2, terı́amos o valor
“Khyonara”. 
Quadro 1 - Exemplo de quadro com vetores
#PraCegoVer: A �igura mostra uma tabela de duas linhas e 4 colunas. Na primeira linha, da esquerda para a
direita, temos os valores: 0, 1, 2, 3, 4. Na segunda linha, da esquerda da direita, temos os valores: Keila, Arthur,
Khyonara, Berenice, Aparecido. 
 
Agora, vamos imaginar que não sabemos onde o valor “Khyonara” está. Neste caso, temos que veri�icar todos
os elementos do vetor até encontrá-lo.
Portanto, para realizar a busca por um valor, temos dois métodos a serem considerados: realizamos uma
busca sequencial ou uma busca binária.
A busca	sequencial percorre todas as posições do vetor, veri�icando uma a uma, até achar o valor desejado
ou simplesmente chegar ao �inal sem achá-lo. Já na busca	binária, o vetor é dividido ao meio e a busca é
realizada apenas em uma das metades.
Vamos entender melhor sobre os dois métodos a partir de agora. No próximo item, ainda mostraremos
exemplos de como o processo é realizado dentro da computação. 
4.1.1 Busca sequencial
De acordo com Viana, Cintra e Nobre (2015), a busca sequencial é de�inida como a procura por um valor x em
um vetor	L. Inspecionando em sequência as posições de L a partir da primeira posição, podemos encontrar o
x. Ao encontrar o elemento procurado, podemos dizer que a busca obteve sucesso. Caso contrário, se
chegarmos à última posição sem encontrarmos a posição desejada, concluı́mos que ela não ocorre no vetor L.
Vamos imaginar o mesmo vetor “nome”, em que desejamos encontrar o nome “Khyonara”. Como isto pode ser
realizado? Comparando elemento a elemento, ou seja, o valor que está no ı́ndice pelo valor a ser procurado.
#PraCegoVer: A �igura mostra um exemplo de busca sequencial. Primeiramente é mostrado um vetor de 4
posições com os seguintes valores: Keila, Arthur, Khyonara, Berenice, Aparecido. 
 
Em seguida, mostra-se um passo a passo para encontrar o nome Khyonara. O passo a passo é mostrado
através de uma série de comparações. As comparações são: 
 
Figura 1 - Exemplo de busca sequencial
1 comparação: Keila == Khyonara? Não 
2 comparação: Arthus == Khyonara? Não 
3 comparação: Khyonara == Khyonara? Sim 
 
Achou o nome do ı́ndice 2. 
 
Por �im, mostrasse outro passo a passo. Desta vez, o objetivo é encontrar o nome José. O passo a passo
também é mostrado através de uma série de comparações. As comparações são: 
 
1 comparação: Keila == José? Não 
2 comparação: Arthur == José? Não 
3 comparação: Khyonara == José? Não 
4 comparação: Berenice == José? Não 
5 comparação: Aparecido == José? Não 
 
Achou o nome do ı́ndice 2. 
 
De acordo com a �igura anterior, temos a primeira comparação realizada. Nela, percorremos o valor que está
na posição 0. Ele é igual ao valor que estamos procurando (Khyonara)? Na verdade, não!
Incrementando o ı́ndice e realizando a mesma veri�icação, podemos dizer que o valor que está na posição ou
no ı́ndice 1 é o mesmo que estamos procurando? Arthur é igual a Khyonara? Também não, certo?
Incrementando novamente o ı́ndice e realizando mais uma comparação, podemos dizer que o ı́ndice 2 é igual
ao valor que estamos procurando? Khyonara é igual a Khyonara? Sim! Assim, encontramos nosso elemento a
partir da posição do ı́ndice que está no valor buscado.
Agora, imagine que iremos procurar o nome José. Perceba que ele não se encontra no vetor que estamos
analisando, por isso, o algoritmo irá parar de executar quando chegar ao �inal, retornando e informando que
não foi encontrado o nome desejado.
No entanto, imaginemos que o vetor tenha mais de um milhão de posições, sendo que o valor desejado não se
encontra no vetor. Será necessário, então, realizar um milhão de veri�icações para se descobrir que o valor não
se encontra no vetor a ser veri�icado. Isto ocorre com frequência na busca sequencial, sendo que, para
resolver o problema de o algoritmo ter que veri�icar elemento por elemento, podemos usar a busca binária.
Na busca binária, o vetor precisa estar ordenado. A mesma lógica serve para números, textos ou letras. Assim,
agora que você já conhece o processo de como fazer uma busca sequencial, iremos conhecer como se dá a
busca binária. Vejamos!
4.1.2 Busca binária
A busca binária só funciona em vetores que estejam ordenados. Isto porque ela divide sucessivamente o vetor
ao meio e procura apenas em uma das metades, ou seja, o algoritmo é executado até encontrar o valor ou
posição.
Vamos ver um exemplo com a �igura a seguir. Observe com atenção!
#PraCeoVer: A �igura mostra um exemplo de busca binária. Inicialmente é mostrado um vetor de 12 posições
com os seguintes valores: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24. Abaixo do vetor tem duas frases destacando
duas posições do vetor. As frases são respectivamente: Posição inicial = 0 e Posição �inal = 11. 
 
Em seguida, mostra-se o mesmo vetor. Contudo, mudou-se as frases que indicam as posições em destaque.
Desta vez, temos 3 frases, que são, respectivamente: Posição inicial = 6, Meio = 8 e Final = 11. 
 
Depois disso, mostra-se o mesmo vetor novamente. Desta vez, houve outra alteração nas frases que destacam
algumas posições do vetor. As frases são, respectivamente: Posição inicial = 9, Meio = 10 e Final = 11. 
 
Por �im, mostra-se novamente esse mesmo vetor com uma única frase destacando umaúnica posição. A frase
diz: Posição inicial = 20. 
 
Imagine o vetor ordenado na �igura anterior. Pretendemos procurar o elemento 20, por isso, a primeira coisa
que o vetor irá fazer é descobrir a posição inicial (0) e, depois, a posição �inal (11). Será realizado o seguinte
cálculo:
	
meio = (posiçaoInicial + posicaoFinal) / 2
meio = (0 + 11) / 2
meio = 5.5 (Arredondar para o inteiro mais próximo 5)
	
Temos, assim, que a quinta posição será a posição do meio, com valor igual a 12.
Encontrada a posição do meio, será realizada a veri�icação a seguir:
 
Se (meio = numeroProcurado) (18 = 20)
Achou o valor
Do contrário
Se (numeroProcurado < meio) (20 < 18)
posiçãoFinal = meio - 1
Do contrário
posiçãoInicial = meio + 1 // Realizar novamente a posição inicial.
Figura 2 - Exemplo de busca binária
	
Dessa forma, podemos veri�icar o número procurado, ou seja, se o elemento do meio é igual ao número
procurado (12 = 20). Como a a�irmação é falsa, segue-se, então, para 20 < 12. Como a a�irmação também não é
verdadeira, o vetor irá andar com a posição inicial.
Como a posição inicial era 0, agora ele vai passar a ser: posiçãoInicial = meio + 1 = 5 + 1 = 6), então, recebe a
posição 6. Perceba que a posição 6 tem o valor 14.
A parte do vetor com valor menor que 12 (< posição 5) foi desconsiderada, pois, como o vetor está ordenado,
iremos considerar apenas da posição 6 até a 11.
Com a posição inicial 6 e a posição �inal 11, é realizado um cálculo para obtermos a posição meio, como
vemos a seguir, até se alcançar a posição desejada. No nosso caso, trata-se da posição 9. Observe:
 
meio = (posiçaoInicial + posicaoFinal) / 2
meio = (6 + 11) / 2
meio = 8.5 (inteiro 8) vetor formado por números inteiros.
 
Realizando a veri�icação, temos:
 
Se (meio == numeroProcurado) (12 = 20)
Achou o valor
Do contrário
Se (numeroProcurado < meio) (20 < 12)
posiçãoFinal = meio - 1
Do contrário
posiçãoInicial = meio + 1
	
Assim, foram necessárias muitas veri�icações até se encontrar o elemento desejado, porém, se fossemos usar
a veri�icação da busca sequencial, seriam necessárias ainda mais veri�icações. Isto é, para a busca sequencial,
terı́amos que realizar 10 veri�icações, enquanto a busca binária realizou apenas três.
VAMOS PRATICAR?
De acordo com o que vimos, imagine o vetor ordenado a seguir. Pr
elemento 22 usando a busca binaria.
#PraCegoVer: A �igura mostra um vetor de 10 posições. Os valores armazenados nesse vetor, são,
respectivamente: 3, 7, 9, 11, 12, 14, 15, 22, 23 ,25.
Agora que já entendemos a respeito das buscas sequencial e binária, no tópico a seguir, veremos com mais
detalhes a respeito das tabelas de dispersão, também conhecidas como tabelas de espalhamento ou tabelas de
hashing. Acompanhe!
4.2 Tabelas de dispersão
Um paradigma muito comum no processamento de dados envolve o armazenamento de informações em uma
tabela e, posteriormente, a recuperação dos dados guardados. Por exemplo, considere um banco de dados de
registros de carteira de trabalho: ele contém um registro para cada carteira de trabalho emitida, sendo que,
dado o número da carteira de trabalho, podemos procurar as informações associadas a ele. 
Normalmente, o banco de dados compreende uma coleção de pares e valores. As informações são recuperadas
do banco a partir de uma determinada chave. No caso do banco de dados da carteira de trabalho, a chave é o
número da carteira de trabalho. Já no caso de uma tabela de sı́mbolos, por exemplo, a chave é o nome do
sı́mbolo.
Viana, Cintra e Nobre (2015) nos explicam que podemos de�inir as tabelas de dispersão, também conhecidas
como tabelas de espalhamento ou de hashing, como aquelas que armazenam uma coleção de valores, sendo
que cada valor está associado a uma chave. As chaves precisam ser todas diferentes, pois são usadas para
mapear os valores das tabelas.
As vantagens da tabela de dispersão é que ela pode ser usada como ı́ndice, porém a grande vantagem está em
se ter uma operação cujo acesso é direto. Isto é, não será preciso fazer um percurso em uma árvore ou
comparar registro. Ainda de acordo com Viana, Cintra e Nobre (2015), outra vantagem é o curso da operação
O(1) acesso, em que a determinação da posição onde o registro será armazenado virá de uma função hashing.
A ideia essencial por trás de uma tabela de dispersão é que todas as informações são armazenadas em uma
matriz de tamanho �ixo. O hashing é usado para identi�icar a posição em que um item deve ser armazenado.
Quando acontece uma colisão, o item em colisão é armazenado em outro lugar na matriz (VIANA; CINTRA;
NOBRE, 2015).
Os tipos de hashings podem ser divididos em. Clique no recurso a seguir.
A função de hashing será responsável por converter a chave em um ı́ndice de alocação. Vejamos um exemplo
de função de dispersão:
h(chave) endereço
Função: h(x) = x mod 7, em que x é a chave e h(x) é o endereço
h(4315) 615, em que 4315 é a chave e 615 é o endereço
Hashing
fechado
Em que é permitido armazenar um conjunto de informações de tamanho limitado. 
Hashing
aberto
Em que é permitido armazenar um conjunto de informações de tamanho ilimitado. 
Assim, temos que a função hashing vai ditar o desempenho do algoritmo, trazendo o ponto em que devemos
armazenar o registro. O segredo está na qualidade da função hashing,	ou seja, quanto melhor for a função,
mais dispersos os registros serão.
Além disso, o hashing funciona da seguinte forma: a chave D1 passa pela função que é convertida no ı́ndice 1,
enquanto a chave D2 passa pela função que vai ser convertida no ı́ndice 2. Veja o esquema a seguir para
compreender melhor.
#PraCegoVer: A �igura mostra um exemplo de uma função de hashing. No centro da imagem é mostrado um
cı́rculo contendo o texto: Função hashing. Conectado a esse cı́rculo tem mais outros 4 cı́rculos. Um dos
cı́rculos está posicionado no canto superior esquerdo e possui o texto "D1". Outro cı́rculo está posicionado no
canto superior direito e possui o texto "[1]". O terceiro cı́rculo está posicionado no canto inferior esquerdo e
possui o texto "D". Por �im, o último cı́rculo está posicionado no canto inferior direito e possui o texto "[2]". 
 
VAMOS PRATICAR?
De acordo com a função de hashing, encontre o endereço para a chave h
Adote a fórmula “Função: h(x) = x mod 5”.
Figura 3 - Função hashing
Agora, vejamos um exemplo de como a função de hashing funciona em uma tabela de dados. Observe o quadro
na sequência.
#PraCegoVer: A �igura mostra uma tabela para descrever a função de hashing. A tabela possui 8 linhas e 4
colunas. 
 
Na primeira linha, temos a colunas (1) com valor "I�ndice", coluna (2) com valor "Chave", coluna (3) com o
valor "Valor", coluna (4) com o valor "Função: h(x) = x mod 7". 
 
Na segunda linha, temos a coluna (1) com o valor "0". 
 
Na terceira linha, temos a coluna (1) com o valor "1". 
 
Na quarta linha, temos a coluna (1) com o valor "2", coluna (2) com o valor "30", coluna (3) com o valor
"Khyonara", coluna (4) com o valor "h(x) = x mod 7 = 30/7". 
 
Na quinta linha, temos a coluna (1) com o valor "3", coluna (2) com o valor "45", coluna (3) com o valor
"Keila", coluna (4) com o valor "h(x) = x mod 7 = 45/7". 
 
Na sexta linha, temos a coluna (1) com o valor "4". 
 
Na sétima linha, temos a coluna (1) com o valor "5", coluna (2) com o valor 40, coluna (3) com o valor
"Arthur", coluna (4) com o valor "h(x) = x mod 7 = 40/7". 
 
Observe que o valor 30 não está na posição 0, mas, sim, na posição 2, devido à fórmula, ou seja, h(x)	=	x	mod
7	=	30/7	 ˜=	4,2 . Como o restante é aproximadamente 2, temos para a chave 30 o lugar de alocação para a
posição 2. Da mesma forma procede para as demais chaves.
Agora, digamos que desejamos incluir uma nova chave que também na divisão com 7 gere um resto 2. A este
caso damos o nome de colisão ou hashing	fechado	(hash	over�low). 
Quadro 2 - Processo da função hashing
A colisão acontece quandodeterminado ı́ndice (posição no vetor) gerado por uma chave se encontra alocado
por um registro. Isto é, quando o valor de uma chave ganha uma posição que já está cheia. Vejamos um
exemplo na �igura a seguir.
VOCÊ SABIA?
O hash	 over�low é quando tentamos inserir um elemento-chave na tabela de
dispersão, mas a tabela já se encontra cheia, invalidando essa inserção. Neste caso,
dizemos que aconteceu um estouro de tabela de dispersão.
#PraCegoVer: A imagem mostra o processo de hashing fechado. Inicialmente mostra-se a palavra
"chave|informação" que possui uma seta conectando com a palavra "Função" e por sua vez, possui uma seta
apontando para a palavra "função". Abaixo desta palavra está escrito "vetor com as posições". 
 
Em seguida, é mostrado uma tabela com 13 linhas e 4 colunas. Enumerando cada linha destas tabelas temos: 
 
Linha 1: Chave, Resto, Adote: h(x) = x mod m, 84, 0 
Linha 2: 47, 5, h(47) = 47 mod 14 = 5, 70*, 1 
Linha 3: 9, 9, h(9) = 9 mod 14 = 9, 25*, 3 
Linha 4: 75, 5, …, 47, 4 
Linha 5: 16, 2, …, 47, 4 
Linha 6: 24, 10, …, 75, 5 
Linha 7: 52, 10, …, 34*, 6 
Linha 8: 84, 0, …, 12*, 7 
Linha 9: 70, 0, …, , 8 
Figura 4 - Processo de hashing fechado
Linha 10: 10, 10, …, 9,9 
Linha 11: 25, 11, …, 24, 10 
Linha 12: 34, 6, …, 52*, 11 
Linha 13: 12, 12, …., h(12), 12 mod 14 = 12, 10*, 12 
 
Na �igura anterior, temos o esquema de como funciona o hashing fechado, em que temos o dado com a chave
que é convertida pela função, em um ı́ndice no qual será alocada a informação.
Podemos observar que nas chaves 24 e 52 acontece uma colisão, pois as duas têm um resto 10, ou seja,
precisam ser alocadas na mesma posição 10. Porém, a posição já tem uma chave alocada que chegou primeiro
(24). Neste caso, o que fazemos com a chave que precisa ser alocada, sendo que sua posição já está ocupada
por outra chave?
O 24 já está alocando a posição 10, então, a chave 52 vai procurar a próxima posição vazia, que seria a 11.
Portanto, a chave 52 �icará na posição 11 com asterisco (*), deixando claro que se trata de uma chave
deslocada. Na implementação real, adotamos que cada entrada H[i] da tabela é uma lista, cujo elemento têm
hash	code	i. Para inserir um elemento na tabela, computamos o hash	code	i e inserimos o elemento na lista
ligada à H[i].
A inserção é realizada seguindo a ordem de cima para baixo na tabela, sendo que, ao �inal da lista, retorna-se
para o inı́cio, seguindo o ciclo novamente.
A chave deslocada só sai da posição também deslocada se for para ir à sua respectiva posição, de acordo com
a função.
A técnica de hashing	aberto, por outro lado, denota que, em uma tabela, cada posição possui um ponteiro
que dá para uma lista encadeada, sendo que esta contém todas as chaves mapeadas por uma função hashing na
posição (VIANA; CINTRA; NOBRE, 2015). Aliás, na técnica aberta, não existe limite de chaves que podem ser
armazenadas na tabela.
A primeira estratégia, comumente conhecida como hashing aberto ou encadeamento separado, é manter uma
lista de todos os elementos com hashing no mesmo valor. Vejamos um exemplo concreto na tabela a seguir,
em que é possı́vel observar na posição 10 duas colisões. Assim, foram adicionados dois campos extras para
alocar as posições.
#PraCegoVer: A �igura mostra o processo de hashing aberto. O processo é descrito através de uma tabela
contendo 13 linhas e 8 colunas. Enumerando cada linha da tabela temos: 
 
Linha 1: Chave, Resto, adote: h(x) = x mod m, 0, -> , 84, 70, 
Linha 2: 47, 5, h(47) = 47 mod 14 = 5, 1 
Linha 3: 9, 9, h(9) = 9 mod 14 = 9, 2, ->, 16 
Linha 4: 75, 5, …, 3 
Linha 5: 16, 2, …, 4, 
Linha 6: 24,10, ..., 5, ->, 47, 75 
Linha 7: 52, 10, …, 6, ->, 34 
Linha 8: 84, 0, …, 7 
Linha 9: 70, 0, …, 8 
Linha 10: 10, 10, …, 9, -> , 9 
Linha 11: 25, 11, …, 10, ->, 24, 52, 10 
Linha 12: 34, 6, …, 11, ->, 25 
Linha 13: 12, 12, h(12) = 12 mod 14 = 12, 12, -> 12 
 
Para realizar uma localização, usamos a função hash para determinar qual lista percorrer. Em seguida,
percorremos a lista da maneira normal, retornando à posição em que o item foi encontrado. Para executar uma
inserção, percorremos a lista apropriada para veri�icar se o elemento já está no lugar. Se são esperadas
duplicatas, geralmente um campo extra é mantido e este seria incrementado no caso de uma correspondência
(VIANA; CINTRA; NOBRE, 2015). Se o elemento for novo, ele será inserido na frente da lista ou no �inal. Este é
Tabela 1 - Processo de hashing aberto
um problema fácil de resolver enquanto o código está sendo gravado. A� s vezes, novos elementos são
inseridos na frente da lista, pois é conveniente e também porque frequentemente acontece que os elementos
inseridos recentemente têm maior probabilidade de serem acessados em um futuro próximo.
#PraCegoVer: A �igura mostra uma tabela com 7 linhas e 8 colunas. Enumerando cada linha da tabela temos: 
 
Linha 1: Chave, Resto, Adote: h(x) = mod 3 , 0,,,,, 
Linha 2: 50, , Adote: h(x) = mod 3 , 1,,,,, 
Linha 3: 23, , Adote: h(x) = mod 3 , 2,,,,, 
Linha 4: 45, , Adote: h(x) = mod 3 , 3,,,,, 
Linha 5: 17, , Adote: h(x) = mod 3 , 4,,,,, 
VAMOS PRATICAR?
Usando a tabela a seguir, realize a localização das posições das chaves u
função hash. Em seguida, percorra a lista da maneira normal, retorn
posição em que o item foi encontrado. Em caso de colisão, adote o proc
hashing aberto para resolver o con�lito.
Linha 6: 9, , Adote: h(x) = mod 3 , 5,,,,, 
Linha 7: 37, , Adote: h(x) = mod 3 , 6,,,,, 
 
Assim, o hashing aberto é uma estratégia em que nenhum dos objetos é realmente armazenado na matriz da
tabela de hashing. Em vez disto, ele é armazenado em uma lista separada da matriz interna da tabela. 
4.3 Árvores de buscas balanceadas
Uma árvore de pesquisa binária balanceada mantém automaticamente sua altura pequena (garantida como
logarı́tmica) para uma sequência de inserções e exclusões. Conforme Viana, Cintra e Nobre (2015), essa
estrutura fornece implementações e�icientes para dados abstratos, como matrizes associativas.
Diferentemente das listas, em que as informações se encontram em uma sequência; nas árvores, esses dados
são representados de forma hierárquica, sendo que cada nó possui um conteúdo (VIANA; CINTRA; NOBRE,
2015).
Nas árvores de busca balanceada, as chaves alocadas são mantidas ordenadas, permitindo que a operação de
busca seja realizada, percorrendo-se um ramo da árvore, desde a base até chegar ao inı́cio (VIANA; CINTRA;
NOBRE, 2015).
As árvores de pesquisa são como um método para armazenar dados, de modo a oferecer suporte para as
operações de inserção rápida, pesquisa e exclusão. O principal problema das árvores de busca é o desejo que
elas sejam equilibradas para que as pesquisas possam ser executadas rapidamente. No entanto, não é
necessário que elas sejam perfeitas, visto que seria muito caro de manter para inserir ou excluir um novo
elemento.
Nesse contexto, vários algoritmos foram desenvolvidos para a construção de árvores de busca que
permanecem equilibradas.
Á
VOCÊ QUER VER?
Uma árvore binária é composta de nós, sendo que cada nó contém uma referência
"esquerda", uma referência "direita" e um elemento de dados. O nó superior da árvore
é chamado de “raiz”. Para compreender melhor o funcionamento de uma árvore
binária, sugerimos que você assistia ao vıd́eo disponıv́el no link:
https://youtu.be/PgZ�lufXGUU. Com ele, será mais fácil identi�icar os pontos
apresentados.
4.3.1 Árvore AVL
A árvore AVL é uma árvore binária que vai seguir as mesmas regras para inserção, busca e remoção de
elementos, bem como adicionar tais regras a métodos para se manter o equilı́brio da árvore. Ela é muito
balanceada: em suas inserções e exclusões, procura-se executar uma rotina de balanceamento em que as
alturas das sub-árvores sejam próximas.
Conforme nos explicam Viana, Cintra e Nobre (2015), as operações básicas, como busca, inserção, remoção e
outras, levam um tempo proporcionalao número de nı́veis da árvore binária de busca. Isto é, a quantidade de
operações para busca, inserção e remoção, no pior dos casos, depende de quantos nı́veis existem na árvore.
Dada esta observação, podemos concluir que é desejado manter a árvore sempre com a menor quantidade de
nı́veis possı́vel para que as operações básicas não custem tanto tempo. 
Vejamos um exemplo em que a inserção dos números se encontra em sequência (10, 11, 12, 13, 14, 15, 16, 17
e 18), ou seja, foi inserido número por número de forma sequencial na árvore. Observe a �igura a seguir.
VOCÊ O CONHECE?
Georgy Adelson era um matemático e cientista de computação. Nascido em Samara,
Adelson foi originalmente educado como um matemático puro. Seu primeiro trabalho,
com o colega e eventual colaborador de longa data, Alexander Kronrod, em 1945,
ganhou um prêmio da Sociedade Matemática de Moscou. Ele começou a trabalhar em
inteligência arti�icial e outros tópicos aplicados no �inal da década de 1950. Junto com
Evgenii Landis, inventou a árvore AVL em 1962. Esta foi a primeira estrutura de dados
da árvore de pesquisa binária balanceada já conhecida.
#PraCegoVer: A �igura mostra duas representações de árvores. Na primeira representação temos uma árvore
desequilibrada em que todos os nós estão conectados do seu lado direito. A sequências de nós é: 10, ao lado
direito deste tem o nó 11, ao lado direito deste tem o nó 12, ao lado direito deste tem o nó 13, ao lado direito
deste tem o nó 14 e ao lado direito deste tem o no 15. 
 
Figura 5 - Distribuição de árvore sequencial
Em seguida, mostra-se o desenho de uma árvore ideal em que cada nó possui dois �ilhos, um �ilho ou nenhum
�ilho. 
 
Neste caso, para elementos, a árvore teria nı́veis, resultando em uma péssima distribuição. O ideal seria que
os nós, conforme sejam inseridos, também sejam rearranjados para manter um equilı́brio. Assim, o ideal seria
manter a mesma quantidade de nı́veis na subárvore da direita e na subárvore da esquerda.
A questão é: como fazer para garantir esse equilı́brio? A resposta vai estar nas chamadas rotações. Podemos,
inclusive, dividir o problema em duas partes: como detectar o desequilı́brio e como corrigir o desequilı́brio.
Vamos começar entendendo como detectar o desequilı́brio.
O equilı́brio de uma árvore de busca é medido subtraindo o número de nı́veis na subárvore da esquerda do
número de nı́veis na subárvore da direita.
Vejamos um exemplo a seguir, em que temos uma árvore qualquer e podemos observar cada um dos nós, bem
como contar quantos nı́veis existe à esquerda e à direta, subtraindo esse número.
#PraCegoVer: A �igura destaca o desequilı́brio de uma árvore binária é uma propriedade do nó. Para
demonstrar esse fato está sendo mostrado uma árvore em que um nó possui altura esquerda com valor 2 e
altura direita com valor 2. Sendo assim causando o desequilı́brio da subárvore. 
 
Pode-se dizer que a árvore está desequilibrada apenas quando o número for maior que 1 ou menor que -1.
Assim, iremos tolerar números de equilı́brio de 0, 1 e de -1, pois podemos ter um número ı́mpar de nós, ou
seja, em alguns casos, não conseguiremos fazer a árvore ter um equilı́brio completamente nulo.
Uma vez detectado o desequilı́brio na árvore, o próximo passo é entender como corrigi-lo, sendo este feito por
meio das rotações.
Figura 6 - Desequilı́brio de uma árvore binária
Existem quatro tipos de rotações, sendo dois tipos primitivos e dois compostos de rotações: rotação à
esquerda, rotação à direita, rotação dupla à esquerda e rotação dupla à direita. Clique no recurso a seguir para
conhecer a rotação à esquerda e rotação à direita.
Veja a �igura a seguir para entender melhor. 
VOCÊ QUER LER?
Um jogo educacional digital, denominado DEG4Trees (Digital	 Educational	 Game	 four
Trees), foi construıd́o para apoiar o ensino de estrutura de árvores binárias de buscas
e árvores AVL. No jogo, é preciso observar as propriedades das estruturas de dados e
interagir com elas para atingir os objetivos. Para saber mais, sugerimos a leitura do
artigo “DEG4Trees: um jogo educacional digital de apoio ao ensino de estruturas de
dados”, de Weider Alves Barbosa, Isabella de Freitas Nunes, Ana Carolina Gondim
Inocêncio, Thiago Borges de Oliveira e Paulo Afonso Parreira Júnior, disponıv́el em:
https://www.researchgate.net/pro�ile/Weider_Alves_Barbosa2/publication/2657866
05_DEG4Tree_Um_Jogo_Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dad
os/links/55fc6c1808ae07629e0d3628.pdf
A rotação à esquerda é como o próprio nome sugere. Os primeiros nós que estão na subárvore da
direita passam para a esquerda, fazendo com que o �ilho da direita se torne a nova raiz. Também
temos o caso particular em que o �ilho da direita já possui o �ilho da esquerda, com todos os
elementos da subárvore da direita maiores que a raiz (x > 1). 
Já a rotação à direita vai funcionar de forma análoga, seguindo a mesma lógica da rotação à
esquerda. Nela, temos uma diagonal para o outro lado, ou seja, o �ilho da esquerda vira a nova raiz
(2 = raiz) e o �ilho da direita de 2 será o �ilho da esquerda de 3. Depois, 3 se tornará o �ilho da
direita de 2. 
•
•
Rotação	à	esquerda
Rotação	à	direita
#PraCegoVer: A �igura mostra alguns exemplos de rotação em uma árvore AVL. 
 
No primeiro exemplo, temos uma árvore com três nós, cada um deles conectado ao lado direito do outro. Os
valores dos nós são: 1, 2 e 3, respectivamente. Logo em seguida, é mostrado uma rotação a esquerda em que o
nó 2 passou a ser o nó raiz e o nó 1 �icou conectado a sua esquerda e nó 3 continuou conectado a sua direita. 
 
No segundo exemplo, mostra-se uma árvore com três nós em que cada nó está conectado ao lado direito do
outro nó. Os valores do nós são 1, 2 e 3 respectivamente. Depois disso, mostra-se o valor x sendo adicionado
no nó 2, o que vai obrigar a execução de uma rotação da árvore. Sendo assim, após a rotação, o nó 2 passou a
ser o nó raiz e do seu lado esquerdo �icou o nó 1. Do lado direito do nó 1 foi encaixado o novo nó com o valor
Figura 7 - Tipos de rotação para árvore AVL
x. O nó 3 continuou ao lado direito do nó 2. 
 
O terceiro e último exemplo mostra uma árvore com 3 nós em que cada nó está conectado ao lado esquerdo
do outro nó. Os valores dos nós são 3, 2 e 1 respectivamente. Depois disso, mostra-se o valor x sendo
adicionado no nó 2 o que vai obrigar que aconteça uma rotação. Após a rotação, o nó 2 passou a ser o nó raiz,
o nó 1 �icou do seu lado esquerdo e o nó 3 continuou do seu lado direito. O novo nó com o valor x �icou
conectado ao lado esquerdo do nó 3. 
 
Vamos tentar compreender, agora, como funciona a rotação dupla à esquerda e a rotação dupla à direita, que
são rotações duplas compostas.
Considere a seguinte situação: a rotação simples à esquerda não resolve o desequilı́brio. Para detectar isto,
basta olharmos o desequilı́brio das subárvores de onde a nova raiz vai vir (3). Temos, assim, um
desequilı́brio positivo na raiz original (1), mas na subárvore da direita percebemos um desequilı́brio negativo
(3). Para corrigir o problema, podemos adotar como solução uma rotação à direita na subárvore da direita e,
em seguida, uma rotação à esquerda na árvore original.
A rotação	dupla	à	direita vai ser bem similar à rotação	dupla	à	esquerda, conforme vemos na �igura na
sequência.
#PraCegoVer: A �igura mostra três exemplos de rotação. 
 
No primeiro exemplo temos uma árvore com um nó raiz com valor 1 e ao seu lado direito tem um nó com o
valor 3. Do lado esquerdo do nó 3 tem um nó com o valor 2. Ao lado do nó 1 tem o número 2 indicando o
valor balanceamento do nó e a o nó 3 possui o valor –1 indicando seu balanceamento. Ao lado direito desta
Figura 8 - Processo da rotação dupla à direita e à esquerda, respectivamente
árvore tem uma seta apontando para outra arvore quepossui o nó 3 como nó raiz, o nó 1 conectado ao seu
lado direito e por �im o nó 2 conectado ao lado direito do nó 1. 
 
No segundo exemplo temos uma árvore com um nó raiz com valor 1 e ao seu lado direito tem um nó com o
valor 3. Do lado esquerdo do nó 3 tem um nó com o valor 2. Ao lado direito desta árvore tem uma seta
apontando para uma outra árvore que possui o nó 1 como nó raiz. Ao lado direito do nó 1 tem um nó com o
valor 2 e ao lado direito do nó 2 tem um nó com o valor 3. Embaixo desta árvore tem um texto escrito:
"Rotação à direita na subárvore da direita". Ao lado desta segunda árvore tem uma seta apontando para uma
terceira árvore a qual contém o nó 2 como nó raiz. Do lado esquerdo do no 2 tem um nó com o valor 1 e do
lado direito tem um nó com o valor 3. Embaixo desta árvore tem um texto com a frase: "Rotação à esquerda na
árvore original". 
 
No terceiro exemplo temos uma árvore com um nó raiz com valor 1 e ao seu lado direito tem um nó com o
valor 3. Do lado esquerdo do nó 3 tem um nó com o valor 2. Ao lado direito desta árvore tem uma seta
apontando para uma outra árvore que possui o nó 1 como nó raiz. Ao lado direito deste nó tem um nó com o
valor 2 e ao lado esquerdo desse nó tem um nó com o valor 3. Embaixo desta árvore tem um texto escrito:
"Rotação à direita da subárvore da direita". Ao lado direito dessa árvore tem uma seta apontando para uma
outra árvore com 3 nós. O nó raiz tem o valor 3, ao lado esquerdo tem um nó com valor 1 e ao lado direito tem
um nó com valor 2. 
 
Agora que já conhecemos a rotação dupla à esquerda e a rotação dupla à direita, como decidir qual delas
devemos usar? Para tanto, precisamos seguir um passo a passo. Clique nos ı́cones a seguir.
Calcular o fator de equilıb́rio (Q = R - L), em que
“R” é o número de nıv́eis à direita e “L” é o
número de nıv́eis à esquerda.
Se -1 ≤ Q ≤ 1, a árvore é equilibrada.
Se Q > 1, temos duas opções: se a subárvore da
direita tem Q < 0, então a rotação seria dupla à
esquerda, mas, do contrário, seria rotação à
esquerda; se a subárvore da direita tem Q > 0,
então a rotação seria dupla à direita, mas, do
contrário, seria rotação à direita.
•
•
•
#PraCegoVer: A �igura mostra a representação de uma árvore com 3 nós. O nó raiz possui o valor 2. Ao lado
direito do nó 2 está conectado o nó com o valor 4. Ao lado esquerdo do nó 4 está conectado o nó com o valor
3. 
 
Como já conhecemos a respeito da árvore AVL, vamos, no próximo item, estudar a respeito das árvores B e B+.
Vejamos!
4.3.2 Árvores B e B+
As árvores	B são uma forma de árvore de pesquisa equilibrada, baseada em árvores gerais. Um nó da árvore B
pode conter vários elementos, em vez de apenas um, como nas árvores de pesquisa binária. Isto é, em vez de
ter apenas dois �ilhos, ela pode ter vários.
VAMOS PRATICAR?
Uma vez detectado o desequilıb́rio na árvore, o próximo passo é entend
corrigi-lo. Use o processo da rotação dupla para corrigir o desequilıb́rio da
a seguir.
De acordo com Viana, Cintra e Nobre (2015), as árvores	B são especialmente úteis para estruturas de pesquisa
armazenadas em discos. Estes têm caracterı́sticas de recuperação diferentes da memória interna (RAM) e,
obviamente, seu acesso é muito mais lento.
Na maioria das árvores de pesquisas, como a AVL, supõe-se que tudo esteja na memória principal. Contudo,
para entender o uso das árvores B, devemos pensar na quantidade de dados que não cabe na memória
principal. Quando o número de chaves é alto, os dados são lidos do disco na forma de blocos. A ideia
principal do uso de árvores B é reduzir o número de acessos ao disco.
Temos, assim, que as árvores B são uma boa combinação para armazenamento e pesquisa em disco, pois é
possı́vel escolher o tamanho do nó para corresponder ao tamanho do cilindro. Ao fazer isto, armazenaremos
muitos membros de dados em cada nó, tornando a árvore mais plana, para que sejam necessárias menos
transições (VIANA; CINTRA; NOBRE, 2015).
Uma estrutura de árvore B é balanceada automaticamente e, geralmente, permite que um nó tenha mais de
dois �ilhos — para manter a árvore larga e, portanto, crescer em altura —, com várias chaves inseridas em um
nó.
Normalmente, de�inimos uma árvore B	com “ordem	b”, em que “b” é o número mı́nimo de �ilhos e “2b” é o
número máximo de �ilhos que qualquer nó	pode ter.
A seguir, temos um exemplo de uma árvore B com b = 2.
#PraCegoVer: A �igura mostra uma representação de uma árvore B. No topo da imagem temos um vetor de 3
posições com os seguintes valores: 8, 21 e 34. Tem 4 setas saindo deste vetor. Cada seta aponta para um vetor
diferente. A primeira seta aponta para um vetor com os valores; 8, 21, 34. A segunda seta aponta para um vetor
com os valores: 14. A terceira seta aponta para um vetor com o valor 23, 31. Por �im, a última seta aponta para
um vetor com o valor 45. 
 
 
Na árvore da �igura anterior, podemos perceber que cada número inteiro é considerado uma chave separada,
ou seja, cada um teria seu próprio nó. Assim como em outras árvores, todas as chaves na subárvore à
esquerda são menores que a chave atual, bem como todas as chaves na subárvore à direita são maiores. Por
exemplo, começando na chave 8, as chaves 3, 4 e 7 são menores, enquanto a chave 14 é maior. 
Observe, também, que, como o número máximo de �ilhos é 2 * 2 = 4, um nó pode armazenar apenas três
chaves, pois os indicadores para �ilhos são armazenados entre as chaves e nas bordas. 
Para implementar a indexação dinâmica em vários nı́veis, geralmente são utilizadas as árvores B e B+. A
desvantagem da árvore B usada para indexação é que ela armazena o ponteiro de dados (ponteiro para o bloco
de arquivos do disco que contém o valor da chave), correspondente a um valor de chave especı́�ico,
juntamente com o valor de chave no nó de um B. Esta técnica reduz bastante o número de entradas que podem
ser empacotadas em um nó de uma árvore B, contribuindo para o aumento do número de nı́veis e do tempo de
pesquisa de um registro.
Figura 9 - Exemplo de árvore B
A árvore B+ elimina essa desvantagem, armazenando ponteiros de dados apenas nos nós das folhas da árvore.
Assim, a estrutura é bem diferente da dos nós internos da árvore B+.
Vejamos algumas propriedades das árvores B e B+. Clique nos ı́cones a seguir.
Todas as folhas estão no mesmo nıv́el.
Uma árvore B é de�inida pelo termo grau mıńimo
“t”, sendo que seu valor depende do tamanho do
bloco de disco.
Todo nó, exceto a raiz, deve conter pelo menos
chaves “t - 1”.
A raiz pode conter, no mıńimo, uma chave.
Todos os nós, incluindo raiz, podem conter, no
máximo, “2t - 1” chaves.
O número de �ilhos de um nó é igual ao número
de chaves, mais 1.
Todas as chaves de um nó são classi�icadas em
ordem crescente.
O �ilho entre duas chaves k1 e k2 contêm todas as
chaves no intervalo de k1 e k2.
•
•
•
•
•
•
•
•
•
A árvore B cresce e diminui a partir da raiz,
diferente da árvore de pesquisa binária.
Todo nó do tipo folha possui a mesma
profundidade entre eles e o nó da raiz.
Como outras árvores de pesquisa binária
equilibradas, a complexidade do tempo para
pesquisar, inserir e excluir é O(Log n).
Cada nó está 50% cheio, com exceção o nó da
raiz.
Na �igura a seguir, podemos observar um exemplo de árvore B+. 
#PraCegoVer: A �igura mostra uma representação de uma árvore B+. Primeiramente é mostrado um vetor
com os valores 23,31. Existem três seta saindo desse vetor. Uma das setas aponta para um vetor com os
valores 8, 21. A segunda seta aponta para um vetor com o valor 23 e a terceira seta aponta para um vetor com
o valor 34. 
 
O vetor com os valores 8, 21 também possui 3 setas apontando para outros 3 vetores. A primeira seta aponta
para um vetor com o valor 2, 4. A segunda seta aponta para um vetor com os valores 8,11 e a terceira seta
aponta para um vetor com o valor 21. 
 
••
•
Figura 10 - A� rvore B+
O vetor com o valor 26 possui duas setas aponta para outros dois vetores. A primeira será aponta para um
vetor com valor 23 e a segunda seta aponta para um vetor com o valor 26, 28. 
 
O vetor com valor 34 possui 2 apontando para outros dois vetores. A primeira seta está apontando para um
vetor com o valo 31 e a segunda seta está apontando para um vetor com os valores 34 e 37. 
 
Dessa forma, a árvore B+ é muito semelhante a árvore B. As duas se equilibram automaticamente e possuem
operações logarı́tmicas de inserção, localização e exclusão.
Uma árvore B+ pode ser vista como uma árvore B em que cada nó contém apenas chaves (não pares de chave-
valor) e um nı́vel adicional é inserido na parte inferior, com folhas vinculadas.
Síntese
Chegamos ao �im de mais uma unidade de estudos! Aqui, pudemos compreender as técnicas de pesquisa
sequencial e binária, em que foi possı́vel aprender os conceitos e a aplicabilidade de tabelas de dispersão.
Também pudemos conhecer as principais árvores de buscas e suas complexidades.
Nesta unidade, você teve a oportunidade de:
conhecer as técnicas de pesquisas sequencial e binária;
entender sobre as tabelas de dispersão;
compreender a respeito das árvores de buscas balanceadas;
identificar as técnicas de manutenção das árvores de pesquisas;
verificar a complexidade dos algoritmos de pesquisa.
•
•
•
•
•
Bibliografia
BARBOSA, W. A. et	al. DEG4Trees: um jogo educacional digital de apoio ao ensino de estruturas de dados.
Goiás: Universidade Federal de Goiás, 2015. Disponı́vel em:
https://www.researchgate.net/pro�ile/Weider_Alves_Barbosa2/publication/265786605_DEG4Tree_Um_Jogo_
Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dados 
/links/
(https://www.researchgate.net/pro�ile/Weider_Alves_Barbosa2/publication/265786605_DEG4Tree_Um_Jogo_
Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dados/links/)55fc6c1808ae07629e0d3628.pdf
(https://www.researchgate.net/pro�ile/Weider_Alves_Barbosa2/publication/265786605_DEG4Tree_Um_Jogo_
Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dados/links/55fc6c1808ae07629e0d3628.pdf).
Acesso em: 11 out. 2019.
VIANA, G. V. R.; CINTRA, G. F.; NOBRE; R. H. Pesquisa	e	ordenação	de	dados. 2. ed. Ceará: EdeuECE, 2015.
https://www.researchgate.net/profile/Weider_Alves_Barbosa2/publication/265786605_DEG4Tree_Um_Jogo_Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dados/links/
https://www.researchgate.net/profile/Weider_Alves_Barbosa2/publication/265786605_DEG4Tree_Um_Jogo_Educacional_Digital_de_Apoio_ao_Ensino_de_Estruturas_de_Dados/links/55fc6c1808ae07629e0d3628.pdf