Árvore Binária Costurada

Prévia do material em texto

Universidade Federal de Sergipe 
Centro de Ciências Exatas e Tecnologia - CCET 
Departamento de Computação - DCOMP 
 
 
 
Victor Matheus Sobral Chagas e Yasmim Batista Ferreira 
 
 
 
 
 
 
 
 
 
 
Árvore binária com costura 
Relatório de projeto 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Galileu Santos de Jesus. 
 
 
Introdução 
 
A árvore binária com costura é uma estrutura de dados derivada da árvore de 
busca binária criada para facilitar o andamento das buscas em certa ordem. Essa 
estrutura surgiu por conta da limitação de recursos na realização de travessias pela 
árvore binária, pois para percorrer uma árvore, a travessia tem que ser começada 
pela raiz e de forma recursiva chegar a suas folhas. Como seus nós só tem 
ponteiros para os seus filhos, torna-se impossível voltar na árvore sem que seja 
adicionada informações extras ou modificações em sua estrutura. 
Tal problema demanda um custo de memória e processamento 
desnecessário que poderia ser revertido. Dessa forma, a árvore com costura tem 
como vantagem a reutilização dos ponteiros que não carregam informações 
relevantes para poder realizar um fácil e direto acesso aos seus nós antecessores 
sem que precise realizar uma nova busca por toda árvore. 
Através dessa costura realizada na árvore binária, podemos ter um melhor 
aproveitamento de memória e maior velocidade de processamento, pois não seria 
necessário o uso de recursão ou de modificações na estrutura. 
 
Descrição 
 
A principal característica da árvore com costura é a reutilização dos ponteiros 
das folhas que teriam valores nulos, agora apontam para algum lugar e este lugar 
depende da ordem de busca escolhida para percorrer a árvore (pós ordem, pré 
ordem ou em ordem). Assim, podemos percorrer a árvore sem a utilização de​ stack 
e de forma não recursiva. 
A árvore binária com costura pode ser classificada em duas, sendo ela árvore 
de costura simples e árvore de costura dupla. 
 
A árvore de costura simples (ou 
Single threaded binary tree​) é uma 
árvore binária de busca onde um 
ponteiro de seus nós folhas apontam 
sempre para seu sucessor ou 
antecessor seguindo a leitura “em 
ordem” da árvore. Isso quer dizer que 
todos os ponteiros direitos nulos dos 
nós da árvore apontam para seu 
respectivo sucessor em ordem ou 
todos os ponteiros esquerdos que 
são nulos apontam para seus 
respectivos antecessores. Como 
pode ser visto na ​Fig. 1​. 
 Fig 1​. Árvore binária com costura simples. 
 
 
 
 
 
 
 
 
Já a árvore de costura dupla (ou 
Double Threaded Binary Tree​), 
também é uma árvore binária de 
busca onde ambos os ponteiros, 
direito e esquerdo, dos nós folhas 
apontam para o seus antecessores e 
seus sucessores respectivamente na 
leitura “em ordem”, ou seja, todos os 
ponteiros direitos que são nulos 
devem apontar para seus sucessores 
em ordem e todos os ponteiros 
esquerdos que são nulos devem 
apontar para seus predecessores em 
ordem. Como pode ser visto na ​Fig 2​. 
 
 Fig 2​. Árvore binária com costura dupla 
 
O que caracteriza uma árvore binária com costura, é a presença de 
sinalizadores booleanos em sua estrutura. Tais sinalizadores tem como objetivo 
sinalizar se o nó da árvore possui alguma costura que leva ao seu sucessor ou 
antecessor seguindo leitura “em ordem”. Na árvore com costura simples, há apenas 
uma costura que leva ao sucessor (​Fig 3​), já na árvore com costura dupla, há uma 
costura esquerda, que leva ao antecessor, e uma costura direita que leva ao 
sucessor (​Fig 4​). 
 Fig 3​. Estrutura da árvore com costura simples. ​ Fig 4​. Estrutura da árvore com costura dupla. 
 
As regras de implementação da árvore com costura são bem parecidas com 
as da árvore binária de busca. As principais diferenças nas regras de implementação 
se encontram na inserção e remoção de elementos, além de modificações nas 
implementações de travessias. 
A diferença de implementação presente na inserção se deve a necessidade 
de alterar os booleanos quando alguma costura é alterada tanto na árvore com 
costura dupla, quanto na árvore com costura simples. Tal mudança depende do lado 
pai em que o novo nó passa a ocupar. Na árvore com costura simples, se o 
elemento foi inserido à esquerda de um nó, o novo elemento precisa de uma costura 
que leve ao seu nó pai. Mas se o elemento foi inserido à direita de um nó, é preciso 
verificar se esse nó pai possui alguma costura, caso possua, basta inserir o 
elemento e fazer uma costura com o elemento que antes estava ligado ao pai. Caso 
não possua costura, apenas se insere o elemento normalmente. Essa inserção pode 
ser observada na ​Fig 5. 
 
 
 
 
 Fig 5​. Inserção em árvore com costura simples.​ Fig 6​. Inserção em árvore com costura dupla. 
 
Já na árvore com costura dupla, deve-se tomar um cuidado maior pois é 
preciso considerar a costura a esquerda para que não se perca a referência dos 
antecessores de cada nó. Caso o nó seja adicionado à esquerda, trata-se a costura 
da esquerda do pai desse nó, caso seja adicionada à direita, trata-se a costura 
direita do pai, como pode ser visto na ​Fig 6​. 
A remoção de elementos de uma árvore com costura respeita os mesmos 
casos de remoção da árvore binária de busca, sendo eles: 
Caso 1:​ Quando o nó removido é um nó folha, ou seja: 
Costura simples​: O ponteiro esquerdo é nulo e possui costura. 
Costura dupla​: Possui costura esquerda e direita. 
Caso 2: ​Quando o nó removido possui apenas um filho, ou seja: 
Costura simples​: Possui costura e um filho a esquerda, ou não possui 
costura sem filho a esquerda 
Costura Dupla​: Não possui uma das costuras. 
Caso 3: ​Quando o nó removido possui dois filhos, ou seja: 
Costura simples​: Possui filho a esquerda e não possui costura. 
Costura dupla​: Não possui costura 
Assim como na inserção, a dificuldade na implementação se dá ao rearranjo 
das costuras na remoção do nó, sendo mais complexo na árvore com costura dupla. 
Como dito antes, a travessia pela árvore se torna muito mais fácil quando os 
nós possuem costura. Desse modo, pode ser feito uma travessia “em ordem” tanto 
na árvore com costura simples, como na árvore com costura dupla. Já na árvore 
com costura dupla, tem se a vantagem do fácil acesso do antecessor em ordem de 
um nó graças a costura esquerda, além disso, é possível fazer uma travessia 
“pós-ordem”, como pode ser observado nos módulos de exibição dos elementos da 
árvore feitos na ​Fig 7​. 
 
 
 
 
Fig 7​. Travessias. em ordem e pós-ordem na árvore com costura dupla. 
 
Aplicação 
 
A árvore binária com costura pode ser aplicada quando se necessita realizar 
diversas travessias em uma árvore binária de busca, pois por conta da recursão 
presente no algoritmo de travessia da árvore de busca, é utilizado um espaço de 
stack ​proporcional a altura da árvore. Se a árvore estiver próxima a um equilíbrio, 
sua complexidade equivale a ​O​(log n) para uma árvore contendo ​n​ elementos. No 
pior dos casos, que é quando a árvore é uma lista linear, sua complexidade é de 
O​(n). 
Por conta disso, as aplicações da árvore binária com costura são as mesmas 
da árvore binária de busca. Algumas delas são: 
 
● Implementação de dicionários. 
● Implementação de indexação multinível em bancos de dados. 
● Implementação do algoritmo de codificação de Huffman. 
● Implementação de algoritmos de busca. 
● indexação de endereços de IP. 
● Gerenciamento da área de memória virtual. 
 
 
 
 
Referências Bibliográficas 
 
Szwarcfiter, Jayme Luiz, ​Estruturas De Dados E Seus Algoritmos​ (2010). 
 
Eustáquio, Pablo, ​Estrutura de Dados​. Disponível em: 
<​https://www.ime.uerj.br/~pauloedp/ESTD/Download/EDAP2006.pdf​> 
 
Geeksforgeeks,​ Árvore binária com costura,​ Disponível em: 
<​https://www.geeksforgeeks.org/threaded-binary-tree/​> 
 
Algorithms,​ Árvore binária com costura, implementação​. Disponível em: 
<​https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-com
plete-implementation/​>Tutorialspoint, ​C++ e Implementação de Árvore Binária com Costura​, 
Disponível em: 
<​https://www.tutorialspoint.com/cplusplus-program-to-implement-thread
ed-binary-tree 
https://www.includehelp.com/data-structure-tutorial/threaded-binary-tree
.aspx​> 
 
 
 
https://www.ime.uerj.br/~pauloedp/ESTD/Download/EDAP2006.pdf
https://www.geeksforgeeks.org/threaded-binary-tree/
https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/
https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/
https://www.tutorialspoint.com/cplusplus-program-to-implement-threaded-binary-tree
https://www.tutorialspoint.com/cplusplus-program-to-implement-threaded-binary-tree
https://www.includehelp.com/data-structure-tutorial/threaded-binary-tree.aspx
https://www.includehelp.com/data-structure-tutorial/threaded-binary-tree.aspx