Hacktoberfest 2026: as issues que os mantenedores marcaram para outubro, abertas e boas para iniciantes. Ver issues do Hacktoberfest

binary-search-tree: left() and right() return modifiable subtree

Aberta
#264 6 comentários 1 reação 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
5/5
Tempo estimado
Mais de uma semana
Facilidade para iniciantes
25/100
Tipo de issue
Bug
Clareza
Precisa de esclarecimento
Status de atividade
Estagnada
Stack de tecnologia
cpp
Domínio
backend

Direção de pesquisa

Comece pelo exercício de binary-search-tree e inspecione example.h, concentrando-se em binary_tree::left(), binary_tree::right() e insert(). Compare o ownership e a constness deles com os testes atuais mostrados na issue. Está concluído quando o exemplo e os testes concordarem com uma API de subárvore const-safe que não possa invalidar o invariante da árvore.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

In the exercise "binary-search-tree" the methods left() and right() are hard to implement correctly. The example implementation itself is IMHO incorrect.

The tests look like this:

template<typename T>
using tree_ptr = typename std::unique_ptr<binary_tree::binary_tree<T>>;

template<typename T>
static void test_leaf(const tree_ptr<T> &tree, const T& data, bool has_left, bool has_right)

//...

test_leaf<uint32_t>(tested->left(), 2, false, false);

That forces implementations of binary_tree::left() (and binary_tree::right()) to return a tree_ptr reference or rvaue which points to a non-const subtree.
Remember: const std::unique_ptr<some_type> means that the unique_ptr itself is const, not the object it points to.

Somebody could take the example implementation (example.h) and write

auto tree = binary_tree::binary_tree<int>(100);
tree.insert(50);
tree.left()->insert(150);

and thus invalidate the invariant of tree.

I consider any implementation of a binary search tree that can be corrupted that way as faulty. I came up with three alternatives that avoid this issue and pass the current tests:

  • binary_tree could have a member variable allow_insert that is true for the root and false for all subtrees
  • binary_tree could have a parent pointer and insert() could check for each of its parents if the new value violates that parent's invariant
  • left() and right() could copy the subtree and return a unique_ptr to that copy.

But IMHO none of those alternatives feels right.

The easiest solution would be if left() and right() could return const raw pointers. But one could argue that raw pointers result in unclear ownership.

Linguagem predominante
C++
Estrelas
291
Forks
244
Merge médio
17min
PRs com merge (30d)
1

Guia de contribuição

Nenhum guia de contribuição indexado para este repositório

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de exercism/cpp

Todas as issues de exercism/cpp

Issues semelhantes

Mais issues de C++

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.