Removing pointers from trie implementation.

1 files changed, 20 insertions, 15 deletions

diff --git a/string/trie.cpp b/string/trie.cpp
index 1b5f573..fa9ec49 100644
--- a/string/trie.cpp
+++ b/string/trie.cpp
@@ -1,20 +1,25 @@
+// Zahlenwerte müssen bei 0 beginnen und zusammenhängend sein.
 struct node {
-	node *e[26]; // Implementierung für Kleinbuchstaben.
-	int c = 0; // Anzahl der Wörter, die an diesem node enden.
-	node() { for(int i = 0; i < 26; i++) e[i] = NULL; }	
+  int children[ALPHABET_SIZE], c; // c = #Wörter, die hier enden.
+  node () {
+    idx = -1;
+    for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = -1;
+  }
 };
+vector<node> trie; // Anlegen mit trie.push_back(node());
 
-void insert(node *root, string &txt, int s = 0) { // Laufzeit: O(|txt|)
-	if(s == (int)txt.size()) root->c++;
-	else {
-		int idx = (int)(txt[s] - 'a');
-		if(root->e[idx] == NULL) root->e[idx] = new node();
-		insert(root->e[idx], txt, s+1);
-}}
+void insert(int vert, vector<int> &txt, int s) { // Laufzeit: O(|txt|)
+  if (s == (int)txt.size()) { trie[vert].c++; return; }
+  if (trie[vert].children[txt[s]] == -1) {
+    trie[vert].children[txt[s]] = trie.size();
+    trie.push_back(node());
+  }
+  insert(trie[vert].children[txt[s]], txt, s + 1);
+}
 
-int contains(node *root, string &txt, int s = 0) { // Laufzeit: O(|txt|)
-	if(s == (int)txt.size()) return root->c;
-	int idx = (int)(txt[s] - 'a');
-	if(root->e[idx] != NULL) return contains(root->e[idx], txt, s + 1);
-	else return 0;
+int contains(int vert, vector<int> &txt, int s) { // Laufzeit: O(|txt|)
+  if (s == (int)txt.size()) return trie[vert].c;
+  if (trie[vert].children[txt[s]] != -1) {
+    return contains(trie[vert].children[txt[s]], txt, s + 1);
+  } else return 0;
 }