Estrutura De Dados

01. A probabilidade p de se inserir N itens consecutivos sem colisão em uma tabela de tamanho M é:

p = M! / (((M-N)!) * (M^N));

Aplicando isto ao Paradoxo do Aniversário, temos:

p = 365! / (342!)* (365^23);

p ≈ 0,49;

Logo a probabilidade de haver colisões é igual a p = 1 – 0,49 = 0,51 ou 51%;

O paradoxo do aniversário é um exemplo da probabilidade de ocorrência de colisões em uma função hash.

02.

03. I. A principal propriedade é que para todo nó da árvore, o conteúdo dos nós pertencentes a sub-árvore esquerda é menor ou igual ao conteúdo da raiz e o conteúdo dos nós pertencentes a sub-árvore direita é maior ou igual ao conteúdo da raiz.

Outra propriedade é que se fizermos uma varredura ‘erd’, os conteúdos da árvore serão impressos em ordem crescente.

II. Se a diferença da altura da sub-árvore esquerda com a sub-árvore direita da raiz de uma árvore é no máximo uma unidade, dizemos que esta árvore está balanceada.

04. Árvore B: todo nó possui ‘n’ chaves que são armazenadas em ordem crescente e folha que indica se o nó é uma folha ou um nó interno. Se for um nó interno, este terá ‘n+1’ ponteiros para seus filhos. E todas as folhas estão na mesma altura.

Árvore B+: é uma variação da árvore B que mantém todas as chaves de busca em seus nós folha de maneira que o acesso sequencial ordenado das chaves de busca seja mais eficiente que na árvore B.

Árvore Rubro-Negra: cada nó possui um bit que indica sua cor(Vermelho ou Preto), a raiz é preta, todas as folhas(fictícias) são pretas, se um nó é vermelho todos seus filhos são pretos e para cada nó, todos os caminhos dos nós até suas folhas contém o mesmo número de nós pretos.