0%
Pular para o conteúdo principal
0%

2.3.3 Exemplo: Representando Conjuntos

Nesta seção, examinamos maneiras de usar listas para representar conjuntos. Um conjunto é uma coleção de objetos distintos. Para dar uma definição mais precisa, podemos empregar o método de abstração de dados: Definimos um conjunto especificando as operações que serão usadas em conjuntos.

Operações em Conjuntos​

As operações básicas incluem:

  • is_element_of_set(x, set) - testa se x é membro do conjunto
  • adjoin_set(x, set) - adiciona x ao conjunto
  • union_set(set1, set2) - retorna a união de dois conjuntos
  • intersection_set(set1, set2) - retorna a interseção de dois conjuntos

Conjuntos como Listas Não Ordenadas​

Carregando playground de código...

Complexidade: is_element_of_set requer O(n) passos. intersection_set requer O(n²) passos.

Conjuntos como Listas Ordenadas​

Podemos acelerar as operações organizando os elementos do conjunto em ordem crescente:

Carregando playground de código...

Complexidade: intersection_set agora requer apenas O(n) passos.

Conjuntos como Árvores Binárias​

Podemos fazer melhor usando uma árvore binária. Cada nó contém um elemento e dois ramos. Todos os elementos no ramo esquerdo são menores que o elemento no nó, e todos os elementos no ramo direito são maiores.

Carregando playground de código...

Complexidade: Para uma árvore balanceada, operações requerem O(log n) passos. No pior caso (árvore desbalanceada), requer O(n).

Exercícios​

Exercício 2.59: Implemente a operação union_set para a representação de conjunto como lista não ordenada.

Exercício 2.60: Especifique implementações das funções se permitirmos duplicatas. Como isso afeta a eficiência?

Exercício 2.61: Implemente adjoin_set para listas ordenadas.

Exercício 2.62: Implemente union_set para listas ordenadas em tempo O(n).

Exercício 2.63: Cada uma das duas funções seguintes converte uma árvore binária em uma lista. Elas produzem o mesmo resultado? Elas têm a mesma ordem de crescimento?

Exercício 2.64: A função list_to_tree converte uma lista ordenada em uma árvore binária balanceada. Explique como funciona.

Exercício 2.65: Use os resultados dos exercícios anteriores para dar implementações O(n) de union_set e intersection_set para conjuntos implementados como árvores binárias (balanceadas).

Exercício 2.66: Implemente a função lookup para um banco de dados implementado como uma árvore binária, ordenada pela chave numérica.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

  • Erro de tradução (palavra incorreta, termo técnico errado)
  • Erro de ortografia ou gramática
  • Link quebrado
  • Código de exemplo que não funciona
  • Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

  • Dúvida sobre o conteúdo desta seção
  • Pergunta sobre um conceito do SICP
  • Dificuldade em entender algum exemplo
  • Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

  • Melhoria na explicação
  • Exemplo adicional
  • Recurso visual (diagrama, ilustração)
  • Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

  • Escolha de tradução de algum termo
  • Consistência de terminologia
  • Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨