Changes

Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.

Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos particulares são árvores;

Até esse ponto, nós lidamos apenas com árvores sem raiz. Podemos usar o comando Maplespantree para mudar transformar uma árvore sem raiz em uma árvore com raiz. Ele faz isso atualizando os conjuntos de ancestrais e filhas (descendentes) para cada vértice, para refletir imitar a estrutura da spanning treeárvore de extensão.

Para usar o comando spantree, devemos selecionar o um vértice e formar uma spanning tree com árvore de extensão usando esse vértice como raiz, direcionando todas as arestas na da árvore em direção a raiz. (Estudaremos spanning trees árvores de extensão mais tarde nesse capítulo. Geralmente, o comando spantree pega um grafo conexo indireto G e um vértice v e constrói uma spanning tree árvore de extensão de G usando v como a raiz, direcionando todas as arestas em direção a v.) Por exemplo, podemos transformar a árvore T1 em uma árvore com raiz, tomando a como sua raiz e utilizando o comando:

Agora representamos apresentaremos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-código:

1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até que não haverem hajam mais ancestrais (ex: quando atingimos o vértice raiz).

2. Para achar todos os descendentes, usamos o comando daughter repetidamente até que não haverem hajam mais descendentes(ex: quando todas as folhas de um vértice forem atingidas).

Uma implementação desse procedure é como a se dá da seguintemaneira:

Agora iremos construir uma árvore mais largamaior, chamada T3 que é a árvore mostrada na Página 5433 do texto, e então iremos executar o novo procedure criado em um de seus vértices.

Os descentendes descendentes do vértice B são obtidos pelo comando:

A seguir, determinamos o conjunto de vértices internos (galhos) e folhas de uma árvore com raiz. Lembre-se que um v é um vértice interno de uma árvore com raiz se v tiver filhos, e que v é o vértice folha de uma árvore com raiz se v não tiver filhos. Em outras palavras, em qualquer árvore com raiz não trivial (ex:.uma árvore com raiz que é mais do que apenas um vértice raiz), as folhas são essas com gráu de vértice grau 1, e os vértices internos são vértices com grau maior que 1.

Agora iremos discutir como encontrar o maior número de filhos de um vértice interno de uma árvore com raiz. Lembre-se que se m é esse número, a árvore é chamada de árvore m-ária. Também iremos descrever como determinar se uma árvore m-ária é balanceadobalanceada. Lembre-se que uma árvore é balanceada se todas as folhas estão no nível h ou h-1 se , sendo essa uma árvore tem com um total de h níveis, onde o nível do vértice é a distância do caminho único from da raiz até tal vértice.

Para utilizar o Maple para determinar se uma árvore é uma árvore m-ária, podemos simplesmente olhar a sequencia sequência de graus do vértice, tomando em conta que para todos os vértices exceto a raiz, o grau de tal vértice é um a mais que o número de descendentes. Isso pode ser feito usando o comando vdegree no Maple. Para determinar se uma árvore é balanceada, podemos usar a estrutura de armazenamento interno de uma árvore em no Maple. Iremos utilizar do fato de que o Maple armazena o nível do vértice em uma árvore como o peso do vértice para esse vérticeele mesmo. Por exemplo, se v é um vértice que está no nível 3 de uma árvore, então podemos extrair essa informação usando o comando vweight no vértice v.

Esaa Essa técnica é formalizade formalizada pelo seguinte procedure no Maple:

Agora iremos utilizar o procedure ArityBalanced para verificar a fórmula na página 541 do texto para árvore árvores m-árias cheias. Isto é, iremos construir um procedure para computar o número de vértices internos e folhas de dada árvore m-ária, e comparar essas quantidades como esboçado no teorema 3 e teorema 4 da página 541 do texto. O procedure chamado TheoremVerify utilizará:

Se o vértice não houverem tiver filhos do vértice, ele é uma folha

Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária (ternária) completa.

Essa sessão foca no uso de árvores em árvores binárias de busca binárias. Especificamente, chamamos o uso de árvores em algoritmos de busca binária assim como o uso de árvores em código no algoritmo de Huffman. A razão pela qual desejamos usar árvores binárias é de que podemos usar a binary estrutura binária da árvore para tomar decisões binárias(ex: true/false) quanto a inserção ou procura de caminhos.