实验P0

实验零要求实现一个数据结构：前缀树。适合复习CPP以及适应实验代码环境。

前言

实现前缀树，实际上是实现一种特殊情况的kv存储，key为字符串，value为任意类型。

<"abcd", 1>
<"abc", 2>
<"abce", 3>
<"a", 1>

有三个类：

• Trie 字典树
• TrieNode 字典树节点类
• TrieNodeWithValue 继承自TrieNode，表示一个key的结尾并存储value

可以很简单地想到每个节点类存储一个字符以及对应的子节点指针的集合。

注意：前缀树的叶子结点必然对应一个value存储，同时内部节点也可能对应一个value存储。

TrieNodeWith Value可以出现在树的任何地方，比如插入a，插入aa，插入aaa，此时树中三个结点均为TrieNodeWithValue类型。

查找思路：

• key与前缀树的遍历二者同时进行，key的每个位置上的char指导当前节点往下走。
• 当走到最后一个char时，需要检查是否是end node。

删除思路：

• 遍历到最后一个char，中间有任何问题（结点不存在）直接返回false
• 将最后一个char对应的结点的is_end设置为false
• 往上回溯遍历的结点，对每个回溯的节点进行判断
  • 如果这个结点没有child并且不是end node，那么可以安全删除

踩坑

本地测试，请去除DISABLED前缀。

网页测评前，代码格式检测：

$ make format
$ make check-lint
$ make check-clang-tidy-p0

提交文件制作，需要包括完整路径：

zip -r p0.zip src/include/primer/p0_trie.h

TrieNode Insert测试

提交时TrieNode Insert测试没有通过，只有70分。

template <typename T>
bool Insert(const std::string &key, T value) {
  if (key.empty()) {
    return false;
  }

  latch_.WLock();
  auto *node = &root_;
  for (char key_char : key) {
    auto node_next = (*node)->GetChildNode(key_char);
    if (node_next == nullptr) {
      node_next = (*node)->InsertChildNode(key_char, std::make_unique<TrieNode>(key_char));
    }
    node = node_next;
  }

  if ((*node)->IsEndNode()) {
    latch_.WUnlock();
    return false;
  }

  // error implementation of convert TrieNode to TrieNodeWithValue
  //     char ch = (*node)->GetKeyChar();
  //     node->reset(new TrieNodeWithValue<T>(ch, value));

  auto *new_node = new TrieNodeWithValue(std::move(**node), value);
  node->reset(new_node);

  latch_.WUnlock();

  LOG_DEBUG("insert into key %s, success", key.c_str());
  return true;
}

主要错误：将TrieNode转换为TrieNodeValues时，丢失了子孙信息。