如何处理C++中Trie实现中的所有删除操作

huangapple
go评论107阅读模式
英文:

How to deal with all deletes in Trie Implementation in C++

问题

  1. 结构 Trie {
  2.     结构 TrieNode {
  3.         布尔 isEnd;
  4.         数组 <TrieNode*， 26> 孩子;
  5.         TrieNode() : isEnd(false), 孩子{} {}
  6.         布尔 isEmpty() {
  7.             对于 (整数 i = 0; i < 26; i++) {
  8.                 如果 (这->孩子[i] != nullptr) {
  9.                     返回 假;
  10.                 }
  11.             }
  12.             返回 真;
  13.         }
  14.     };
  15.     TrieNode* 根;
  16.     Trie () {
  17.         根 = 新 TrieNode();
  18.     }
  19.     穿插 (字符串 &word) {
  20.         TrieNode* 当前 = 根;
  21.         对于 (整数 i = 0; i < word.length(); i++) {
  22.             整数 idx = word[i] - 'a';
  23.             如果 (当前->孩子[idx] == nullptr) {
  24.                 当前->孩子[idx] = 新 TrieNode();
  25.             }
  26.             当前 = 当前->孩子[idx];
  27.         }
  28.         当前->isEnd = 真;
  29.     }
  30.     布尔 isPre (字符串 &word, 整数 类型) { // 类型 0 : isPresent, 类型 1: isPrefix
  31.         TrieNode* 当前 = 根;
  32.         对于 (整数 i = 0; i < word.length(); i++) {
  33.             整数 idx = word[i] - 'a';
  34.             如果 (当前->孩子[idx] == nullptr) {
  35.                 返回 假;
  36.             }
  37.             当前 = 当前->孩子[idx];
  38.         }
  39.         返回 (类型 ? 真 : 当前->isEnd);
  40.     }
  41.     TrieNode* 擦除 (TrieNode* 当前, 字符串 &word, 整数 i) {
  42.         如果 (当前 == nullptr) {
  43.             返回 nullptr;
  44.         }
  45.         如果 (i == word.length()) {
  46.             当前->isEnd = 假;
  47.             如果 (当前->isEmpty()) {
  48.                 删除 当前;
  49.                 当前 = nullptr;
  50.             }
  51.             返回 当前;
  52.         }
  53.         整数 idx = word[i] - 'a';
  54.         当前->孩子[idx] = 擦除(当前->孩子[idx], word, i + 1);
  55.         如果 (当前->isEnd == 假 && 当前->isEmpty()) {
  56.             删除 当前;
  57.             当前 = nullptr;
  58.         }
  59.         返回 当前;
  60.     }
  61. };

Note: The translation provided here is based on the code snippet you provided. If you encounter any issues or need further assistance, feel free to ask.

英文: 
  1. struct Trie {
  2. struct TrieNode {
  3. bool isEnd;
  4. array&lt;TrieNode*, 26&gt; child;
  5. TrieNode() : isEnd(false), child{} {}
  6. bool isEmpty() {
  7. for (int i = 0; i &lt; 26; i++) {
  8. if (this-&gt;child[i] != nullptr) {
  9. return false;
  10. }
  11. }
  12. return true;
  13. }
  14. };
  15. TrieNode* root;
  16. Trie () {
  17. root = new TrieNode();
  18. }
  19. void insert (string &amp;word) {
  20. TrieNode* curr = root;
  21. for (int i = 0; i &lt; word.length(); i++) {
  22. int idx = word[i] - &#39;a&#39;;
  23. if (curr-&gt;child[idx] == nullptr) {
  24. curr-&gt;child[idx] = new TrieNode();
  25. }
  26. curr = curr-&gt;child[idx];
  27. }
  28. curr-&gt;isEnd = true;
  29. }
  30. bool isPre (string &amp;word, int type) { // type 0 : isPresent, type 1: isPrefix
  31. TrieNode* curr = root;
  32. for (int i = 0; i &lt; word.length(); i++) {
  33. int idx = word[i] - &#39;a&#39;;
  34. if (curr-&gt;child[idx] == nullptr) {
  35. return false;
  36. }
  37. curr = curr-&gt;child[idx];
  38. }
  39. return (type ? true : curr-&gt;isEnd);
  40. }
  41. TrieNode* erase (TrieNode* curr, string &amp;word, int i) {
  42. if (curr == nullptr) {
  43. return nullptr;
  44. }
  45. if (i == word.length()) {
  46. curr-&gt;isEnd = false;
  47. if (curr-&gt;isEmpty()) {
  48. delete curr;
  49. curr = nullptr;
  50. }
  51. return curr;
  52. }
  53. int idx = word[i] - &#39;a&#39;;
  54. curr-&gt;child[idx] = erase(curr-&gt;child[idx], word, i + 1);
  55. if (curr-&gt;isEnd == false &amp;&amp; curr-&gt;isEmpty()) {
  56. delete curr;
  57. curr = nullptr;
  58. }
  59. return curr;
  60. }
  61. };

I implemented the following code, but the issue is with the erase function. Specifically, say I insert two elements in the trie and then remove both. Then the isPre() function stops working. I guess when I call the erase to delete the entire trie, it deletes the original root, which is then accessed, and thus the issue.

But I am not sure how to resolve it. I tried adding a nullptr check at the start of the isPre() function but even then, I get the error.

Except for the case where I delete all the trie's nodes after inserting them, the trie is working fine (even when I have not inserted anything).

Minimal Reproducible example:

  1. /* Trie Struct */
  2. string str = &quot;a&quot;;
  3. Trie trie;
  4. cout &lt;&lt; trie.isPre(str, 0); // Working Fine
  5. trie.insert(str);
  6. cout &lt;&lt; trie.isPre(str, 0); // Working Fine
  7. trie.erase(trie.root, str, 0);
  8. cout &lt;&lt; trie.isPre(str, 0); // Creates the Error

Error:

  1. ==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x611000000350 at pc 0x00000034e11e bp 0x7ffdd3c379e0 sp 0x7ffdd3c379d8
  2. READ of size 8 at 0x611000000350 thread T0

Edit:
As, I had suspected the error was caused due to the root node being delete. So, I just added a condition that root shouldn't be deleted. It worked fine. Here is the implementation. But, I am not sure if this is the way to go, I would be glad if anyone can suggest a better trie implementation

答案1

得分: 1

代码中的问题是在根节点上执行了delete操作，这是不应该发生的。一个快速修复方法是只有在i > 0时才执行delete。或者，您可以只在子节点（在递归树中向上一级）上执行delete操作，这样目标永远不会是根节点。这还意味着您不需要返回值是一个节点指针，而可以使用返回值来指示成功（如果找到了单词）或失败（没有要删除的内容）：

  1.     // 现在假定 curr 永远不会是 nullptr
  2.     bool erase (TrieNode* curr, string &word, int i) {
  3.         if (i == word.length()) {
  4.             bool success = curr->isEnd;
  5.             curr->isEnd = false;
  6.             return success;
  7.         }
  8.         int idx = word[i] - 'a';
  9.         TrieNode* child = curr->child[idx];
  10.         bool success = child && erase(child, word, i + 1);
  11.         if (success && !child->isEnd && child->isEmpty()) {
  12.             delete child;
  13.             curr->child[idx] = nullptr;
  14.         }
  15.         return success;
  16.     }
英文:

Indeed your code performs a delete on the root node, which should never happen. A quick fix is to only perform the delete when i &gt; 0. Alternatively you could only perform a delete on a child (one level up in the recursion tree) -- that way the target will never be the root. This also means you don't need the return value to be a node pointer, and can instead use the return value to indicate success (if the word was found) or failure (nothing to delete):

  1.     // Now curr is assumed to never be nullptr
  2. bool erase (TrieNode* curr, string &amp;word, int i) {
  3. if (i == word.length()) {
  4. bool success = curr-&gt;isEnd;
  5. curr-&gt;isEnd = false;
  6. return success;
  7. }
  8. int idx = word[i] - &#39;a&#39;;
  9. TrieNode* child = curr-&gt;child[idx];
  10. bool success = child &amp;&amp; erase(child, word, i + 1);
  11. if (success &amp;&amp; !child-&gt;isEnd &amp;&amp; child-&gt;isEmpty()) {
  12. delete child;
  13. curr-&gt;child[idx] = nullptr;
  14. }
  15. return success;
  16. }

huangapple
  • 本文由 发表于 2023年6月5日 15:33:38
  • 转载请务必保留本文链接：https://go.coder-hub.com/76404340.html
  • algorithm
  • c++
  • data-structures
  • trie
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定