Merge branch 'BAEL-1434' of git://github.com/fatosmorina/tutorials into fatosmorina-BAEL-1434

pivovarit · pivovarit · commit c454fc8b0b77 · 2018-01-20T11:01:48.000+01:00
diff --git a/core-java/src/main/java/com/baeldung/trie/Trie.java b/core-java/src/main/java/com/baeldung/trie/Trie.java
@@ -0,0 +1,78 @@
+package com.baeldung.trie;
+
+public class Trie {
+    private TrieNode root;
+
+    public Trie() {
+        root = new TrieNode();
+    }
+
+    public void insert(String word) {
+        TrieNode current = root;
+        for (int i = 0; i < word.length(); i++) {
+            char ch = word.charAt(i);
+            TrieNode node = current.getChildren()
+                .get(ch);
+            if (node == null) {
+                node = new TrieNode();
+                current.getChildren()
+                    .put(ch, node);
+            }
+            current = node;
+        }
+        current.setEndOfWord(true);
+    }
+
+    public boolean find(String word) {
+        TrieNode current = root;
+        for (int i = 0; i < word.length(); i++) {
+            char ch = word.charAt(i);
+            TrieNode node = current.getChildren()
+                .get(ch);
+            if (node == null) {
+                return false;
+            }
+            current = node;
+        }
+        return current.isEndOfWord();
+    }
+
+    public void delete(String word) {
+        delete(root, word, 0);
+    }
+
+    private boolean delete(TrieNode current, String word, int index) {
+        if (index == word.length()) {
+            if (!current.isEndOfWord()) {
+                return false;
+            }
+            current.setEndOfWord(false);
+            return current.getChildren()
+                .size() == 0;
+        }
+        char ch = word.charAt(index);
+        TrieNode node = current.getChildren()
+            .get(ch);
+        if (node == null) {
+            return false;
+        }
+        boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
+
+        if (shouldDeleteCurrentNode) {
+            current.getChildren()
+                .remove(ch);
+            return current.getChildren()
+                .size() == 0;
+        }
+        return false;
+    }
+
+    public boolean containsNode(String word) {
+        return find(word);
+    }
+
+    public boolean isEmpty() {
+        return root == null;
+    }
+
+}
diff --git a/core-java/src/main/java/com/baeldung/trie/TrieNode.java b/core-java/src/main/java/com/baeldung/trie/TrieNode.java
@@ -0,0 +1,31 @@
+package com.baeldung.trie;
+
+import java.util.HashMap;
+import java.util.Map;
+
+class TrieNode {
+    private Map<Character, TrieNode> children;
+    private boolean endOfWord;
+
+    public TrieNode() {
+        children = new HashMap<>();
+        endOfWord = false;
+    }
+
+    public Map<Character, TrieNode> getChildren() {
+        return children;
+    }
+
+    public void setChildren(Map<Character, TrieNode> children) {
+        this.children = children;
+    }
+
+    public boolean isEndOfWord() {
+        return endOfWord;
+    }
+
+    public void setEndOfWord(boolean endOfWord) {
+        this.endOfWord = endOfWord;
+    }
+
+}
diff --git a/core-java/src/test/java/com/baeldung/trie/TrieTest.java b/core-java/src/test/java/com/baeldung/trie/TrieTest.java
@@ -0,0 +1,55 @@
+package com.baeldung.trie;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+public class TrieTest {
+    @Test
+    public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() {
+        Trie trie = createTrie();
+
+        assertFalse(trie.isEmpty());
+    }
+
+    @Test
+    public void givenATrie_WhenAddingElements_ThenTrieHasThoseElements() {
+        Trie trie = createTrie();
+
+        assertFalse(trie.containsNode("3"));
+        assertFalse(trie.containsNode("vida"));
+
+        assertTrue(trie.containsNode("life"));
+    }
+
+    @Test
+    public void givenATrie_WhenLookingForNonExistingElement_ThenReturnsFalse() {
+        Trie trie = createTrie();
+
+        assertFalse(trie.containsNode("99"));
+    }
+
+    @Test
+    public void givenATrie_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
+
+        Trie trie = createTrie();
+
+        assertTrue(trie.containsNode("Programming"));
+        trie.delete("Programming");
+        assertFalse(trie.containsNode("Programming"));
+    }
+
+    private Trie createTrie() {
+        Trie trie = new Trie();
+
+        trie.insert("Programming");
+        trie.insert("is");
+        trie.insert("a");
+        trie.insert("way");
+        trie.insert("of");
+        trie.insert("life");
+
+        return trie;
+    }
+}
