exercism / exercism/cpp

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

未关闭
#264 6 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
C++
星标
290
派生
244
PR 合并指标
30 天内没有已合并 PR

描述

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:
```cpp
template
using tree_ptr = typename std::unique_ptr>;

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

//...

test_leaf(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` means that the `unique_ptr` itself is `const`, not the object it points to.

Somebody could take the example implementation (`example.h`) and write
```cpp
auto tree = binary_tree::binary_tree(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.

贡献指南

这个仓库没有索引到贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。