Apresentação • Introdução • Estruturas e suas implementações • Resultados e Análises • Conclusão • Bibliotecas • Compilação e Execução • Referências • Autor
Foi proposto pelo professor Michel Pires da Silva da matéria de Arquitetura e Estruturas de Dados 2 do 4º Período do curso de Engenharia de Computação um trabalho relacionado ao conteúdo passado em suas aulas teóricas que são Estrutura de Dados Árvore, onde foi introduzido uma comparação de tempo entre diversas implementações sob diferentes volumes de dados em três tipos de árvores sendo elas, Árvore Binária de Pesquisa, Árvore AVL e Árvore RedBlack e outras diferentes estruturas sendo vectors e MAPs. Portanto foi proposto o seguinte desafio:
Chegou o momento de compararmos tais estruturas, observando seu comportamento sob diferentes volumes de dados. Para tanto, elabore arquivos que contenham 500 , 5000 , 50.000 , 500.000 entradas numéricas do tipo ponto flutuante. Para tanto, tente evitar repetições de valores em grande escala para que possamos ter uma estrutura profunda. Considere produzir os menores a partir dos maiores volumes de forma randômica. Feito a isso, vamos testar os seguintes processos:
1) - Qual o tempo gasto com pesquisa para um arquivo de entrada com 10.000 consultas. Considere como consulta a busca de um determinado número na estrutura escolhida. Para cada pesquisa, é preciso remover o elemento da árvore, retornando esse número para o usuário. Então, considere o processo de remoção como parte final do processo.
2) - Qual o tempo necessário para montar a estrutura em memória.
3) - Qual o ganho dessas estruturas ao compará-las a vetores ordenados e aplicados à pesquisa binária. Qual o tempo gasto com a ordenação do vetor? Foi possível produzi-lo em memória?
4) - Adotando como estrutura o map e unorder_map do C++, há ganhos maiores nesse processo de pesquisa?
Elabore um relatório detalhando a implementação dessas estruturas, funcionamento da aplicação, exemplo de resultado, modo de compilação e conclusões. Considere essa última seção como uma discussão de quando adotar cada estrutura acima citada e o por quê de tal escolha. Para toda essa discussão, apresentar gráficos que demonstrem os resultados obtidos durante o processo de análise.
Com isso, foi desenvolvido um algoritmo baseado na proposta, onde foi possível obter as seguintes conclusões presentes em Conclusão!
Para introduzir o problema proposto primeiramente foi necessário a criação dos cinco diferentes arquivos sendo quatro deles contendo os diferentes tamanhos de entrada do tipo float e um contendo 10.000 entradas do tipo float utilizado para consultas, sendo possível encontra-los na pasta src/files para verificação. A criação dos arquivos foi necessária apenas uma vez para manter o padrão de testes, após isso foi removido as funções de criações.
Após a criação dos arquivos foi necessário a implementação dos diferentes tipos de Estrutura de Dados Árvore onde foram utilizadas através de repositórios feitos pelo professor Michel Pires da Silva, sendo eles, Árvore Binária de Pesquisa, Árvore AVL e Árvore RedBlack onde na última estrutura foi necessária a implementação do método de remoção onde foi encontrado o mesmo no livro do [1]Cormem em forma de pseudocódigo, sendo feita apenas algumas alterações no código principal para que fosse possível ser feita a implementação da remoção sem nenhum problema. Sendo feita essas implementações foi necessário implementar a utilização de vectors e estruturas do tipo MAPs encontrando informações em [2] para uma implementação sem erros;
O que é uma Árvore Binária de Pesquisa?
Uma Árvore Binária de Pesquisa é organizada, como o nome sugere, em uma árvore binária como mostra a Figura 1. Sendo uma estrutura baseada em nós, onde todos os nós da subárvore esquerda possuem um valor númerico interior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz, sendo essa a forma padrão. Essa estrutura possue o objetivo de estruturar os dados de forma a permitir Busca Binária. Esse tipo de estrutura suporta muitas operações de conjuntos dinâmicos, incluindo busca, mínimo, máximo, antecessor, sucessor, inserção e remoção, possibilitando seu uso como um dicionário e também como uma fila de prioridades.
Figura 1: Árvores Binárias de Pesquisa. (a)Uma árvore binária de pesquisa com seis nós e altura 2. (b)Uma árvore de busca binária menos eficiente, com altura 4, contendo as mesmas chaves de (a).
Custos de uma Árvore Binária de Pesquisa?
As operações básicas em um árvore binária de pesquisa demoram um tempo proporcional á altura da árvore. No caso de uma árvore binária completa com n nós, tais operações são executados no tempo Árvore Binária de Pesquisa:
| Algoritmo | Caso Médio | Pior Caso |
|---|---|---|
Espaço |
||
Busca |
||
Inserção |
||
Remoção |
Tabela 1: Complexidade de uma Árvore Binária de Pesquisa em notação big O.
- Logo a árvore binária de busca é de pouca utilidade para ser aplicada em problemas de busca em geral, surgindo então o interesse em árvores balanceadas, cuja altura seja
$O(log{}{n})$ no pior caso.
Operação de Busca
A operação de busca por um valor específico implementada no algoritmo através de uma função recursiva como é possível visualizar no pseudocódigo abaixo que foi usado como base para implementação:
TreeSearch(x,k)
1 if x == NULL ou k == x.chave
2 return x
3 if k < x.chave
4 return TreeSearch(x.esquerda, k)
5 else return TreeSearch(x.direita, k)Explicação: A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Igualmente caso o valor é maior do que a raiz, a busca segue pela subárvore direita. Se tornando um processo recursivo até encontrar o valor requerido. Se o valor na for encontrado até a busca chegar na subárvore nula é concluido que o valor não está presente na árvore
Operação de Inserção
A operação de inserção é utilizado o procedimento presente na função _insertTree() onde o mesmo toma um nó z para o qual z.chave = v, z.esquerda=NULL e z.direita=NULL, e modifica T e alguns dos atributos de z de modo tal que insere z em uma posição adequada na árvore, sendo possível visualizar no pseudocódigo abaixo:
insertTree(T,z)
1 y = NULL
2 x = T.raiz
3 while x != NULL
4 y = x
5 if z.chave < x.chave
6 x = x.esquerda
7 else x = x.direita
8 z.p = y
9 if y = NULL
10 T.raiz = z //a árvore T era vazia
11 else if z.chave < y.chave
12 y.esquerda = z
13 else y.direita = zExplicação: A fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menor que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor. Segue abaixo na Figura 2 um exemplo de inserção na Árvore Binária de Pesquisa:
Figura 2: Exemplo de uma inserção do valor 13 em uma árvore binária de pesquisa. Os nós sombreados emtommais claro indicamo caminho simples da raiz até a posição emque o item é inserido. A linha tracejada indica a ligação que é acrescentada à árvore para inserir o item.
Operação de Remoção
A exclusão de um nó na árvore binária de pesquisa é um processo mais complexo. Para excluir um nó de uma árvore binária de pesquisa, levando em consideração três casos distintos para a exclusão, sendo eles:
Caso 1 - Remoção na folha: A exclusão na folha é a mais simples, batando apenas removê-lo da árvore como no exemplo da figura abaixo:
Caso 2 - Remoção de nó com um filho: Ao excluir um nó que possui um filho, o filho vai subir para a posição do pai.
Caso 3 - Remoção de nó com dois filhos: Neste caso, há duas opções para ser operado. A primeira é a possibilidade de substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais á esquerda da subárvore direita) ou pelo valor antecessor (o nó mais á direita da subárvore esquerda), sendo feita então a remoção do nó sucessor ou antecessor.
A função antecessor foi utilizada para que houvesse uma implementação sem erros onde a mesma é composta por:
antecessor(T,x)
1 if x.direita != NULL
2 return antecessor(x.direita)
3 x = T
4 T = T.esquerda
5 free xRemoveTree(T,x)
1 y = T.raiz
2 if y == NULL
3 return
4 if x.chave < y.chave
5 RemoveTree(y.esquerda, x)
6 if x.chave > y.chave
7 RemoveTree(y.direita, x)
8 if y.direita == NULL{
9 aux = y
10 y = y.esquerda
11 free aux
12 }
13 if y.esquerda == NULL
14 antecessor(y.esquerda, y)
15 aux = y
16 y = y.direita
17 free aux- T representa uma estrutura de árvore e x um nó
Testes utilizando Árvore Binária de Pesquisa
Após ser feita a implementação de todos os algoritmos básicos presentes em uma Árvore Binária de Pesquisa foi possível realizar os testes propostos em Apresentação obtendo então os seguintes resultados informados na tabela a seguir:
Onde os mesmos são fornecidos pelo programa desenvolvido da seguinte forma após a sua compilação:
O que é uma Árvore AVL?
Uma árvore AVL é uma árvore de busca binária de altura balanceada, ou seja, uma árvore balanceada são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências identidas, Sendo necessária a reconstrução da árvore para seu estado ideal a cada operação sobre seus nós (inserção ou remoção). A sua diferença de alturas das subárvores á esquerda e á direita de x é no máximo de uma unidade.
Figura 7: Demonstração de uma Árvore AVL aproximadamente balanceada, uma árvore desbalanceada após remoções e a sua correção resultando em uma Árvore AVL completamente balanceada.
Complexidade de uma Árvore AVL
Todas as operações básicas em uma Árvore AVL possuem complexidade
| Algoritmo | Caso Médio | Pior Caso |
|---|---|---|
Espaço |
||
Busca |
||
Inserção |
||
Remoção |
Tabela 3: Complexidade de uma Árvore AVL em notação big O.
- Logo a árvore AVL é caracterizada por sua eficiência em buscas com chaves de probabilidades de ocorrências idênticas, reduzindo o número médio de comparações necessária para localizar qualquer elemento da árvore em 39 vezes menos.
Operação de Busca
A operação de busca por um valor específico implementada no algoritmo através de uma função recursiva como é possível visualizar no pseudocódigo abaixo que foi usado como base para implementação, sendo a mesma utilizada em Árvore Binária de Pesquisa:
TreeSearch(x,k)
1 if x == NULL ou k == x.chave
2 return x
3 if k < x.chave
4 return TreeSearch(x.esquerda, k)
5 else return TreeSearch(x.direita, k)Explicação: A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Igualmente caso o valor é maior do que a raiz, a busca segue pela subárvore direita. Se tornando um processo recursivo até encontrar o valor requerido. Se o valor na for encontrado até a busca chegar na subárvore nula é concluido que o valor não está presente na árvore
Operação de Inserção
A operação de inserção é utilizado o procedimento presente na função _insertTreeAVL() onde é necessário uma busca pelo elemento inserido nesta mesma árvore. Após a busca o local correto para a inserção do nó será em uma subárvore vazia de uma folha da árvore. Depois de inserido o nó, a altura do nó pai e de todos os nós acima deve ser atualizada. Em seguida o algoritmo de rotação simples ou dupla deve ser acionado para o primeiro nó pai desregulado
insertTreeAVL(T,z)
1 if T == NULL
2 new(T)
3 T.item = z
4 T.peso = 0
5 T.esquerda = NULL
6 T.direita = NULL
7 else if z.chave = T.item.chave
8 insertTreeAVL(T.esquerda, z)
9 if (getPeso(T.esquerda) - getPeso(T.direita) = 2)
10 if z.chave < T.esquerda.item.chave
11 rotacaoSimplesDireita(T)
12 else
13 rotacaoDuplaEsquerdaDireita(T)
14 else if z.chave > T.item.chave
15 insertTreeAVL(T.direita, z)
16 if (getPeso(T.direita) - getPeso(T.esquerda) = 2)
17 if z.chave > T.direita.item.chave
18 rotacaoSimplesEsquerda(T)
19 else
20 rotacaoDuplaDireitaEsquerda(T)
21 T.peso = PesoMax(getPeso(T.esquerda),getPeso(T.direita))+1A inserção demonstrada utilizou de quatro diferentes funções que foram criadas para auxiliar o balanceamento na inserção, sendo essas as 4 diferentes rotações possíveis de visualizar nos exemplos gráficos e respectivos pseudocódigos abaixo:
Figura 8: Exemplo de uma rotação simples à direita.
rotacaoSimplesDireita(t)
1 aux = t.left;
2 t.left = aux.right;
3 aux.right = t;
4 t.peso = PesoMax(getPeso(t.left), getPeso(t.right)) + 1;
5 aux.peso = PesoMax(getPeso(aux.left), t.peso) + 1;
6 t = aux;rotacaoSimplesEsquerda(t)
1 aux = t.right;
2 t.right = aux.left;
3 aux.left = t;
4 t.peso = PesoMax(getPeso(t.esquerdo), getPeso(t.direito)) + 1;
5 aux.peso = PesoMax(getPeso(auxˆ .direito), t.peso) + 1;
6 raiz = aux;
Figura 9: Exemplo de uma rotação dupla a esquerda/direita.
rotacaoDuplaEsquerdaDireita(t)
1 rotacaoSimplesEsquerda(t.left);
2 rotacaoSimplesDireita(t);rotacaoDuplaDireitaEsquerda(t)
1 rotacaoSimplesDireita(t.right);
2 rotacaoSimplesEsquerda(t);- t representa uma estrutura de árvore e z um nó.
Operação de Remoção
O primeiro passo para remover uma chave na árvore AVL consiste em realizar uma busca binária a partir do nó raiz. Caso a busca encerre em uma subárvore vaiza, então a chave não está na árvore e a remoção não pode ser realizado. Caso a busca encerre em um nó a remoção poderá ser realizada obedecendo os seguintes casos
Caso 1 - Remoção na folha: A exclusão na folha é a mais simples, batando apenas removê-lo da árvore como no exemplo da figura abaixo:
Caso 2 - Remoção de nó com um filho: Ao excluir um nó que possui um filho, o filho vai subir para a posição do pai, bastando apontar o nó pai para a única subárvore e excluir o nó.
Caso 3 - Remoção de nó com dois filhos: Neste caso é necessário localizar o nó antecessor ou sucessor, que sempre será um nó folha ou possuirá apenas uma subárvore, copiar a chave do nó antecessor ou sucessor para o nó que deseja excluir e excluir o nó antecessor ou sucessor a partir da respectiva subárvore do nó que deseja excluir.
RemoveTree(T,F,x)
1 y = T.raiz
2 if y == NULL
3 return
4 if x.chave < y.chave
5 RemoveTree(y.esquerda,T,x)
6 if x.chave > y.chave
7 RemoveTree(y.direita,T,x)
8 if y.direita == NULL{
9 aux = y
10 y = y.esquerda
11 free aux
12 rebalenceTree(f) //Função que verifica os pesos da árvore e balanceia novamente se necessário
13 }
14 if y.esquerda != NULL{
15 antecessor(y.esquerda, y)
16 rebalenceTree(T)
17 rebalenceTree(F)
18 }
19 aux = y
20 y = y.direita
21 free aux
22 rebalenceTree(T)
23 rebalenceTree(F)- T e F representam uma estrutura de árvore e x um nó.
Figura 10: Exemplo de uma remoção balanceada na Árvore AVL.
Testes utilizando Árvore AVL
Após ser feita a implementação de todos os algoritmos básicos presentes em uma Árvore AVL foi possível realizar os testes propostos em Apresentação obtendo então os seguintes resultados informados na tabela a seguir:
Onde os mesmos são fornecidos pelo programa desenvolvido da seguinte forma após a sua compilação:
O que é uma Árvore RedBlack?
As Árvores RedBlack são um dos muitos esquemas de árvores de busca que são "balanceadas" de modo a garantir que operações básicas de conjuntos dinâmicos demorem o tempo
Figura 12: Exemplo de uma árvore RedBlack.
Complexidade de uma Árvore RedBlack
Todas as operações básicas em uma Árvore RB possuem complexidade
| Algoritmo | Caso Médio | Pior Caso |
|---|---|---|
Espaço |
||
Busca |
||
Inserção |
||
Remoção |
Tabela 5: Complexidade de uma Árvore RedBlack em notação big O.
- Árvores Red Black são usadas na maioria das bibliotecas de linguagens como map, multimap, multset em C++ e é caracterizada por ser utilizada em aplicações de tempo real (críticas)
Operação de Busca
A operação de busca por um valor específico implementada no algoritmo através de uma função iterativa como é possível visualizar no pseudocódigo abaixo que foi usado como base para implementação:
RBTreeSearch(T,x)
1 if T == NULL
2 return
3 atual = T
4 while atual != NULL
5 if x == atual.valor
6 return
7 if x > atua.valor
8 atual = atual.direita
9 else
10 atual = atual.esquerda- T representa uma estrutura de árvore e x um valor do tipo flutuante.
Operação de Inserção
A operação de inserção é utilizado o procedimento presente na função _insertTreeRB(), sendo considerado uma operação complicada porque pode ferir alguma propriedade deste tipo de árvore, podendo ser implementadas de forma bastante parecida com as respectivas operações nas Árvores Binárias de Pesquisa, bastanto apenas modificar as cores dos nós para que as propriedades de Árvores RedBlack sejam satisfeitas, utilizando uma função secundária RBInsertFixUp() para restauras essas propriedades na inserção.
insertTreeRB(T,z)
1 y = T.nil
2 x = T.raiz
3 while x != T.nil
4 y = x
5 if z.chave < x.chave
6 x = x.esquerda
7 else x = x.diretia
8 z.p = y
9 if y == T.nil
10 T.raiz = z
11 else if z.chave < x.chave
12 y.esquerda = z
13 else y.direita = z
14 z.esquerda = T.nil
15 z.direita = T.nil
16 z.cor = VERMELHO
17 RBInsertFixUp(T,z)RBInsertFixUp(T,z)
1 while z.p.cor == VERMELHO
2 if z.p == z.p.p.esquerda
3 y = z.p.p.direita
4 if y.cor == VERMELHO
5 z.p.cor = PRETO //caso 1
6 y.cor = PRETO //caso 1
7 z.p.p.cor = VERMELHO //caso 1
8 z = z.p.p //caso 1
9 else if z = z.p.direita
10 z = z.p //caso 2
11 rotacaoSimplesEsquerda(T, z) //caso 2
12 z.p.cor = PRETO //caso 3
13 z.p.p = VERMELHO //caso 3
14 rotacaoSimplesDireita(T, z.p.p) //caso 3
15 else (igual à cláusala then com "direita" e "esquerda" trocadas)
16 T.raiz.cor = PRETO- T representa uma estrutura de árvore e z um nó.
Explicação: A operação de inserção em uma Árvore RedBlack começa por uma busca da posição onde o novo nó deve ser inserido, partindo-se da raiz em direção aos nós que possuam o valor mais próximo do qual vai ser inserido, onde é feita a verificação de acordo com seus respectivos casos:
Caso 1: Caso esta inserção seja feita em uma árvore vazia, basta alterar a cor do nó para preto, satisfazendo assim a propriedade 2;
Caso 2: Ao inserir x, se o tio de x é vermelho, é necessário fazer a recoloração de seu a, t e p;
Obs1: Se o pai de a é vermelho, o rebalanceamento tem que ser feito novamente.
Obs2: Se a é raiz, então ele deve ser preto!
Caso 3: Suponha que o tio do elemento inserido é preto. Neste caso, para manter o critério 4 é preciso fazer rotações envolvendo a, t, p e x.
– Há 4 subcasos que correspondem às 4 rotações possíveis:
Caso 3a: Rotação à direita;
Caso 3b: Rotação à esquerda;
Caso 3c: Rotação dupla esquerda, podendo ser visto como um caso 3a seguido do caso 3b;
Caso 3d: Rotação dupla direita, podendo ser visto como um caso 3b seguido do caso 3a;
(OBS: Lembrando que a Árvore RedBlack não possui explicitamente rotações duplas, os exemplos acima de rotações duplas são constituidos de duas rotações simples onde resulta em uma rotação dupla implicitamente)
Operação de Remoção
A remoção nas árvores RedBlacks se inicia com uma etapa de busca e remoção como nas Árvores Binárias de Pesquisa convecionais. Então se alguma propriedade da árvore for violada, a árvore deve ser rebalanceada, sendo um procedimento um pouco mais complicado que inserir um nó.
O procedimento para eliminar um nó de uma árvore RedBlack é baseado no procedimento remove_RBTree(), onde primeiramente é necessário a utilização da sub-função RBTransplant() que é chamada na função de remoção como é possível visualizar nos respectivos pseudocódigos abaixo:
RBTransplant(T,u,v)
1 if u.p == T.nil
2 T.raiz = v
3 else if u == u.p.esquerda
4 u.p.esquerda = v
5 else u.p.direita = v
6 v.p = u.pExplicação: Essa sub-função faz com que seja substituido uma subárvore como um filho de seu pai por uma outra subárvore e quando é feita essa substituição, a subárvore enraizada no nó u pela subárvore enraizado no nó v, o pai do nó u tornase o pai do nó v, e o pai de u acaba ficando com v como seu filho adequado.
remove_RBTree(T,z)
1 y = z
2 y.cor.original = y.cor
3 if z.esquerda == T.nil
4 x = z.direita
5 RBTransplant(T,z,z.direita)
6 else if z.direita == T.nil
7 x = z.esquerda
8 RBTransplant(T,z,z.esquerda)
9 else y = Tree-Minimum(z.direita)
10 y.cor.original = y.cor
11 x = y.direita
12 if y.p == z
13 x.p = y
14 else RBTransplant(T,y,y.direita)
15 y.direita = z.direita
16 y.direita.p = y
17 RBTransplant(T,z,y)
18 y.esquerda = z.esquerda
19 y.esquerda.p = y
20 y.cor = z.cor
21 if y.cor.original == PRETO
22 RBDeleteFixUp(T,x)- T representa uma estrutura de árvore e u, v e z um nó.
Após ser feita a remoção do nó z, remove_RBTree() chama um procedimento auxiliar RBDeleteFixUp(), que muda as cores e executa rotações para restaurar as propriedades da árvore RedBlack, sendo necessário observar em uma remoção os seguintes casos para que se mantenha em conformidade com suas propriedades:
Caso 1: É feita a verificação se o pai do nó não é nulo, se for vai para o segundo caso
Caso 2: Se o nó e seu pai forem pretos e seu irmão for vermelho, o pai deve ser pintado de vermelho e o irmão de preto e então se o nó for filho esquerdo, faz a rotação à esquerda de seu pai e vai pro próximo caso, se for filho direito, rotaciona o pai à direita e vai pro próximo caso
Caso 3: Nesse caso, se o pai do nó, o irmão, o filho esquerdo e direito do irmão forem todos pretos, pinta o irmão de vermelho e volte para o primeiro caso com o pai do nó, se não forem vai pro próximo caso.
Caso 4: Se o irmão e o filho esquerdo e direito do irmão forem pretos e o pai do nó for vermelho, deve pintar o irmão de vermelho e o pai do nó de preto, se não deve prosseguir para o próximo caso.
Caso 5: Se o nó for filho esquerdo e o filho direito do irmão for preto deverá pintar o irmão de vermelho e o filho esquerdo do irmão de preto e aí sim rotacionar à direita o irmão, mas se o nó for filho direito deverá pintar o irmão de vermelho e o filho direito do irmão de preto e então rotacionar para esquerda o irmão, indo para o último caso
Caso 6: Ao chegar nesse último caso deverá pintar o pai do nó de preto, caso o nó seja filho esquerdo, pinta o filho direito do irmão do nó de preto e rotaciona o pai do nó para a esquerda, se o nó for filho direito, pinta o filho esquerdo do irmão de preto e rotaciona o pai para direita.
Ao sair do encadeamento de casos, poderá ser feita a remoção do nó naturalemnte
Testes utilizando Árvore RedBlack
Após ser feita a implementação de todos os algoritmos básicos presentes em uma Árvore RedBlack foi possível realizar os testes propostos em Apresentação obtendo então os seguintes resultados informados na tabela a seguir:
Onde os mesmos são fornecidos pelo programa desenvolvido da seguinte forma após a sua compilação:
O que é uma Pesquisa Binária?
A busca/pesquisa binária é um algoritmo que implementa o paradigma Divisão e Conquista para encontrar um elemento em um vetor ordenado. Uma analogia ao funcionamento desse algoritmo seria a busca de uma palavra em dicionário.
Divisão e Conquista: Consiste em uma técnica de dividr um problema maior recursivamente em problemas menores até que o problema possa ser resolvido diretamente
Ou seja, a busca binária funciona dividindo repetidamente pela metade a porção da lista que deve conter o item, até reduzir as localizações possíveis a apenas uma.
Figura 14: Exemplo de uma busca binária ao elemento 4 de um vetor ordenado.
Complexidade de uma Pesquisa Binária
Considerando um array com N elementos, o tempo de execução de uma Pesquisa Binária é:
| Complexidade | Caso | Situação |
|---|---|---|
| Melhor caso | O elemente procurado está no meio do array | |
| Pior caso | O elemento não existe | |
| Caso médio | O elemento está em uma posição aleatoria |
Tabela 7: Complexidade de uma Pesquisa Binária em notação big O.
- Para se ter uma ideia da sua vantagem, em um array contendo N = 1000 elementos, no pior caso a Busca Sequencial irá executar 1000 comparações, já a Busca Binária irá executar apenas 10 comparações
Sua implementação no algoritmo
Primeiramente para a pesquisa binária ser funcional foi necessário realizar a ordenação dos 4 vectors que continha os diferentes tamanhos de entradas, onde foi utilizado a função sort() se tratando de uma função em STL (Standard Template Library) incluida na biblioteca algorithm presente na linguagem C++ onde é necessário apenas passar o inicio (begin) e fim (end) da estrutura que é requerida a ordenação, sendo possível ver a sua implementação no código desenvolvido para os teste abaixo:
Internamente essa função utiliza IntroSort, que é uma combinação de QuickSort, HeapSort e InsertionSort.
Figura 15: Exemplo de implementação da função sort() no algoritmo desenvolvido onde **vector_500entries** se trata de um vector com 500 números flutuantes.
A utilização da Pesquisa Binária no algoritmo foi necessário após ser feita a proposta em Apresentação onde foi necessário realizar comparações de tempo com as estruturas mencionadas anteriormente e vetores ordenados aplicados à pesquisa binária, analisando o tempo de ordenação dos respectivos vetores com entradas de 500, 5.000, 50.000 e 500.000 números flutuantes e o tempo gasto utilizando a Pesquisa Binária nesses vetores
Sua implementação no algoritmo foi feita utilizando uma função presente dentro da biblioteca bits/stdc++.h que está presente no C++ onde é chamada a função binary_search(start_ptr, end_ptr, num) que retorna true se o elemento estiver presente na estrutura pesquisada, senão retorna false. A variável start_ptr contpem o ponto inicial da busca binária e end_ptr mantém a posição final do espaço de busac binária e num é o valor a ser encontrado, sendo possível de visualizar um exemplo gráfico abaixo da implementação da função no código que foi desenvolvido para testes:
Figura 16: Exemplo de implementação da pesquisa binária no algoritmo desenvolvido onde **vector_500entries** se trata de um vector com 500 números flutuantes e **query_numbers** um vector contendo 10.000 números flutuantes para a pesquisa.
Testes utilizando Pesquisa Binária com vetores ordenados
Após ser feita a implementação de todos os algoritmos básicos presentes em uma Árvore RedBlack foi possível realizar os testes propostos em Apresentação obtendo então os seguintes resultados informados na tabela a seguir:
Onde os mesmos são fornecidos pelo programa desenvolvido da seguinte forma após a sua compilação:
Função std::map
Inicialmente map é um contêiner que armazena elementos em pares chave-valor. Os valores de chave geralmente são usados para classificar e identificar exclusivamente os elementos, enquanto os valores mapeados armazenam o contéudo associado a essa chave, podendo diferir os tipos de chave e valor mapeados, sendo necessário incluir a biblioteca map para a sua utilização.
Os tipos de chave e valores usados para a implementação da função map() no algoritmo de testes foram do tipo int e float respectivamentes como é possível visualizar um exemplo de sua implementação abaixo:
map<int, float> map500entries;Foi necessária a sua utilização para ser obtido resultados de seu tempo de execução para ser feita a pesquisa utilizando os métodos internos da função, verificando se há ganho maiores no processo comparado à pesquisa binária.
Complexidade
Sua complexidade para pesquisa utilizando sua função inclusa find() (como feito no algoritmo) é Árvore Binária de Pesquisa balanceada, sendo n o número de elementos dentro da map().
Função std::unordered_map
Inicialmente map é um contêiner associativo que contém pares de valores-chave com chaves exclusivas, havendo similiaridade com a estrutura de dados Tabela Hash.
Internamente, os elementos não são classificados em nenhuma ordem específica, mas organizados em buckets. Em qual bucket um elemento é colocado depende inteiramente do hash de sua chave, permitindo o acesso rápido a elementos individuais, uma vez que o hash é calculado, se referindo ao bucket exato em que o elemento está localizado.
Os tipos de chave e valores usados para a implementação da função unordered_map() no algoritmo de testes foram do tipo int e float respectivamentes como é possível visualizar um exemplo de sua implementação abaixo:
unordered_map<int, float> unordered_map500entries;Foi necessária a sua utilização para ser obtido resultados de seu tempo de execução para ser feita a pesquisa utilizando os métodos internos da função, verificando se há ganho maiores no processo comparado à pesquisa binária.
Complexidade
Sua complexidade para pesquisa utilizando sua função inclusa find() (como feito no algoritmo) é Tabela Hash e, portanto, a chave atua como um índice durante a pesquisa em mapas não ordenados. Considerando n o número de elementos dentro da unordered_map()
Testes utilizando as estruturas MAPs
Após ser feita a implementação da função std::map e std::unordered_map e sua respectivas funções de pesquisa, foi possível realizar os testes propostos em Apresentação obtendo então os seguintes resultados informados nas tabelas a seguir:
Onde os mesmos são fornecidos pelo programa desenvolvido da seguinte forma após a sua compilação:
• Após todo o código ser implementado com suas respectivas estruturas funcionando, foi possível realizar testes para obtenção do resultados de tempo de cada tipo de estrutura mencionado na proposta, onde foi possível obter os valores que estão presentes na tabela 2, tabela 4, tabela 6, tabela 8, tabela 9 e tabela 10, mostrando seus tempos médios para os diferentes tamanhos de entradas e processos, possibilitando a criação dos seguintes gráficos a seguir:
Observando que foi utilizado um total de 10.000 números do tipo flutuante para realizar as pesquisas nas respectivas estruturas, considerando que:
- Há um total de 3 números iguais no conjunto de 10.000 números em relação a entrada de 500 números, sendo 0.6% do total de entradas mencionada;
- Há um total de 10 números iguais no conjunto de 10.000 números em relação a entrada de 5.000 números, sendo 0.2% do total de entradas mencionada;
- Há um total de 66 números iguais no conjunto de 10.000 números em relação a entrada de 50.000 números, sendo 1.32%% do total de entradas mencionada;
- Há um total de 601 números iguais no conjunto de 10.000 números em relação a entrada de 500.000 números, sendo 12.02%% do total de entradas mencionada.
•Todos os teste foram realizados em uma máquina com as seguintes especificações, sendo elementos ocasionais de incertezas nas medições de tempo:
Processador: AMD Ryzen 5 1600;
Mémoria : 16 GB - 1600 Mhz;
Sistema Operacional: Linux - Ubuntu 20.04 LTS
Montagem em estrutura
- Levando em consideração esses valores apresentados em relação aos resultados obtidos de tempo foi possível analisar através de comparações que para montagem em estrutura a Árvore Binária de Pesquisa se destaca por não possuir nenhuma limitação em sua inserção como as outras árvores possuem para garantir o balanceamento, ou seja, pela
Árvore Binária de Pesquisanão ser uma estrutura balanceada sem condições de construção, se torna uma estrutura mais eficiente na montagem. Ao contrário disso, foi possível visualizar que a Árvore RedBlack obteve uma menor eficiência em sua montagem em estrutura por se tratar de uma árvore que, entre as árvores balanceadas envolvidas nos testes, possui um maior número de casos para serem tratadas na inserção em mémoria, tornando o processo de montagem um pouco mais lento, havendo uma diferença de 0,060821334 segundos na montagem em estrutura entre aÁrvore Binária de PesquisaeÁrvore RedBlack.
Pesquisa
- Utilizando de base os resultados obtidos e estruturados, foi possível notar pela comparação das médias uma diferença positiva para a Árvore RedBlack, sendo seguida da Árvore AVL e por último a Árvore Binária de Pesquisa em ranking de velocidade de execução durante as pesquisas para até 50.000 entradas, sendo explicado pela falta de balanceamento da
Árvore Binária de Pesquisa, tornando-a mais lenta. Após ser realizado o último testes com um total de 500.000 entradas foi possível observar que obteve uma diferença em relação ao ranking de tempos onde aÁrvore Binária de Pesquisatomou a liderança de mais rápida, seguinda pelaÁrvore AVLficando em ultimo lugar aÁrvore RedBlacksendo a estrutura que demorou mais tempo para realizar pesquisas, podendo ocasionar essa diferença na maior quantidade de entradas por possuir cerca de 12% de seus elementos presentes nos 10.000 números utilizados para consulta e por ser uma árvore um pouco menos estritamente equilibrida que aÁrvore AVLcomo mencionado nas explicações das estruturas acima. Apesar da estruturaÁrvore AVLapresentar resultado mediano em todos os teste é levado em consideração a massa de dados iguais contidas na árvore em relação as 10.000 entradas de consulta pois é vísivel em literatura [1] que aÁrvore AVLse destaca na eficiência de pesquisa em relação aÁrvore RedBlack.
Remoção
- Com esses mesmos dados foi concluido que no processo de remoção de elementos das estruturas estudadas, entre elas se destacou novamente a
Árvore RedBlack, agora em sincronia com conteúdos encontrados na literatura [1] é possível concordar com os resultados forncedios pelo teste, em sequência no ranking está situado aÁrvore AVLe por fim aÁrvore Binária de Pesquisa. AÁrvore RedBlackse destaca nesse processo em relação a outros tipos de árvores mencionados pois menos rotações são realizadas devido ao balancemaneto relativamente relaxado.
Comparações com vetores
- Utilizando os testes citados anteriormente em comparação com teste realizados é possível visualizar utilizando como referência o gráfico apresentado na Figura 22 que estruturas do tipo Árvore apresentam maior eficiência em pesquisa de elementos quando comparadas com utilização da
Busca Bináriaem vetores ordenados, havendo um diferença de tempo de 0,00040225 segundos entre aÁrvore Binária de Pesquisa(estrutura menos eficiente para pesquisa) e a pesquisa em vetores ordenados, onde para a implementação daPesquisa Bináriafoi necessária a utilização da função sort() como mencionada anteriormente na explicação das estruturas, podendo visualizar os tempos de ordenação para os diferentes tamanhos de entradas no gráfico abaixo:
Utilização de estruturas MAPs
- Ao adotar as estruturas MAPs mencionadas em MAPs foi realizado testes, possibilitando as seguintes conclusões.
Para a utilização da função std::map() em comparação com as demais estruturas analisadas com testes de pesquisa foi possível observar que obteve um eficiência maior tendo uma diferença 0,000828749 segundos entre aÁrvore RedBlack(segunda estrutura mais eficiente para pesquisa) e a utilização da estrutura map() para pesquisa, essa eficiência deve se a sua maneira de armazenar elementos internamente comoÁrvore Binária de Pesquisabalanceada, tendo uma complexidade$O(log{n})$ mesmo no pior caso. É possível observar esse ganho de eficiência em comparação com as outras estruturas no gráfico plotado abaixo:
Para a utilização da função std::unordered_map() foi feita também testes de pesquisas, possibilitando a sua comparação com os testes de pesquisas feitos com as estruturas presentes no código, onde foi possível observar um ganho de eficiência ainda maior comparado com a ultima estrutura implementada std::map reduzindo o tempo de pesquisa em 0,002289 segundos (quase um terço do seu tempo) entre ela, possuindo uma diferença de 0,00311775 segundos da Árvore RedBlack (estrutura em árvore mais eficiente em pesquisa). Essa estrutura apresenta esse ganho de tempo no processo de pesquisa por armazenar elementos usando Tabela Hash, buscando uma chave específica torna sua complexidade para a operação de
Para o funcionamento do programa, é necessário incluir as seguintes bibliotecas:
#include 'iostream'#include 'stdio.h'#include 'stdbool.h'#include 'stdlib.h'#include 'vector'#include 'fstream'#include 'random'#include 'iomanip'#include 'string'#include 'sstream'#include 'algorithm'#include 'bits/stdc++.h'#include 'ctime'#include 'unordered_map'#include 'map'
[1] CORMEM, Thomas H. et al. Algoritmos: Teoria e Prática. 3. ed. Cambridge, Massachussetts: MIT Press, [2009]. 1292 p. ISBN 9780262033848.
[2] THAPLIYAL, Rohit. Map vs unordered_map in C++. [S. l.]: GeeksforGeeks, 7 jul. 2022. Disponível em: https://www.geeksforgeeks.org/map-vs-unordered_map-c/. Acesso em: 15 out. 2022.
[3]STROUSTRUP, B. Cplusplus. Disponível em: https://cplusplus.com. Acesso em: 17 out. 2022.
O programa feito de acordo com a proposta possui um arquivo Makefile que realiza todo o procedimento de compilação e execução. Para tanto, temos as seguintes diretrizes de execução:
| Comando | Função |
|---|---|
make clean |
Apaga a última compilação realizada contida na pasta build |
make |
Executa a compilação do programa utilizando o gcc, e o resultado vai para a pasta build |
make run |
Executa o programa da pasta build após a realização da compilação |
Desenvolvido por Pedro Henrique Louback Campos
Aluno do 4° periodo do curso de Engenharia de Computação no CEFET-MG