Prévia do material em texto

<p>Árvores: estruturas hierárquicas</p><p>Apresentação</p><p>As estruturas de dados são recursos fundamentais para a resolução de problemas envolvendo</p><p>sistemas computacionais. Matrizes e listas são exemplos de estruturas lineares que armazenam</p><p>informações de maneira sequencial. Por serem lineares, o tempo necessário para consultar uma</p><p>lista será proporcional ao seu tamanho. Então imagine buscar um número em uma lista com 100</p><p>itens, o</p><p>número de comparações necessárias para encontrar (ou não encontrar) um item pode ser tão</p><p>grande quanto alguns múltiplos de 100.</p><p>Mesmo em uma máquina que pode fazer milhões de comparações por segundo, procurar m itens</p><p>levará aproximadamente m segundos, e como tempo é dinheiro, você precisa conhecer estruturas</p><p>nas quais o tempo de busca pode ser minimizado. Além disso, devido à natureza de</p><p>alguns problemas, você precisará utilizar estruturas conhecidas</p><p>como hierárquicas.</p><p>Nesta Unidade de Aprendizagem, você irá conhecer uma estrutura hierárquica importante chamada</p><p>árvore. Uma árvore herda característica das topologias em níveis, nas quais as informações</p><p>mais gerais estão no topo e as específicas na base. As árvores são empregadas para armazenar</p><p>dados de diferentes contextos,</p><p>tais como diretórios de arquivos, banco de dados, processos decis��rios,</p><p>bem como agilizar o tempo de busca de informações.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Identificar as características de um TAD do tipo árvore em Python.•</p><p>Descrever o armazenamento hierárquico dos elementos em Python.•</p><p>Especificar as aplicações que utilizam representações hierárquicas</p><p>de dados.</p><p>•</p><p>Desafio</p><p>Em diversas aplicações são necessárias estruturas mais complexas</p><p>do que estruturas puramente sequenciais, entre elas destacam-se as árvores, pois existem inúmeros</p><p>problemas práticos que são modelados através delas. Além disso, as árvores, em geral, admitem um</p><p>comportamento computacional simples e eficiente.</p><p>Os compiladores fazem uso dessas estruturas e uma das etapas no processo de compilação é</p><p>identificar se o programa não apresenta erros, tais como o uso indevido de palavras reservadas ou</p><p>uso de símbolos que não foram identificados e não fazem parte do dicionário</p><p>da linguagem de programação.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/997bd18c-8b5d-4661-a686-5c98dd858b10/1ae097f7-a880-4110-a75f-7d5979037afa.png</p><p>Responda:</p><p>1) Quantas comparações são necessárias para verificar se a palavra</p><p>bag existe no dicionário? Mostre essa informação para a empresa,</p><p>a fim de justificar que a atual forma de organizar os dados não é a</p><p>mais eficiente.</p><p>2) O responsável pela empresa solicitou que você proponha uma nova estrutura para organizar o</p><p>dicionário, possibilitando otimizar o número de comparações realizadas durante a verificação de</p><p>uma string. Projete a nova estrutura do dicionário.</p><p>Infográfico</p><p>Uma árvore é um tipo abstrato de dados (TAD) usado para representar estruturas hierárquicas. Esse</p><p>TAD é adaptado para modelar situações diversas. Assim, existem tipos diferentes de árvores, tais</p><p>como as binárias e as genéricas. Em uma árvore binária, como o próprio nome</p><p>diz, cada nó pode ter, no máximo, duas arestas; as árvores genéricas, por sua vez, não têm limitação</p><p>de arestas.</p><p>No que tange a implementação da árvore binária, ela se torna mais simples quando comparada à</p><p>árvore genérica. Diante disso, surge</p><p>uma alternativa: converter árvore genérica para árvore binária.</p><p>No Infográfico a seguir, você encontrará mais detalhes sobre a árvore genérica e os passos para</p><p>transformá-la em árvore binária.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/8844b488-f2bf-4420-9f1d-a30b4b8327f9/47bbc9f2-759a-476f-bb39-00e597977ea9.png</p><p>Conteúdo do livro</p><p>Algoritmos precisam ser aprimorados para facilitar a resolução de problemas práticos, logo as</p><p>estruturas também seguem essa lógica. As árvores são estruturas de dados empregadas em várias</p><p>situações do dia a dia, tais como movimento de jogadores, corretores ortográficos e organização de</p><p>processos decisórios.</p><p>Para facilitar o uso dessa estrutura, é necessário definir um tipo abstrato de dado (TAD) para</p><p>representá-la e implementar métodos que possibilitem a inserção, a remoção e a consulta de</p><p>informações, além de outros.</p><p>No capítulo Árvores: estruturas hierárquicas, da obra Estrutura de dados, você conhecerá o TAD e</p><p>verá demais detalhes dessa importante estrutura.</p><p>Boa leitura.</p><p>ESTRUTURA</p><p>DE DADOS</p><p>Clicéres Mack Dal Bianco</p><p>Árvores: estruturas</p><p>hierárquicas</p><p>Objetivos de aprendizagem</p><p>Ao final deste texto, você deve apresentar os seguintes aprendizados:</p><p>� Identificar as características de um TAD do tipo árvore em Python.</p><p>� Descrever o armazenamento hierárquico dos elementos em Python.</p><p>� Especificar as aplicações que utilizam representações hierárquicas</p><p>de dados.</p><p>Introdução</p><p>Uma árvore é considerada uma estrutura de dados não linear, um formato</p><p>que possibilita organizar os dados e suas ligações de maneira mais pro-</p><p>dutiva do que o simples antes e depois permitido nas estruturas lineares,</p><p>como as listas com base em vetores ou em encadeamentos.</p><p>As árvores fornecem uma organização natural dos dados, principal-</p><p>mente quando as informações estão dispostas em forma de pirâmide,</p><p>como em um organograma empresarial, que apresenta uma distribuição</p><p>hierárquica, com os líderes no topo e os demais funcionários na base.</p><p>Diante disso, as árvores tornaram-se estruturas onipresentes em uma</p><p>ampla faixa de aplicações voltadas para os sistemas de arquivos, interfaces</p><p>gráficas, bancos de dados e inteligência artificial. Neste capítulo, você</p><p>aprofundará seus conhecimentos sobre as estruturas de dados do tipo</p><p>árvores.</p><p>Características de um TAD do tipo árvore</p><p>As estruturas do tipo árvore recebem esse nome porque fazem analogia às</p><p>árvores biológicas, mas de cabeça para baixo, conforme mostra a Figura 1a.</p><p>Serão utilizadas terminologias como raiz e folha para identificar os nós, como</p><p>o nó raiz, referente à informação que está no topo. De maneira intuitiva,</p><p>o exemplo da Figura 1b apresenta uma estrutura para categorização de veícu-</p><p>los, em que o nó veículo é a raiz. É interessante observar que a raiz é um nó</p><p>peculiar, que indica o ponto de partida para as operações de busca, inserção</p><p>e remoção, não possuindo um nó antecessor.</p><p>Um tipo especial de árvores são as binárias, onde cada nó pode ter,</p><p>no máximo, dois nós diretamente ligados a ele. O conjunto de nós que formam</p><p>uma árvore pode ser particionado em três subconjuntos distintos, que são:</p><p>o subconjunto formado somente pelo nó raiz; o subconjunto formado pelos</p><p>nós da esquerda; e o subconjunto dos nós da direita. Essa divisão pode ser</p><p>visualizada na Figura 1c.</p><p>Figura 1. (a) Árvore invertida que demonstra a analogia das estruturas hierárquicas. (b) Apli-</p><p>cação de árvore para categorizar veículos. (c) Exemplo de árvore binária e seus subconjuntos.</p><p>Fonte: (a) DMCA/PngLot.com. (b) Edelweiss e Galante (2009, p. 169). (c) Adaptada de Edelweiss e</p><p>Galante (2009).</p><p>(a) (b)</p><p>(c)</p><p>Árvores: estruturas hierárquicas2</p><p>Na representação de uma árvore binária, cada nó contém um campo de</p><p>informação (pode ser do tipo inteiro, float ou string) e os ponteiros para os</p><p>filhos. Para a organização geral de uma árvore, utiliza-se um Tipo Abstrato</p><p>de Dados (TAD), ou seja, um modelo estruturado capaz de descrever um</p><p>ambiente com número finito de objetos, em que os objetos são associados por</p><p>meio de determinados relacionamentos. Criação de nós, inserção, remoção e</p><p>busca de informação são exemplos de operações básicas fornecidas em um</p><p>TAD do tipo árvore.</p><p>Segundo Goodrich e Tamassia (2013), um TAD é uma forma de definir um</p><p>tipo de dado que, nesse caso, seria o nó, juntamente com as suas operações</p><p>que manipulam esse tipo</p><p>de dado. A implementação das operações não precisa</p><p>ser descrita. Assim, para descrever uma estrutura de dados abstrata, deve-se:</p><p>� fornecer o relacionamento entre os objetos que estão sendo armazenados;</p><p>� especificar as operações que poderão ser utilizadas para representar</p><p>relacionamentos de cenários hierárquicos.</p><p>Os relacionamentos são as próprias ligações dos nós em determinada árvore.</p><p>No exemplo da Figura 1C, o nó 5 está ligado com o nó 3 (seu descendente). Um</p><p>ponto importante dessa relação é que o nó descendente só pode ser acessado</p><p>pelos seus nós ancestrais. Árvores binárias são, em geral, implementadas como</p><p>uma estrutura dinâmica, ou seja, usa-se alocação de memória dinamicamente</p><p>por meio de ponteiros, e o TAD possibilitará os encadeamentos. Os encadea-</p><p>mentos, no caso de um nó, representarão os relacionamentos ou os seus filhos.</p><p>Observe o código a seguir, em que o nó de uma árvore é composto por três</p><p>informações, o label, que pode ser um nome ou número, o apontador esquerdo</p><p>e o apontador direito, que indicam os relacionamentos, para a esquerda (left)</p><p>e para a direita (right). A classe nó é inicializada com o atributo label,</p><p>e os apontadores para esquerda e direta do nó são inicializados como vazios.</p><p>Class No:</p><p>def __init__(self, label):</p><p>self.label = label</p><p>self.left = None</p><p>self.right = None</p><p>De acordo com Goodrich, Tamassia e Goldwasser (2013), em Python, todos</p><p>os tipos de dados (como int, float e str) são classes, então, definir uma</p><p>classe é criar um novo tipo de dado ou um TAD, cujo comportamento lógico</p><p>3Árvores: estruturas hierárquicas</p><p>é dado por um conjunto de operações. A seguir, observa-se a classe de uma</p><p>árvore. O código apresenta os protótipos das principais operações. Todos os</p><p>métodos comporão o TAD BinaryTree. A raiz (root) é inicializada como</p><p>vazia. A operação inserção (insert) recebe como parâmetro o dado a ser</p><p>armazenado e, nessa operação, localiza-se a posição que a informação deve</p><p>ser inserida seguindo os critérios de armazenamento de uma árvore binária.</p><p>class BinaryTree:</p><p>def _ _ init _ _ (self):</p><p>self.root = None</p><p># insere informação</p><p>def insert(self, number):</p><p># verifica se árvore está vazia</p><p>def empty(self):</p><p># mostra em pré-ordem</p><p>def show _ pre(self, curr _ node):</p><p># mostra em-ordem</p><p>def show _ em(self, curr _ node):</p><p># mostra em-pós-ordem</p><p>def show _ pos(self, curr _ node):</p><p>#remove nó</p><p>def remove(self, number):</p><p># busca informação</p><p>def search(self, number):</p><p>#recebe o endereço do nó raiz</p><p>def getRoot(self):</p><p>#busca o maior valor</p><p>def bigger(self):</p><p>Árvores: estruturas hierárquicas4</p><p>A árvore pode ser percorrida de três formas, em pré-ordem, em ordem e</p><p>em pós-ordem. Os protótipos desses percursos são show_pre, show_em</p><p>e show_pos. Já a operação de remoção (remove) recebe a informação a ser</p><p>removida, busca a sua localização e, após a efetivação da remoção, os enca-</p><p>deamentos serão atualizados. Observe que, nesse TAD, foram incluídas duas</p><p>operações adicionais: getRoot e bigger. A primeira retorna o endereço</p><p>de memória da raiz, e a segunda localiza o maior valor da árvore.</p><p>Já o protótipo de busca (search) recebe como parâmetro o dado a ser</p><p>localizado que, nesse caso, é um número (number). A busca inicializa veri-</p><p>ficando se a árvore não está vazia. Para evitar qualquer alteração indesejada</p><p>na raiz, seu endereço é passado para uma estrutura auxiliar (curr_node).</p><p>Caso a árvore não esteja vazia, um conjunto de instruções é repetido enquanto</p><p>não localizar o número ou uma subárvore vazia.</p><p>Segundo Baka (2017), a busca é como um processo de decisão que realiza</p><p>perguntas a fim de identificar qual direção prosseguir. Inicia-se perguntando</p><p>se o valor que está no nó (curr_node.getLabel() ) é igual ao número.</p><p>Se for igual, a busca termina com sucesso. Caso contrário, uma segunda</p><p>pergunta é feita,</p><p>- o número é menor que o valor do nó?</p><p>Se a resposta for sim, a busca continuará na subárvore à esquerda, se a</p><p>resposta for “maior que”, a busca continuará na subárvore à direita. Por fim,</p><p>se chegarmos a uma subárvore vazia, a pesquisa termina sem êxito.</p><p>def search(self, number):</p><p># verifica se a árvore está vazia</p><p>if self.empty():</p><p>print(‘Arvore está vazia!’)</p><p>else:</p><p># árvore não está vazia, busca número</p><p>curr _ node = self.root</p><p>while True:</p><p>if curr _ node.getLabel() == number:</p><p>print('O dado foi encontrado na árvore ')</p><p>break;</p><p># verifica se a busca continua para a esq. ou</p><p>a dir.</p><p>5Árvores: estruturas hierárquicas</p><p>if number< curr _ node.getLabel():</p><p>curr _ node = curr _ node.getLeft() #continua</p><p>a esquerda</p><p>else:</p><p>curr _ node = curr _ node.getRight() # continua</p><p>a direita</p><p>Os TADs das árvores encapsulam as operações básicas como inserção, busca, remoção</p><p>e percursos. Além das operações básicas, você pode incluir outros métodos, como os</p><p>baseados nos relacionamentos dos nós, por exemplo, encontrar o pai de determinado</p><p>nó, retornar aos nós antecessores e, ainda, localizar o maior valor e retornar à altura</p><p>da árvore.</p><p>Armazenamento hierárquico dos elementos</p><p>As propriedades das árvores impactam no armazenamento das informações.</p><p>As principais propriedades que envolvem uma árvore são grau, nível, altura,</p><p>nós folhas, nó pai, nó filho e os critérios de armazenamento. O grau de um nó</p><p>representa o seu número de subárvores. Por sua vez, o grau de uma árvore cor-</p><p>responde ao número máximo de graus de todos os seus nós. Uma árvore binária</p><p>tem grau máximo igual a 2. A Figura 2a traz os nós e seus respectivos graus.</p><p>Figura 2. (a) Graus dos nós de uma árvore. (b) Nó raiz e nós folhas.</p><p>(a) (b)</p><p>Árvores: estruturas hierárquicas6</p><p>O nó denominado pai refere-se ao nó que está no topo e com ligação direta</p><p>a outro nó. Logo, o nó filho é o nó abaixo e, finalmente, o nó folha é o nó que</p><p>não possui filhos (Figura 2b). Diante disso, pode-se definir os níveis de uma</p><p>árvore. O nível é a distância do nó raiz, então, o nível do nó raiz é zero. Dessa</p><p>forma, é possível definir que a altura é o nível mais distante da raiz, conforme</p><p>poder ser observado na Figura 3.</p><p>Figura 3. Níveis e altura de uma árvore.</p><p>Fonte: Adaptada de Ascencio e Araujo (2011).</p><p>As propriedades a seguir são importantes para definir os relacionamentos</p><p>durante o armazenamento. Segundo Cormen et al. (2012), o armazenamento</p><p>deve respeitar os seguintes critérios:</p><p>� todos os nós de uma subárvore da direita são maiores do que o nó raiz;</p><p>� todos os nós de uma subárvore da esquerda são menores do que o nó raiz;</p><p>� cada subárvore também é conhecida como árvore.</p><p>7Árvores: estruturas hierárquicas</p><p>Armazenamento em uma árvore</p><p>O processo de armazenamento de informações em uma estrutura do tipo árvore</p><p>é similar ao método de busca em que, inicialmente, é verificado se a árvore</p><p>está vazia e, em caso afirmativo, o nó é definido como raiz. Caso contrário,</p><p>compara-se o elemento com a raiz: se for menor, segue para a subárvore da</p><p>esquerda e, se for maior, segue para a subárvore da direita. Esse processo é</p><p>realizado até encontrar uma posição livre.</p><p>Veja o exemplo para o armazenamento dos valores 37, 20, 80 apresentado</p><p>na Figura 4. Considere que a árvore está vazia, então, na primeira inserção,</p><p>o nó 37 será alocado como raiz. O próximo número que será armazenado é o</p><p>20 e, dessa vez, a raiz não está vazia. Então, é testado se esse número é menor</p><p>do que o valor que está na raiz. Em caso afirmativo, busca-se uma posição</p><p>livre à esquerda. Nesse exemplo, como a subárvore à esquerda do nó 37 está</p><p>vazia, encontrou-se a posição que referenciará o nó 20. Agora, será a vez</p><p>de armazenar o número 80, que é maior do que 37, e esse nó está com a sua</p><p>subárvore da direita vazia, então, esse é o endereço que referenciará o nó 80.</p><p>Figura 4. Exemplo de inserção em uma árvore.</p><p>Fonte: Adaptada de Ascencio e Araujo (2011).</p><p>Caso fosse necessário inserir o valor 72 na árvore anterior, a inserção</p><p>seguiria a mesma lógica detalhada antes. A árvore será acessada pela</p><p>raiz,</p><p>verifica-se a direção a seguir, como o número (72) é maior do que o atual valor</p><p>da raiz (37), e a posição da direita está alocada, o número será comparado com</p><p>80 e alocado à esquerda deste, conforme mostra a Figura 5. A cada inserção</p><p>os encadeamentos são atualizados.</p><p>Árvores: estruturas hierárquicas8</p><p>Figura 5. Operação de inserção do número 72.</p><p>Fonte: Adaptada de Ascencio e Araujo (2011).</p><p>A implementação da inserção é similar à da busca. O método recebe o</p><p>número, que é inicializado como um nó. Após, é necessário verificar se a</p><p>árvore está vazia, caso contrário, entra-se no laço de repetição. Os primeiros</p><p>testes no laço de repetição determinam se a tentativa de inserção ocorrerá na</p><p>subárvore da esquerda ou da direita. Esses testes são feitos até encontrar um</p><p>endereço livre, ou seja, um pai que referenciará o nó.</p><p>def insert(self, number):</p><p># cria um novo nó</p><p>node = Node(number)</p><p># verifica se a árvore está vazia</p><p>if self.empty():</p><p>self.root = node</p><p>else:</p><p># árvore não vazia,</p><p>curr _ node = self.root</p><p>dad _ node = None</p><p>while True:</p><p>if curr _ node != None:</p><p>9Árvores: estruturas hierárquicas</p><p># verifica se vai para esquerda ou direita</p><p>if node.getLabel() < curr _ node.getLabel():</p><p>curr _ node = curr _ node.getLeft() # pros-</p><p>segue a esquerda</p><p>else:</p><p>curr _ node = curr _ node.getRight() # pros-</p><p>segue a direita</p><p>else:</p><p># se curr _ node é None, então encontrou onde</p><p>inserir</p><p>if node.getLabel() < dad _ node.getLabel():</p><p>dad _ node.setLeft(node) #insere a esquerda</p><p>do nó pai</p><p>else:</p><p>dad _ node.setRight(node) #insere a direita</p><p>do nó pai</p><p>break # sai do loop</p><p>Nesse tipo de árvore, a ordem de inserção das informações determinará os encadeamen-</p><p>tos, por exemplo, a inserção da sequência de valores 3,10,15, resultará na árvore a seguir:</p><p>Árvores: estruturas hierárquicas10</p><p>Agora, se você inserir os valores em outra ordem, os relacionamentos se alteram.</p><p>Para a inserção na sequência 10,3,15, o resultado é apresentado a seguir:</p><p>Observe que o primeiro valor será a raiz, e os demais relacionamentos são definidos</p><p>respeitando as propriedades, maiores valores à direita e menores valores à esquerda.</p><p>Remoção em uma árvore</p><p>O TAD da árvore binária também possibilita a remoção de nós. Para a remoção</p><p>de um nó da árvore, existem três situações a considerar: se o nó não tem filhos,</p><p>ou seja, é um nó folha, ele poderá ser removido sem ajustes posteriores na árvore;</p><p>se o nó possui apenas um filho, então esse filho passará a ocupar a posição do</p><p>nó removido; e se o nó possui dois filhos, então encontra-se o sucessor desse</p><p>nó, que deve estar na subárvore à direita do nó a ser removido. O caso mais</p><p>simples é a remoção de um nó folha, bastando alterar o ponteiro do pai para</p><p>nulo. A Figura 6 demonstra a remoção do nó 7 e a árvore final após a remoção.</p><p>Figura 6. Operação de remoção do nó 7.</p><p>Fonte: Adaptada de Tenenbaum, Langsam e Augenstein (2010).</p><p>11Árvores: estruturas hierárquicas</p><p>O segundo caso trata da remoção de um nó que possui um filho (à es-</p><p>querda ou à direita). A Figura 7 demonstra a remoção do nó 8, que possui</p><p>um filho à esquerda. É possível perceber que um dos ponteiros do pai deve</p><p>ser atualizado, no exemplo, o ponteiro à direita do pai (o nó 3) recebeu o nó 7</p><p>(filho do nó removido).</p><p>Figura 7. Operação de remoção do nó 8.</p><p>Fonte: Adaptada de Tenenbaum, Langsam e Augenstein (2010).</p><p>Considerando o terceiro caso, a remoção trata um nó que possui filhos à</p><p>esquerda e à direita. A Figura 8 apresenta a remoção do nó 3. Esse nó possui</p><p>duas subárvores que devem ser referenciadas por outro nó, ou seja, o nó</p><p>sucessor. O sucessor será o nó que está mais à esquerda (ou de menor valor)</p><p>na subárvore à direita do nó que será removido. A subárvore à direita do nó 3</p><p>apresenta o nó 7 mais à esquerda. O nó sucessor apontará para os filhos do nó 3.</p><p>Figura 8. Remoção do nó 3 com atualização dos ponteiros do nó sucessor (nó 7). O ponteiro</p><p>do nó pai também é atualizado com o endereço do nó sucessor.</p><p>Fonte: Adaptada de Tenenbaum, Langsam e Augenstein (2010).</p><p>Árvores: estruturas hierárquicas12</p><p>A classe usada para a remoção recebe como parâmetro um número a ser</p><p>removido. O algoritmo inicia verificando se a árvore não está vazia. A árvore</p><p>não estando vazia, entra-se no laço de repetição para localizar a posição do</p><p>número. Compara-se o valor do nó atual (curr_node) com o número e, se</p><p>for menor, a busca continua à esquerda. Ao localizar a posição, o nó atual é</p><p>atualizado com o endereço dessa posição (curr_node.getLeft()). Caso</p><p>contrário, a busca continua à direita. Nesse caso, o nó atual recebe o endereço</p><p>da subárvore à direita (curr_node.getRight()).</p><p>def remover(self, number):</p><p>if self.root == None:</p><p>return False # se arvore vazia</p><p>curr _ node = self.root</p><p>dad = self.root</p><p>child _ left = True</p><p># Busca a posição do número</p><p>while curr _ node.getLabel() != number: # enquanto não</p><p>encontrou</p><p>dad = curr _ node</p><p>if number < curr _ node.getLabel(): # caminha para esquerda</p><p>curr _ node = curr _ node.getLeft()</p><p>child _ left = True # é filho a esquerda? sim</p><p>else: # caminha para direita</p><p>curr _ node = curr _ node. getRight ()</p><p>child _ left = False # é filho a esquerda? NAO</p><p>if curr _ node == None:</p><p>return False # encontrou uma folha, então sai do laço</p><p>� # se chegou aqui, significa que encontrou o número (number);</p><p>� # "curr_node": contém a referência ao nó a ser eliminado;</p><p>� # "dad": contém a referência para o pai do nó a ser eliminado;</p><p>� # "child_left": é verdadeira se o nó atual é filho à esquerda do pai.</p><p>Em relação ao nó a ser removido, a variável booleana (child_left)</p><p>será verdadeira, caso esse nó seja filho à esquerda, ou falsa, se o nó for filho</p><p>à direita. Essa variável será utilizada para atualizar o endereço do nó pai.</p><p>Após localizar a posição do nó, a próxima etapa do método de remoção será</p><p>identificar qual dos três casos enquadra o nó a ser removido e processar as</p><p>atualizações dos ponteiros.</p><p>13Árvores: estruturas hierárquicas</p><p>Supondo que o número a ser removido seja encontrado na árvore, os pró-</p><p>ximos testes condicionais identificarão qual é a situação que condiz com</p><p>esse nó. A seguir, veremos como pode ser implementado cada um dos casos.</p><p>Primeiro caso</p><p>Vamos iniciar com o caso mais simples, em que o nó a ser removido é uma</p><p>folha. Observe o código a seguir, a primeira condição retorna se esse nó é a</p><p>raiz e, em caso afirmativo, o endereço da raiz recebe nulo. Caso o nó a ser</p><p>removido seja um filho à esquerda (child_left), então o ponteiro à esquerda</p><p>do pai recebe nulo (None). Não sendo um filho à esquerda, então significa</p><p>que ele está à direita, e o ponteiro do pai à direita recebe nulo.</p><p># Caso 1;</p><p># Se não possui nenhum filho (é uma folha), elimine-o</p><p>if curr _ node.getLeft() == None and curr _ node.getRight()</p><p>== None:</p><p>if curr _ node == self.root:</p><p>self.root = None # se raiz</p><p>else:</p><p>if child _ left:</p><p>dad.left = None # se for filho a esquerda do pai</p><p>else:</p><p>dad.right = None # se for filho a direita do pai</p><p>Segundo caso</p><p>No segundo caso, o nó a ser removido tem um filho à esquerda ou à direita.</p><p>Inicialmente, é avaliado se o filho está à esquerda (curr_node.Left).</p><p>Se for o caso, é necessário guardar o endereço desse filho, ou seja, o nó que</p><p>ficará órfão. Depois, testa-se o nó a ser removido que está alocado à esquerda</p><p>do pai (child_Left), então, o ponteiro à esquerda do nó pai (dad.Left)</p><p>receberá o endereço do nó órfão.</p><p>Árvores: estruturas hierárquicas14</p><p>Caso o filho, ou seja, o nó órfão, esteja à direita (curr_node.Right),</p><p>o próximo teste será para verificar se o nó a ser removido é um filho da</p><p>esquerda ou (dad. Right) da direita. Se for da direita, o ponteiro à direita</p><p>do nó pai referenciará o nó órfão. Se for da esquerda, o endereço à esquerda</p><p>do pai (dad.Left) referenciará o nó órfão.</p><p># Caso 2</p><p># Se o nó a ser removido possui um filho a esquerda</p><p>if curr _ node.Left != None:</p><p>if child _ Left:</p><p>dad.Left = curr _ node.Left # se for filho a es-</p><p>querda do pai</p><p>else:</p><p>dad.Right = curr _ node.Left # se for filho a di-</p><p>reita do pai</p><p># Se o nó a ser removido possui um filho a direita</p><p>elif curr _ node.Right != None:</p><p>if child _ Left:</p><p>dad.Left = curr _ node.Right # se for filho a es-</p><p>querda do pai</p><p>else:</p><p>dad.Right = curr _ node.Right # se for filho a</p><p>direita do pai</p><p>Terceiro caso</p><p>O último caso remove o nó que possui subárvore à esquerda e subárvore à</p><p>direita. Nessa situação, o primeiro procedimento é encontrar o nó sucessor,</p><p>ou seja, o nó que ocupará a posição do nó que será removido. O sucessor deve</p><p>ser o menor valor da subárvore à direita. Se o nó a ser removido é um filho à</p><p>esquerda (child_Left), então o endereço à esquerda do pai apontará para</p><p>o sucessor. Se o nó a ser removido é um filho à direita, o endereço à direita do</p><p>pai apontará para o sucessor. Por fim, o ponteiro à esquerda do nó sucessor é</p><p>atualizado com o filho à esquerda do nó a ser removido (successor.Left</p><p>= curr_node.Left). Um exemplo é o caso do nó 7 apontando para o nó 2,</p><p>conforme mostra a Figura 8.</p><p>15Árvores: estruturas hierárquicas</p><p># Caso 3</p><p># Se possui mais de um filho, se for um avô ou outro grau</p><p>maior de parentesco</p><p>successor = self.noSuccessor(curr _ node)</p><p># Usando sucessor que seria o Nó mais à esquerda da</p><p>subárvore a direita</p><p>if child _ Left:</p><p>dad.Left = sucessor # se for filho a esquerda do pai</p><p>else:</p><p>dad.Right = sucessor # se for filho a direita do pai</p><p>successor.Left = curr _ node.Left # acertando o ponteiro</p><p>a esquerda do sucessor</p><p># agora que ele assumiu a posição correta</p><p>na árvore</p><p>return True</p><p>Além de retornar o nó com menor valor da subárvore à direita, o método</p><p>que retornará o nó sucessor (NoSuccessor) atualizará os ponteiros dessa</p><p>subárvore. O método a seguir recebe como parâmetro o nó a ser removido</p><p>(noRemove). São inicializados outros dois nós, o dadSuccessor e o suc-</p><p>cessor. Ao finalizar o laço de repetição (while), o nó sucessor (succes-</p><p>sor) será o nó mais à esquerda da subárvore à direita, o dadSuccessor</p><p>será o pai do nó sucessor, e o noRemove será o nó que deverá ser excluído.</p><p># Método Sucessor</p><p>def noSuccessor(self, noRemove): # O parâmetro é a referência</p><p>para o Nó que deseja-se remover</p><p>dadSuccessor = noRemove</p><p>successor = noRemove</p><p>curr _ node = noRemove.Right # vai para a subárvore a</p><p>direita</p><p>while curr _ node!= None: # enquanto não chegar no Nó</p><p>mais à esquerda</p><p>dadSuccessor = sucessor</p><p>successor = curr _ node</p><p>curr _ node = curr _ node.Left # caminha para a esquerda</p><p>if successor != no _ remove.Right: # se sucessor não é o</p><p>filho a direita do Nó a ser eliminado</p><p>Árvores: estruturas hierárquicas16</p><p>dadSuccessor.Left= successor.Right # pai herda os filhos</p><p>do sucessor</p><p>successor.Right = no _ remove.Right # guardando a refe-</p><p>rencia a direita do sucessor</p><p>return successor</p><p>A ferramenta Visualgo realiza a inserção de maneira interativa em uma árvore e pode</p><p>ser acessada no endereço a seguir.</p><p>https://visualgo.net</p><p>Aplicações que utilizam árvores</p><p>Em diversas situações, são necessárias estruturas mais complexas do que</p><p>as puramente sequenciais. As árvores são largamente empregadas nas mais</p><p>diversas áreas da computação como banco de dados, sistemas operacionais,</p><p>compiladores, redes de computadores, entre outras. A seguir, estão descritos</p><p>alguns exemplos de aplicações.</p><p>Árvore genealógica</p><p>Imagine uma árvore genealógica que fornece os relacionamentos entre ge-</p><p>rações: avós, pais, filhos, irmãos. Essa organização é usada pelos profissio-</p><p>nais de Direito, pois dela decorrem os deveres e os direitos dos familiares.</p><p>De modo geral, organiza-se árvores genealógicas hierarquicamente.</p><p>No exemplo da Figura 9, o nó raiz está identificado como “eu”. Uma operação</p><p>necessária seria localizar o grau de parentesco dos nós. Nessa situação, os</p><p>níveis da árvore são um termo importante, pois, a partir do nível, é possível</p><p>criar um método para retornar o grau de parentesco entre nós. Nesse caso,</p><p>quanto maior o nível, mais distante é o parentesco.</p><p>17Árvores: estruturas hierárquicas</p><p>Figura 9. Exemplo de árvore genealógica organizada hierarquicamente.</p><p>Estrutura organizacional de uma empresa</p><p>A Figura 10 apresenta uma estrutura organizacional de uma empresa. A partir</p><p>de determinado gerente, seria fácil listar todos os operadores (Op.) que são</p><p>subordinados a ele. Também é possível verificar os gerentes que estão direta-</p><p>mente relacionados à determinado diretor. A subárvore da esquerda pode ser</p><p>categorizada com os funcionários responsáveis pelas vendas, e a subárvore da</p><p>direita, com os funcionários responsáveis pelo marketing, agilizando, assim,</p><p>a localização das equipes.</p><p>Árvores: estruturas hierárquicas18</p><p>Figura 10. Estrutura simples de uma organização empresarial.</p><p>Fonte: Veyrat (2017, documento on-line).</p><p>Documento HTML</p><p>A linguagem HTML é a estrutura básica das páginas web, e essa linguagem</p><p>exige que algumas tags básicas estejam presentes, como html, head, body,</p><p>dentro da estrutura head. Por exemplo, existem comandos para a formatação e</p><p>inserção de conteúdo, e o programador deve respeitar essa organização. Desse</p><p>modo, é possível analisar se as tags do código estão relacionadas corretamente.</p><p>A Figura 11 apresenta alguns elementos da linguagem HTML.</p><p>19Árvores: estruturas hierárquicas</p><p>Figura 11. Modelo de documento HTML.</p><p>Fonte: Adaptada de Devfuria (2012).</p><p>Document</p><p><html></p><p><head> <body></p><p><h1> <p></p><p>“This is a” “document”</p><p>“simple”</p><p><i></p><p><title></p><p>“Sample</p><p>Document”</p><p>“An HTML</p><p>Document”</p><p>Cada nível da árvore corresponde a um nível de aninhamento interno nas</p><p>tags. A primeira tag é <html>, todas as demais estão contidas nessa tag, e</p><p>essa mesma propriedade de aninhamento hierárquico vale para as demais tags.</p><p>Obviamente, existem outras tags, como para inserção de tabelas <table>,</p><p>inclusão de links <a link> e marcadores <li>. A intenção é demonstrar</p><p>a aplicabilidade usando algumas tags como exemplo.</p><p>Organização de diretórios</p><p>Outro exemplo prático de uso é a organização de um diretório de determinado</p><p>sistema operacional. Seja ele desktop ou mobile, os arquivos estão organizados</p><p>de forma hierárquica, conforme demonstra a Figura 12. Perceba que é fácil</p><p>determinar o caminho de um arquivo ou até mesmo verificar rapidamente a</p><p>existência de um arquivo.</p><p>Árvores: estruturas hierárquicas20</p><p>Figura 12. Organização de diretório em sistema operacional.</p><p>Fonte: Goodrich e Tamassia (2013, p. 286).</p><p>Este capítulo demonstrou o emprego de árvores em casos práticos, mas</p><p>os exemplos não foram esgotados. Ao realizar uma busca sobre uso de</p><p>árvores na área específica de computação gráfica, exemplos dessa estrutura</p><p>aplicada a jogos, para determinar os próximos movimentos dos personagens,</p><p>serão encontrados. Ao pesquisar pelo uso de árvores na área de minera-</p><p>ção de dados, aplicações para identificar quando uma transação bancária</p><p>pode ser uma fraude serão encontradas, entre outras. Assim, percebe-se a</p><p>abrangência desse tema e a importância de saber codificar essa estrutura</p><p>para a projeção de soluções, principalmente, na representação de situações</p><p>multi ou bidirecionais, facilitando a própria implementação e agilizando a</p><p>consulta de informações.</p><p>21Árvores: estruturas hierárquicas</p><p>ASCENCIO, A. F. G.; ARAUJO, G. S. Estrutura de dados: algoritmos, análise de complexidade</p><p>e implementações em Java e C/C++. São Paulo: Person, 2011.</p><p>BAKA, B. Python data structures and algorithms. Birmingham, UK: Packt, 2017.</p><p>CORMEN, T. H. et al. Algoritmos: teoria e prática. 3. ed. Rio</p><p>de Janeiro: Elsevier, 2012.</p><p>DEVFURIA. DOM — Document Object Model: O que você precisa saber sobre o DOM</p><p>(Document Object Model). 2012. Disponível em: http://www.devfuria.com.br/javascript/</p><p>dom/. Acesso em: 21 dez. 2019.</p><p>EDELWEISS N.; GALANTE, R. Estrutura de dados. Porto Alegre: Bookman, 2009.</p><p>GOODRICH, M. T.; TAMASSIA, R. Estruturas de dados e algoritmos em Java. 5. ed. Porto</p><p>Alegre: Bookman, 2013.</p><p>GOODRICH, M. T.; TAMASSIA, R.; GOLDWASSER M. H. Data structures and algorithms in</p><p>Python. Hoboken, NJ: Wiley, 2013.</p><p>TENENBAUM A. M.; LANGSAM Y., AUGENSTEIN M. J. Estruturas de dados usando C. São</p><p>Paulo: Person, 2010.</p><p>VEYRAT, P. Exemplo de estrutura organizacional de uma empresa: qual escolher? 24 maio</p><p>2017. Disponível em: https://www.heflo.com/pt-br/rh/exemplo-de-estrutura-organi-</p><p>zacional-de-uma-empresa/. Acesso em: 21 dez. 2019.</p><p>Os links para sites da Web fornecidos neste capítulo foram todos testados, e seu fun-</p><p>cionamento foi comprovado no momento da publicação do material. No entanto, a</p><p>rede é extremamente dinâmica; suas páginas estão constantemente mudando de</p><p>local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade</p><p>sobre qualidade, precisão ou integralidade das informações referidas em tais links.</p><p>Árvores: estruturas hierárquicas22</p><p>Dica do professor</p><p>Uma árvore é formada por um conjunto finito de elementos denominados vértices ou nós. Se não</p><p>existirem nós, a árvore está vazia, caso contrário, há um nó especial chamado raiz da árvore (r), e os</p><p>demais elementos restantes são particionados em conjuntos distintos não vazios, as subárvores de</p><p>r, sendo cada um desses conjuntos, por sua vez, uma árvore.</p><p>Uma estrutura é necessária para representar os nós e seus encadeamentos. Nesta Dica do</p><p>Professor, você vai conhecer detalhes sobre o tipo abstrado de dados para os nós de uma árvore.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/0beb15bff6678ab87cdedd14c99bfc7d</p><p>Exercícios</p><p>1) Alguns problemas requerem estruturas que possibilitem operações como inserção e</p><p>remoção de maneira dinâmica, tais como as árvores. Em relação às árvores e suas vantagens</p><p>em relação às demais estruturas, marque a alternativa correta.</p><p>A) A árvore é uma estrutura linear que permite representar uma relação hierárquica. Ela tem um</p><p>nó raiz e subárvores não vazias.</p><p>B) Árvores são consideradas eficientes para guardar informações, pois apresentam uma forma</p><p>de organização não linear.</p><p>C) As árvores são um tipo específico de estruturas em que os elementos só podem ser inseridos</p><p>e retirados de uma das extremidades.</p><p>D) As árvores utilizam o critério de fim de lista para armazenar os elementos, ou seja, o último</p><p>número inserido vai para o fim da lista.</p><p>E) As informações de uma árvore são armazenadas de forma contínua na memória, o que facilita</p><p>a busca.</p><p>2) Considere que você precisa utilizar uma árvore binária e o TAD deve ter um campo para</p><p>armazenar um número inteiro. Os nós podem ser representados na linguagem Python como</p><p>uma classe com os seguintes atributos básicos:</p><p>A) Número do nó, ponteiro para subárvore da direita e ponteiro para subárvore da esquerda.</p><p>B) Informação armazenada no nó, lista de filhos, e ponteiro para o pai.</p><p>C) String que será armazenada no nó, ponteiro subárvore da esquerda e lista de filhos.</p><p>D) Lista de dados do tipo inteiros, ponteiro para subárvore da direita e ponteiro para o pai.</p><p>E) Número do nó, ponteiro para subárvore da direita e ponteiro para o pai.</p><p>Durante a implementação de um TAD hierárquico, será necessário conhecer alguns termos para</p><p>projetar os métodos. Acerca das terminologias da estrutura de dados do tipo árvore, considere a</p><p>imagem a seguir e marque a alternativa correta:</p><p>3)</p><p>A) Os nós folhas são: D, G, C, H.</p><p>B) Pode-se dizer que o grau do nó C é 2.</p><p>C) O grau do nó E é 2.</p><p>D) A altura desta árvore é 2.</p><p>E) No segundo nível estão os nós B e C.</p><p>Dada a seguinte árvore e considerando as propriedades de armazenamento de uma árvore binária,</p><p>após a inserção do nó 9 e do nó 5, nessa ordem, pode-se afirmar que esses nós serão filhos dos</p><p>nós:</p><p>4)</p><p>A) 9 será filho da direita do nó 14, e 5 será filho da direita do nó 4.</p><p>B) 9 será filho da esquerda do nó 10 e 5 será filho da direita do nó 4.</p><p>C) 9 será filho da esquerda do nó 7 e 5 será filho da esquerda do nó 4.</p><p>D) 9 será filho da direita do nó 14 e 5 será filho da esquerda do nó 7.</p><p>E) 9 será filho da direita do nó 10 e 5 será filho da esquerda do nó 7.</p><p>5) Caso você tivesse que indicar uma estrutura de dados apropriada para armazenar uma</p><p>sequência de comandos HTML e verificar sua sintaxe antes de apresentar as informações no</p><p>browser, qual estrutura você indicaria?</p><p>A) Pilha</p><p>B) Fila</p><p>C) Tabela de dispersão</p><p>D) Grafo</p><p>E) Árvore</p><p>Na prática</p><p>Estruturas de dados do tipo árvores são importantes para organizar informações, permitindo</p><p>agilizar as consultas, bem como podem ser utilizadas em aplicações de diversas áreas.</p><p>Neste Na Prática, você verá o uso de árvores em um processo de decisão na área de inteligência</p><p>artificial, obtendo dados em um formato estruturado hierarquicamente, possibilitando auxiliar na</p><p>tomada de decisão de forma rápida e simplificada.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/b223b18a-73af-44e9-8bfa-305c0ddbae95/47775fa1-8034-4d9a-9a30-f15a5e913b17.png</p><p>Saiba +</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>Estruturas de Dados e Algoritmos em Java</p><p>Para se aprofundar mais em estrutura de dados, leia este livro, que apresenta o conteúdo</p><p>pertinente ao que foi estudado nesta Unidade de Aprendizagem.</p><p>Conteúdo interativo disponível na plataforma de ensino!</p><p>Site do professor Paulo Feofiloff</p><p>Acesse o site do professor Paulo Feofiloff, autor do livro Projeto de Algoritmos, e você irá encontrar</p><p>uma abordagem geral sobre árvores binárias.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Apresentação sobre árvores</p><p>Quer saber mais sobre relação de dependência de nós? Acesse o material disponibilizado por</p><p>Martins (2017) e veja exemplos sobre o assunto e demais termos relacionados as estruturas</p><p>hierárquicas.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.ime.usp.br/~pf/algoritmos/aulas/bint.html</p><p>https://pt.slideshare.net/cpmart/aula-08-rvores-76617076</p>