24

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.230

Passo 1 de 8keyboard_arrow_downkeyboard_arrow_up

Nas estruturas simples de árvores de dados usam em suas principais operações, como insert, delete, etc. Essa função é utilizada em todos os casos. Assim parece impossível implementar uma fila de prioridade baseado em comparação de chaves com todas operações em . Porém existem algoritmos que ordenam n números em , aproveitando o fato que as chaves são números com k bits ou aproveitando que as chaves possuem um domínio limitado.

Passo 2 de 8keyboard_arrow_downkeyboard_arrow_up

Uma árvore de Van Emde Boas usa abordagem de endereçamento direto para armazenar os valores de chave na mesma. Um exemplo de uma árvore de Van Emde Boas seria como:

0

0

0

1

0

0

1

0

1

1

0

0

1

1

1

1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Passo 3 de 8keyboard_arrow_downkeyboard_arrow_up

A árvore de Van Emde Boas já é mais eficiente na memória de poupança do que qualquer outra estrutura de árvore de auto-equilíbrio. No entanto, isso pode ser feito mais eficiente em termos de velocidade de busca também por sobreposição de uma árvore binária na parte superior do mesmo. Isto pode ser alcançado através da criação de uma árvore binária que contém um 1 no seu nó, se qualquer um dos seus filhos tem um valor em cada um deles, 0, caso contrário. A criação começa a partir de baixo para cima. Dois índices consecutivos da matriz de bits são verificados para a criação de um nó da árvore binária. Se qualquer um desses valores é o valor 1 no nó da árvore for binário tem-se 1; 0 caso contrário.

Passo 4 de 8keyboard_arrow_downkeyboard_arrow_up

A árvore ficaria, então, da seguinte forma:

C:\Users\Renato\Dropbox\Renato (1)\Exercícios para Resolver\algoritmos\Imagens do Chegg\IMG_0100.PNG

Passo 5 de 8keyboard_arrow_downkeyboard_arrow_up

A figura mostra a árvore de Van Emde Boas com uma árvore binária sobreposta. Se algum dos índices consecutivos ou ambos tiverem um 1, então o valor do nó da árvore é um binário como no caso do índice de 2 e 3. Logicamente pela árvore de nós armazena o espaço lógico de suas linhas abaixo. Observando a estrutura acima, pode ser visto que as estruturas de árvore são de auto-equilíbrio, como esta estrutura não é para armazenar os valores duplicados. Os valores duplicados podem ser simplesmente ignorados ao inserir os valores na árvore Van Emde Boas.

Passo 6 de 8keyboard_arrow_downkeyboard_arrow_up

A árvore de Van Emde Boas não suporta chaves duplicadas. A razão é a estrutura de armazenamento da árvore. A árvore armazena uma matriz de bits que pode conter apenas um 1 ou 0. As chaves não estão fisicamente armazenadas na árvore em vez os índices de matriz são considerados como sendo o valor da chave. Onde quer que a chave estiver presente, o correspondente índice é definido como 1. Se a chave não está presente o índice é deixado 0.

Passo 7 de 8keyboard_arrow_downkeyboard_arrow_up

A fim de fazer a árvore de suportar as chaves duplicadas, seria necessária a mudança na estrutura de armazenamento da árvore. A razão é que o valor binário só pode indicar a presença ou ausência dos dados. Na estrutura de armazenamento da matriz de bits a alteração pode ser executada conforme especificado adiante. Ao executar as mudanças que devem ser tomados cuidados de se a mudança na matriz de bits é fazer quaisquer alterações nos níveis superiores da estrutura como a árvore binária sobreposta. Para permitir a duplicação, a pequena modificação nas folhas seria suficiente. Na árvore comum, existe um conjunto de dados um bit que está armazenado para demonstrar se os dados são mantidos na posição determinada. Para a duplicação, um número inteiro pode ser mantido em seu lugar. Inicialmente todos os índices seria configurado para 0. Agora, sempre que a chave é encontrada, o correspondente índice seria incrementado de 1. Este pode ser mostrado como abaixo:

C:\Users\Renato\Dropbox\Renato (1)\Exercícios para Resolver\algoritmos\Imagens do Chegg\IMG_0102.PNG

Passo 8 de 8keyboard_arrow_downkeyboard_arrow_up

Agora, a modificação não deve fazer qualquer impacto sobre o restante da estrutura de dados. Isto torna-se mais importante quando a estrutura é sobreposta aumentando uma árvore binária. Um valor diferente de zero pode simplesmente ser considerado como sendo um número inteiro positivo, no caso da estrutura em árvore modificada. Assim, a duplicação pode ser permitida pela representação da frequência de ocorrência do valor da chave em vez de mostrar se os dados estão lá ou não. Os nós de árvore binária sobreposta teriam um 1 neles se qualquer um dos ramos abaixo tem um valor diferente de 0; e 0, caso contrário.

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.