CMU15-445 bustub Project0：Trie 树实现

实验环境是在阿里云的云服务器上配置的，推荐使用该方式，方便快捷，就不在此赘述了

Project0主要是考察Modern C++编程基础，难度不大，2022fall的目标是实现一个字典树(Trie);

字典树(Trie)

字典树(Trie)是一种树形数据结构，用于高效地存储和检索字符串数据集中的键(高效地进行前缀匹配)。Trie 的本质是一个多叉树，每个节点有多个孩子，每个孩子对应一个字符，每个节点有一个布尔值表示当前节点是否是一个单词的结尾。
例如插入两个键值对 (“ab”, 1) 和 (“ac”, “val”)，则形成下图的结构：
Trie
root 是根节点，不存储键；a 是一个非终结节点，只存储键；下层的两个节点是终结节点，除了键还要存储一个任意类型的值。每个节点有一个 map 存储以每个子节点的键索引的子节点。

在该项目中，主要有三个类：

TrieNode: 表示非终结节点，成员为键，是否是终结节点的标记，子节点 map

TrieNode:
  /** Key character of this trie node */
  char key_char_;
  /** whether this node marks the end of a key */
  bool is_end_{false};
  /** A map of all child nodes of this trie node, which can be accessed by each
   * child node's key char. */
  std::unordered_map<char, std::unique_ptr<TrieNode>> children_;

TrieNodeWithValue: 表示终结节点，继承自TrieNode，表示终结节点，带有一个 T 类型的 value
Trie: 表示整个 Trie 树

Trie:
  /* Root node of the trie */
  std::unique_ptr<TrieNode> root_;
  /* Read-write lock for the trie */
  ReaderWriterLatch latch_;

TrieNode 实现

TrieNode 构造函数

/**
   * TODO(P0): Add implementation
   *
   * @brief Construct a new Trie Node object with the given key char.
   * is_end_ flag should be initialized to false in this constructor.
   *
   * @param key_char Key character of this trie node
   */
  explicit TrieNode(char key_char) {
    this->key_char_ = key_char;
    this->is_end_ = false;
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Move constructor for trie node object. The unique pointers stored
   * in children_ should be moved from other_trie_node to new trie node.
   *
   * @param other_trie_node Old trie node.
   */
  TrieNode(TrieNode &&other_trie_node) noexcept {
    this->key_char_ = other_trie_node.key_char_;
    this->is_end_ = other_trie_node.is_end_;
    this->children_ = std::move(other_trie_node.children_);  // this?
  }

需要注意的是移动构造函数（move constructor），由于 unique_ptr 表示独占性资源，没有拷贝构造函数，所以这里我们要用 std::move。

TrieNode 成员函数

std::unique_ptr<TrieNode> *InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) {
  if (children_.find(key_char) != children_.end()) {
    return nullptr;
  }
  if (child->key_char_ != key_char) {
    return nullptr;
  }
  children_[key_char] = std::move(child);
  return &children_[key_char];
}


std::unique_ptr<TrieNode> *GetChildNode(char key_char) {
  if (children_.find(key_char) != children_.end()) {
    return &children_[key_char];
  }
  return nullptr;
}

大多数成员函数的实现都很简单，只是注意在InsertChildNode()与GetChildNode()中，因为 unique_ptr 是独占性指针不能拷贝，返回值是 unique_ptr 的指针。

TrieNodeWithValue 实现

// Construct a new TrieNodeWithValue
TrieNodeWithValue(char key_char, T value) : TrieNode(key_char), value_(value) { is_end_ = true; }
// Construct a new TrieNodeWithValue object from a TrieNode object and specify its value.
TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::move(trieNode)), value_(value) { is_end_ = true; }

该类的is_end_始终为true

Trie 实现

1	Trie() { root_ = std::make_unique<TrieNode>('\0'); }

构造函数，根节点不携带键

Insert()
沿 Trie 树搜索到键的最后一个字符，过程中如果节点不存在就创建。对于最后一个键的字符分三种情况：

如果相应节点不存在，创建一个终结节点 TrieNodeWithValue，插入成功；
如果相应节点存在但不是终结节点（通过 is_end_ 判断），将其转化为 TrieNodeWithValue 并把值赋给该节点，该操作不破坏以该键为前缀的后续其它节点（children_ 不变），插入成功；
如果相应节点存在且是终结节点，说明该键在 Trie 树存在，规定不能覆盖已存在的值，返回插入失败。

template <typename T>
  bool Insert(const std::string &key, T value) {
    latch_.WLock();
    if (key.empty()) {
      latch_.WUnlock();
      return false;
    }
    auto current = &root_;
    size_t i = 0;
    // 找，找不到就新建，只到key的倒数第二个字符
    while (i + 1 < key.size()) {
      if ((*current)->GetChildNode(key[i]) == nullptr) {
        std::unique_ptr<TrieNode> tmp = std::make_unique<TrieNode>(key[i]);
        (*current)->InsertChildNode(key[i], std::move(tmp));
      }
      current = (*current)->GetChildNode(key[i]);
      i++;
    }
    // 第一种情况，末尾结点不存在
    if ((*current)->GetChildNode(key[i]) == nullptr) {
      std::unique_ptr<TrieNodeWithValue<T>> tmp = std::make_unique<TrieNodeWithValue<T>>(key[i], value);
      (*current)->InsertChildNode(key[i], std::move(tmp));
      latch_.WUnlock();
      return true;
    }
    // 第二种情况，将普通结点转化为带value的结点
    current = (*current)->GetChildNode(key[i]);
    if (!(*current)->IsEndNode()) {
      auto *tmp = new TrieNodeWithValue<T>(std::move(*(*current)), value);
      current->reset(tmp);
      latch_.WUnlock();
      return true;
    }
    // 第三种情况
    latch_.WUnlock();
    return false;
  }

Remove()

递归地沿 Trie 树逐字符向下搜索给定键，如果中途发现不存在直接返回 false。
如果找到了，则将该节点的 is_end_ 标为 false（此时虽然其值仍存在，但会被我们视为非终结节点）。如果该节点没有子节点，则可以删除。
递归回溯，如果其 parent 节点在移除该子节点后没有其它子节点并且不是终结节点，也删除。

bool Remove(const std::string &key) {
  latch_.WLock();
  if (key.empty()) {
    latch_.WUnlock();
    return false;
  }
  auto cur = &root_;
  bool success = false;
  RemoveInner(key, 0, cur, &success);
  latch_.WUnlock();
  return success;
}
bool RemoveInner(const std::string &key, size_t i, std::unique_ptr<TrieNode> *cur, bool *success) {
  if (i == key.size()) {
    *success = true;
    (*cur)->SetEndNode(false);
    return !(*cur)->HasChildren();
  }
  if ((*cur)->GetChildNode(key[i]) == nullptr) {
    *success = false;
    return false;
  }
  bool can_remove = RemoveInner(key, i + 1, (*cur)->GetChildNode(key[i]), success);
  if (!*success) {
    return false;
  }
  if (can_remove) {
    (*cur)->RemoveChildNode(key[i]);
  }
  return !(*cur)->HasChildren() && !(*cur)->IsEndNode();
}

GetValue

沿 Trie 树查找，如果键不存在，或者节点中存储的值类型与函数调用的类型 T 不一致，将 *success 标识设为 false。
类型判断的方式是使用 dynamic_cast。

template <typename T>
  T GetValue(const std::string &key, bool *success) {
    // *success = false;
    // return {};
    latch_.RLock();
    if (key.empty()) {
      *success = false;
      latch_.RUnlock();
      return {};
    }
    auto cur = &root_;
    for (auto &c : key) {
      if (!(*cur)->HasChild(c)) {
        *success = false;
        latch_.RUnlock();
        return {};
      }
      cur = (*cur)->GetChildNode(c);
    }
    auto ret_value = dynamic_cast<TrieNodeWithValue<T> *>(cur->get());
    if (ret_value == nullptr) {
      *success = false;
      latch_.RUnlock();
      return {};
    }
    *success = true;
    latch_.RUnlock();
    return ret_value->GetValue();
  }
};

测试

1
2
3

cd build
make starter_trie_test
./test/starter_trie_test

代码格式化

1
2
3

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