ERRATA: No vídeo eu afirmo que o algoritmo de inserção apresentado garante que não haverão chaves repetidas na estrutura. Enretanto, isto não é verdade em todos os casos. Considere o seguinte contra-exemplo: vamos supor que estamos inserindo a chave x=43 após apagar a chave x=44 e que a chave x=44 está na posição de colisão C com a chave x=43. Também considere que a chave x=43 já estava ocupando o posição C+1. Como o estado da posição C é APAGADO o algoritmo simplesmente insere x=43 na posição C, mesmo que x=43 já esteja ocupando a posição C+1, uma vez que a posição C é avaliada antes da posição C+1. Para resolver este problema podemos fazer uma busca na tabela para verificar se a chave x já está na tabela. Caso esteja, apenas o valor é modificado. Isto pode ser feito de forma eficiente uma vez que a busca retorna a posição na tabela que x ocupa. Caso x não esteja na tabela, basta inserir o elemento conforme o algoritmo apresentado no vídeo. Considerando que o tempo da busca e da inserção apresentada no vídeo são constantes, o custo do algoritmo de inserção proposto aqui permanece constante.
Muito obrigado pelo trabalho!
aula incrível, obrigado!
Ótima aula!
Muito bom! Muito obrigado.
ERRATA:
No vídeo eu afirmo que o algoritmo de inserção apresentado garante que não haverão chaves repetidas na estrutura. Enretanto, isto não é verdade em todos os casos. Considere o seguinte contra-exemplo: vamos supor que estamos inserindo a chave x=43 após apagar a chave x=44 e que a chave x=44 está na posição de colisão C com a chave x=43. Também considere que a chave x=43 já estava ocupando o posição C+1. Como o estado da posição C é APAGADO o algoritmo simplesmente insere x=43 na posição C, mesmo que x=43 já esteja ocupando a posição C+1, uma vez que a posição C é avaliada antes da posição C+1.
Para resolver este problema podemos fazer uma busca na tabela para verificar se a chave x já está na tabela. Caso esteja, apenas o valor é modificado. Isto pode ser feito de forma eficiente uma vez que a busca retorna a posição na tabela que x ocupa. Caso x não esteja na tabela, basta inserir o elemento conforme o algoritmo apresentado no vídeo. Considerando que o tempo da busca e da inserção apresentada no vídeo são constantes, o custo do algoritmo de inserção proposto aqui permanece constante.