Conceitos e Classificações de Árvores Binárias em Aplicações Orientadas a Objetos

DAOO DESENVOLVIMENTO DE APLICACOES ORIENTADAS A OBJETOS Arvores Binarias 1 Definigdes 2 Percursos em Arvores Uma arvore binaria 6 um conjunto finito de elementos que 3 Aplicagdes de Arvores Binarias oué 4 Arvores Binarias de Busca 5 Operagdes métodos vazio 2 6 Representagdes e Implementagao em C ou é dividido em trés subconjuntos disjuntos isto 6 com intersegao vazia 1 e um elemento chamado raiz da arvore e uma arvore binaria chamada subarvore esquerda uma arvore binaria chamada subarvore direita As subarvores podem ser vazias pela propria definigdo Cada elemento de uma arvore 6 chamado no da arvore Outras definigdes e Se A éraiz de uma arvore binaria e B é a raiz de uma de suas subarvores entéo A 6 chamado pai de B e B é filho esquerdo ou direito de A dependendo de B ser raiz da subarvore esquerda ou direita respectivamente e Nos que nao tém filhos sao chamados folhas e Umno n1é ancestral de um no n2 e n2 descendente de n1 se n1 6 o pai de n2 ou o pai de algum ancestral de n2 Um no n2 6 descendente esquerdodireito de um no n1 se n2 é filho esquerdodireito de n1 ou o descendente de um filho esquerdodireito de n1 Ca AépaideBeC B é filho esquerdo oY s UX ee Sa ancestrals de Ae pai de D i Se f BeD sio Co descendentes j é esquerdos i f flea e F oe D Ee F sao folhas FIGURA 1 Conceitos basicos de uma arvore binaria 11 Classificagdes de Arvores Binarias Arvores Estritamente Binarias AEB Uma arvore binaria 6 AEB se cada no que nao for folha tiver exatamente 2 filhos Uma arvore estritamente binaria com n folhas tem 2n 1 nos Profundidade de uma Arvore Binaria A raiz de uma arvore binaria esta por definiao no nivel zero O nivel de um outro no qualquer da arvore é 1 mais o nivel do seu pai A profundidade d de uma arvore corresponde ao maior nivel de um no da arvore A profundidade é a maior distancia da raiz até uma folha Arvore Binaria Completa ABC de Profundidade d Uma arvore binaria completa de nivel 0 profundidade d ABC é uma arvore estritamente binaria na qual todas as nivel 1 folhas estado no nivel d Se d é a profundidade da arvore o numero nivel 2 2s d total de nds 6 2 1 O numero total de folhas é 22 nivel 3 Embora uma arvore binaria completa FIGURA 2 Arvore Binaria Completabrde Profundidade 3 possua muitos nos o maximo possivel em cada nivel a distancia da raiz a uma folha qualquer é relativamente pequena Arvore Binaria Quase Completa ABQC E uma arvore binaria de profundidade d onde a cada folha na arvore ou esta no nivel d ou no nivel d1 ela completa até o nivel d1 b para qualquer no nd da arvore com um descendente direito no nivel d todos os descendentes esquerdos de nd que sao folhas estao também no nivel d Uma arvore binaria quase completa pode ter seus nds numerados comegando da raiz indo de cima para baixo e da esquerda para a direita sem que haja auséncia de nenhum no na sequéncia on ran t 1 Ce a Coe 1 NL 3 4 5 FIGURA 3 Uma arvore binaria quase completa Assim uma ABC é uma ABQC A Objetivo Percorrer a arvore binaria em uma dada ordem visitando os seus nos Visitar um nd significa utilizar aquele no para alguma coisa por exemplo imprimir a sua informagao na tela 21 Algoritmo recursivo e Caso base se a arvore binaria a percorrer é vazia nada precisa ser feito e Caso recursivo 3 possibilidades dependendo do momento em que a raiz é visitada Percorrendo em Préordem ou em profundidade 1 Visita a raiz 2 Percorre a subarvore esquerda em préordem 3 Percorre a subarvore direita em préordem Percorrendo em Ordem Simétrica 1 Percorre a subarvore esquerda em ordem simétrica 2 Visita a raiz 3 Percorre a subarvore direita em ordem simétrica Percorrendo em Pésordem 1 Percorre a subarvore esquerda em pdsordem 2 Percorre a subarvore direita em pdsordem 3 Visita a raiz Os nos da arvore da figura 1 sao visitados na seguintes ordens e Préordem ABDCEF e Ordem Simétrica DBAECF e PosOrdem DBEFCA 3 Aplicagdes de Arvores Binarias 31 Eliminagdo de Réplicas e Ordenacgdo de Pacotes Protocolos de comunicagao em rede fragmentam as mensagens grandes em pacotes menores que sao numerados sequencialmente e sdo enviados através da rede veja figura abaixo Como os pacotes podem seguir caminhos diferentesm nado ha a garantia de que eles chegardao ao seu destino exatamente na ordem em que foram enviados pelo remetente Além disso pode haver por causa da perda de mensagens de confirmagao a duplicagao de alguns pacotes que chegam ao destinatario caso mensagens de OK se percam forgando 0 né emissor a reenviar 0 pacote ci i 8 c nm OS oe er Cy i 2 Gc Ei ra a fragmentagao eliminagao de réplicas ordenagaoy FIGURA 4 Uma rede de comunicagao Desta forma a fim de reconstituir a mensagem original o destinatario precisa 1 descartar as réplicas de pacotes recebidos e 2 ordenalos O uso de arvores binarias possibilita a implementagao de um algoritmo eficiente para resolver 1 e 2 Solucdo usando Arvore Binaria O numero do primeiro pacote recebido 6 colocado em um no que se torna a raiz da arvore O numero de pacote subsequente é comparado com o numero da raiz Se for igual achou uma réplica e entao o pacote pode ser descartado Se o numero for menor examinamos a subarvore esquerda se é maior examinamos a subarvore direita Se a subarvore em questdo for vazia o pacote ainda nao tinha sido recebido e o seu numero é colocado em um novo no da arvore binaria naquela posigao Mas se a sub arvore considerada nao for vazia comparamos o numero do pacote recebido com a informagao da raiz daquela subarvore e o processo é entao repetido recursivamente para a subarvore compara com raiz verifica se 6 igual maior ou menor etc Com isso resolvemos o problema 1 Uma vez construida uma arvore binaria desta forma basta percorréla em ordem simétrica para obter os seus elementos ordenados em ordem crescente resolvendo assim 2 Arvores construidas desta forma sao chamadas de Arvores Binarias de Busca 32 Codigo de Huffman Uma Arvore Binaria pode ser usada para representar cédigos de Huffman para caracteres que aparecem em um arquivo texto por exemplo Enquanto os cddigos ASCII ou Unicode utilizam o mesmo numero de bits para codificar cada caractere o cddigo de Huffman utiliza numeros diferentes de bits para codificar os caracteres Se usarmos menos bits para as letras mais comuns por exemplo a e o na lingua portuguesa e mais bits para os caracteres menos comuns por exemplo k we y poderemos reduzir o numero total de bits necessarios O uso do cddigo de Huffman para codificar arquivos texto resulta em arquivos finais menores em termos de numero de bits do que quando outros cdédigos sao usados Assim muitos programas que comprimem arquivos utilizam 0 cédigo de Huffman para gerar arquivos menores economizando desta forma espago para armazenamento ou reduzindo o tempo de envio de arquivos pela Internet A figura abaixo mostra a arvore do cdédigo de Huffman para o alfabeto composto apenas de letras minusculas de acordo com a frequéncia de sua ocorréncia em textos da lingua portuguesa As letras sao folhas Os dados armazenados nos nos que nao sao folhas podem ser ignorados OAL 7 FW OA 7 Vo D8 8 orn 4 D D ota 7 p Ey e t iv s d y 9 ya ii b x Py AL A Mi FIGURA 5 Huffman para letras minusculas em portugués Para obter 0 cddigo de uma letra basta determinar a sequéncia de Os e 1s partindo da raiz da arvore binaria até chegar na letra desejada Na verdade se o caminho da esquerda for tomado um 0 4 adicionado ao cdédigo quando for o caminho da direita adicionase 0 1 Podese desta forma construir um dicionario de cédigos para cada caractere caractere codigo Huffman a 110 b 1011011 c 10111 d 0010 z 0001000 Compare as codificag6es da string teste em ASCII e usado a arvore de Huffman da Figura 5 ASCII Huffman t e s t e t e s t e 01110100 01100101 01110011 01110100 01100101 11110 100 1110 11110 100 4O bits 20 bits Construindo uma Arvore de Huffman Arvores de Huffman podem ser criadas de acordo com a ocorréncia de careteres em um texto especifico de forma a que caracteres mais frequentes naquele texto sejam codificados com menos bits aparecendo assim um nivel menor na arvore binaria Para construir uma Arvore de Huffman procedemos da seguinte forma 1 Obtenha do arquivo a ser codificado uma tabela de frequéncias tf com todos os caracteres presentes no arquivo e suas respectivas frequéncias no arquivo Por exemplo caractere frequéncia a 123 b 12 c 23 2 Cada no da arvore de Huffman a ser construida deve conter 2 campos c 0 caractere e f a frequéncia do caractere c Apenas nas folhas c 6 0 caractere e f é a frequéncia de ocorréncia de c obtida de tf Nos nds que nao sao folhas f 6 calculado como sendo a soma dos fs dos filhos daquele no e c nao é considerado 1678 esr cf c cf caracter frequéncia FIGURA 6 Folhas e Nos Intermediarios 3 Construa em seguida uma fila de arvores binarias com prioridade ascendente f da raiz é considerada a prioridade da arvore binaria Inicialmente sao inseridas na fila com prioridades arvores binarias formadas de um unico no o caractere e sua respectiva frequéncia obtida de tf frente fim recongrorisis olplelelel ascendente NM ny Sn Aner kp 2 ixfe2t Life L Poe ee ee ee ee ee eee eee FIGURA 7 Fila inicial de prioridades 4 Remova as 2 primeiras arvores da fila as com os menores valores de f combinandoas em seguida em uma Unica arvore binaria com a raiz tendo f como a soma das frequéncias das raizes das arvores removidas da fila Insira de volta a nova arvore na fila com prioridades frente fim Teoomgeoriess elplelel ascendente Do kT 2 2 kL2 G4 foe eee ee ee Ke fee Ae FIGURA 8 Duas primeiras arvores combinadas Prdoximo passo frente fim fila com prioridade eleljel ascendente a J LE 4 pet G40 L 1ofA 2 12 FIGURA 9 Trés primeiras arvores combinadas 5 Proceder assim até que reste apenas 1 unica arvore binaria final na fila esta sera a arvore de Huffman WR Uma Arvore Binaria de Busca é uma arvore bindria na qual as informacées guardadas em todos os descendentes esquerdos de um no n tém valores menores que aquele guardado em n na qual as informagdes armazenadas em todos os descendentes direitos de n tém valores maiores ou iguais aquele armazenado em n FIGURA 10 Exemplo de uma Arvore Binaria de Busca ABB WR 51 Operacgoes sobre um no Sendo p um ponteiro para no da arvore ppai é4o0 ponteiro para o pai de p ou paip pesq o0ponteiro para o filho esquerdo de p ou esqp pdir ou dirp é o ponteiro para o filho direito de p pinfo ou infop é a informação contida em p pehraiz ou ehraizp retorna true se p for raiz da árvore ou false caso contrário pehfolha ou ehfolhap retorna true se p for folha da árvore ou false caso contrário pehesq ou ehesqp retorna true se p for filho esquerdo de algum nó da árvore ou false caso contrário pehdir ou ehdirp retorna true se p for filho direito de algum nó da árvore ou false caso contrário pirmao ou irmaop retorna ponteiro para o irmão de p p crianoesqx ou crianoesqxp cria um novo nó filho esquerdo de p com a informação x p crianodirx ou crianodirxp cria um novo nó filho direito de p com a informação x Exemplo Sendo p q r s e t ponteiros para nós da árvore binária da figura abaixo pinfo ou infop B ppai q pesq r pirmao s qehraiz true pehdir false rehfolha true pcrianodirG cria nó apontado por t supondo que p nao tinha FIGURA 11 Operagées em arvores binarias ainda filho direito 52 Operagdes sobre Arvores Binarias Sendo a uma arvore binaria as operagées basicas sobre a sao avazia retorna true sea arvore for vazia ou false caso contrario aadicionax adiciona elemento x a arvore binaria aremovex remove da arvore 0 no com informagao x se houver apercorre visita todos os nos da arvore seguindo uma determinada ordem A Operacao adiciona em Arvores Bindrias de Busca Sendo raiz ponteiro para a raiz de uma avore binaria de busca o algoritmo para adicionar um novo nd contendo informagao x mantendo menores a esquerda e maiores a direita é dado por e se x for igual a inforaiz entdo x ja esta na arvore binaria de busca e se x for menor a inforaiz entao se ainda nao existe um filho esquerdo de raiz entao cria este filho com a informagao x o se ja existe filho esquerdo de raiz adiciona x a subarvore cuja raiz 6 esqraiz e se x for maior a inforaiz entdo se ainda nao existe um filho direito de raiz entao cria este filho com a informagao x o se ja existe filho direito de raiz adiciona x a subarvore cuja raiz 6 dirraiz A Operacdo remove em Arvores Binarias de Busca A operagao para remogao de um no em uma arvore binaria de busca requer a analise de 3 casos distintos Sendo r o nd a remover 1 se r 6 uma folha da arvore binaria de busca simplesmente removemos r alterando o seu pai 2 se r tem apenas 1 filho substituimos o n6é r pelo seu filho casos a e b da figura abaixo 1 i 1 a wa aay 1 FIGURA 12 a r sé tem um filho esquerdo b r so tem um filho direito 3 se rtem 2 filhos entéo encontramos o sucessor s de r que esta na sua subarvore direita é 0 menor elemento dessa subarvore e fazemos com que s substitua r O restante da subarvore direita de r se torna subárvore direita de s e a subárvore esquerda de r se torna a nova sub árvore esquerda de s Há aqui 2 situações particulares A se s é o filho direito de r então substituímos r por s caso c figura abaixo FIGURA 13 c r tem 2 filhos e s é filho de r B se s não foi filho de r figura d abaixo substituímos s pelo seu próprio filho direito t na figura e então substituímos r por s FIGURA 14 d r tem 2 filhos e s não é filho de r 6 Representações e Implementações em C 61 Representação Implícita por Vetores Neste caso armazenamos os dados e a estrutura da árvore binária em um vetor arvbin FIGURA 15 Representação implícita por vetores Se a árvore binária não for quase completa precisamos guardar também informação a respeito da existência ou não de cada nó Por isso temos um vetor de nós sendo que cada nó armazena uma informação info e se existe ou não existe struct No TipoDado info a informação armazenada no nó bool existe se o nó existe ou não e neste caso info é lixo de mem Na figura acima o nó na posição 4 precisa ser marcado como inexistente A raiz da árvore é armazenada sempre na posição zero do vetor armazenada no atributo raiz Assim a classe de uma árvore binária usando a representação implícita por nós fica assim definida ArvBin implícita arvbin vetorNo raiz int 0 construtor vazia bool adicionax TipoDado removex TipoDado percorre infop Indice TipoDado esqp Indice Indice dirp Indice Indice paip Indice Indice irmaop Indice Indice ehesqp Indice boolean ehdirp Indice boolean ehraizp Indice boolean ehfolhap Indice boolean crianoesqx Tipodado p Indice crianodirpx Tipodado p Indice adicionax Indice r Indice percorrer Indice outros métodos auxiliares Em C using TipoDado int tipo dos dados da árvore binária using Indice int índice do vetor constexpr Indice null 1 índice inválido constexpr Indice maxnos 500 funções auxiliares Indice iesqIndice p return 2p1 calcula o índice do filho esquerdo d Indice idirIndice p return 2p2 direito Nó da árvore estruturas são como classes onde tudo é public struct No No existefalse construtor padrão nó não exist NoTipoDado x infox existetrue inicializa info com x e existe TipoDado info bool existe Classe ArvBin Árvore Binária repesentação Implícita por vet class ArvBin protected No arvbinmaxnos vetor para armazenar dados e estrutura da árv implici Indice raiz Operações sobre nós TipoDado infoIndice p retorna info do nó apontado por p Indice esqIndice p filho esquerdo de p ou null Indice dirIndice p filho direito de p ou null Indice paiIndice p pai de p ou null se raiz Indice irmaoIndice p retorna índice para o irmao de p ou null bool ehraizIndice p true se p 6 indice da raiz da arvore false bool ehfolhaIndice p true se p 6 indice de uma folha na arvore 1 bool ehesqIndice p true se p é filho esquerdo de algum no fals bool ehdirIndice p true se p 6 filho direito de algum no false void crianoesqTipoDado x Indice p cria novo no filho esq de p com i void crianodirTipoDado x Indice p cria novo no filho dir de p com i Operacgoes recursivas void adicionaTipoDado x Indice p inclui novo no na avore bin busca j void percorreIndice r percorre a arvore bin em ordem simé public ArvBinI constroi arvore bindria vazia bool vazia true se arvore vazia false cc void adicionaTipoDado x adiciona x a darvore criando uma nova se necess void percorre percorre a arvore binaria na ordem escolhida void removeTipoDado x deleta x da arvore bindria de busca se encc Exercicio 1 Qual o principal problema com a implementagao de arvores binarias usando a representagao implicita por vetores 2 Escreva a implementagao dos métodos da classe ArvBin definida acima arquivo ArvBincpp e crie um programa principal que a teste a operagao remove por ser mais complexa pode ser deixada para a representagao explicita por nds abaixo 62 Representagdo Explicita por Nos Esta representagao de arvores binarias em C evita o problema que existe com a representagao implicita criando nos dinamicamente a medida em que se adicionam elementos a rede FIGURA 16 Representação explícita por nós Abaixo uma possível definição do No No info TipoDado pai No esq No dir No construtorx TipoDado p No ehraiz boolean ehfolha boolean ehesq boolean ehdir boolean irmao No crianoesqx TipoDado crianodirx TipoDado A classe ArvBin fica então definida como ArvBin raiz No construtor destrutor vazia boolean adicionax TipoDado removex TipoDado percorre infop Ponteiro TipoDado esqp Ponteiro Ponteiro dirp Ponteiro Ponteiro paip Ponteiro Ponteiro irmaop Ponteiro Ponteiro ehesqp Ponteiro boolean ehdirp Ponteiro boolean criaarvorex TipoDado Ponteiro crianoesqp Ponteiro x Tipodado crianodirp Ponteiro x TipoDado adicionar Ponteiro x TipoDado percorrer Ponteiro Implementação da Representação Explícita por Nós em C using TipoDado int tipo dos dados da árvore binária Classe ArvBin Árvore Binária repesentação Explícita por nós class ArvBin public ArvBin constrói árvore binária vazia raiz nullptr ArvBin destrói árvore percorrendo os nós e liberando a memória de cada um deles bool vazia const const pois este método não altera a árvo void adicionaTipoDado x void removeTipoDado x void percorre const protected um Nó não precisa ser conhecido fora da árvore binária então a sua definição pode ser feita aqui na área protegida da classe struct No definido como classe mas como tudo é public struc TipoDado info No pai ponteiro p o nó pai No esq ponteiro p o filho esquerdo Nox dir ponteiro p o filho direito NoTipoDado x Nox p construtor do classe No bool ehraiz const bool ehfolha const bool ehesq const bool ehdir const Nox irmao const void crianoesqTipoDado x void crianodirTipoDado x Nox raiz ponteiro para a raiz da arvore bindria de busca métodos internos recursivos r é ponteiro para raiz da ABB void adicionaTipoDado x Nox r adiciona x a arvore void percorreosimNox r const percorre ordem simétrica a arvore void LimpaNo r libera mem dos nos da arvore Nox buscaTipoDado x Nox r busca x na ABB nullptr se nao encor Nox menorNox r retorna ponteiro para menor elem na void removeNox rem remove no rem da arvore outros métodos auxiliares Exercicio 1 O destrutor deve percorrer os nds da arvore em que ordem visitar o no aqui é deletar o nd comando delete 2 Implemente os métodos busca menor de uma arvore binaria de busca ABB 3 Implemente as operagdes de arvores binarias de busca usando a representagao por nos as informagées contidas em cada no devem ser do tipo inteiro Teste a sua implementagao 2021 Luiz A de P Lima Jr