binary-search-tree: left() and right() return modifiable subtree
- 主要语言
- 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 还没有评估数据。