Advertisement
Guest User

Trie

a guest
Mar 6th, 2016
499
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdlib>
  2.  
  3. using namespace std;
  4.  
  5. /**
  6.  * Namespaces: std
  7.  * Libraries: <cstdlib>
  8.  */
  9.  
  10. struct Node {
  11.     char key;
  12.     int count;
  13.     Node *next, *child;
  14.     Node(char key) : key(key), count(0), next(NULL), child(NULL) {}
  15. };
  16.  
  17. /**
  18.  * Complexity: O(|key| * k)
  19.  */
  20. Node *trie_find(Node *root, char *key) {
  21.     Node *node, *list;
  22.     for (list = root; *key != 0; key++) {
  23.         for (node = list; node != NULL; node = node->next)
  24.             if (node->key == *key)
  25.                 break;
  26.         if (node != NULL)
  27.             list = node->child;
  28.         else
  29.             return NULL;
  30.     }
  31.     return (node->count > 0) ? node : NULL;
  32. }
  33.  
  34. /**
  35.  * Complexity: O(|key| * k)
  36.  */
  37. void trie_insert(Node *(&root), char *key) {
  38.     Node *node, *list, *parent = NULL;
  39.     for (list = root; *key != 0; key++) {
  40.         for (node = list; node != NULL; node = node->next)
  41.             if (node->key == *key)
  42.                 break;
  43.         if (node != NULL)
  44.             list = node->child;
  45.         else {
  46.             node = new Node(*key);
  47.             node->next = list;
  48.             if (parent != NULL)
  49.                 parent->child = node;
  50.             else
  51.                 root = node;
  52.             list = NULL;
  53.         }
  54.         parent = node;
  55.     }
  56.     node->count++;
  57. }
  58.  
  59. /**
  60.  * Complexity: O(|key| * k)
  61.  */
  62. void trie_erase(Node *root, char *key) {
  63.     Node *node, *list;
  64.     for (list = root; *key != 0; key++) {
  65.         for (node = list; node != NULL; node = node->next)
  66.             if (node->key == *key)
  67.                 break;
  68.         if (node != NULL)
  69.             list = node->child;
  70.         else
  71.             return;
  72.     }
  73.     if (node->count > 0)
  74.         node->count--;
  75. }
Advertisement
RAW Paste Data Copied
Advertisement