Advertisement
Guest User

Trie

a guest
Mar 6th, 2016
851
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdlib>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. /**
  7.  * Namespaces: std
  8.  * Libraries: <cstdlib>, <map>
  9.  */
  10.  
  11. struct Node {
  12.     bool leaf;
  13.     Node *parent;
  14.     map<char, Node *> child;
  15.     Node(Node *parent = NULL)
  16.         : parent(parent), leaf(false), child()
  17.     {}
  18. };
  19.  
  20. /**
  21.  * Complexity: O(|key| * log(k))
  22.  */
  23. Node *trie_find(Node *root, char *key) {
  24.     Node *it;
  25.     for (it = root; *key != 0; key++) {
  26.         if (it->child.find(*key) == it->child.end())
  27.             return NULL;
  28.         it = it->child[*key];
  29.     }
  30.     return (it->leaf) ? it : NULL;
  31. }
  32.  
  33. /**
  34.  * Complexity: O(|key| * log(k))
  35.  */
  36. void trie_insert(Node *root, char *key) {
  37.     Node *it;
  38.     for (it = root; *key != 0; key++) {
  39.         if (it->child.find(*key) == it->child.end())
  40.             it->child[*key] = new Node(it);
  41.         it = it->child[*key];
  42.     }
  43.     it->leaf = true;
  44. }
  45.  
  46. /**
  47.  * Complexity: O(|key| * log(k))
  48.  */
  49. void trie_erase(Node *root, char *key) {
  50.     Node *it;
  51.     for (it = root; *key != 0; key++) {
  52.         if (it->child.find(*key) == it->child.end())
  53.             return;
  54.         it = it->child[*key];
  55.     }
  56.     it->leaf = false;
  57.     while (it->parent != NULL) {
  58.         if (it->child.size() > 0 || it->leaf)
  59.             break;
  60.         it = it->parent, key--;
  61.         it->child.erase(*key);
  62.     }
  63. }
Advertisement
RAW Paste Data Copied
Advertisement