CMU 15-445 | Project #0 - C++ Primer

• 官网链接：https://15445.courses.cs.cmu.edu/fall2023/project0/
• 耗时：1 天

本节实验只是一道开胃菜，如果没有 C++ 基础建议先去其它地方学习一下。这部分主要就是实现了一个 Copy-On-Write Trie。虽然只是开胃，但还是把我小小地折磨了一下。

什么是 Trie

Trie 有时也称为前缀树或字典树，是一种用于存储具有相同前缀的字符串的树形数据结构，它能够高效地支持插入、查找和删除等操作。例如，在英文字符集中，每个节点可能有26个指针（对应a-z），指向它的子节点。在实际应用中，为了节省空间，一般只存储实际使用的字符对应的指针。

那 COW Trie 又是什么

Trie

本节实验要求实现一个 Copy-On-Write Trie，实际就是 Trie 树上的所有节点创建后都不可修改，如果需要进行增删修改，则需要重新创建相应的节点。官网上已经给了这个 COW Trie 操作的例子，我们需要注意一点：修改了某个节点，它对应的所有父节点也需要重新创建，因为重新创建了某个节点，它的父节点也需要修改子节点的信息，所以对这个 COW Trie 的增删操作每次都返回了一个新的根节点。

如何记录父节点？有点类似于 DFS，用一个栈就可以。

在代码中的具体体现就是：TrieNode 和 Trie 的方法和属性到处都有 const 修饰，意味着变量不能被修改。但是在树的构建过程中，时不时得修改父节点的 children_ 属性，所以就要用到 Clone() 这个方法，它可以返回 std::unique_ptr<TrieNode>，而且已经通过继承的方式将带值的节点正确复制。这样可以节省很多代码量，而不是手动一个一个进行复制和判断。