Fix Trie implementation (eugenp#4668)

pivovarit · web-flow · commit 692eafafea6d · 2018-07-09T16:26:52.000+02:00
* encoding

* Fix Trie implementation
diff --git a/data-structures/src/main/java/com/baeldung/trie/Trie.java b/data-structures/src/main/java/com/baeldung/trie/Trie.java
@@ -1,13 +1,13 @@
 package com.baeldung.trie;
 
-public class Trie {
+class Trie {
     private TrieNode root;
 
     Trie() {
         root = new TrieNode();
     }
 
-    public void insert(String word) {
+    void insert(String word) {
         TrieNode current = root;
 
         for (int i = 0; i < word.length(); i++) {
@@ -16,11 +16,11 @@ public void insert(String word) {
         current.setEndOfWord(true);
     }
 
-    public boolean delete(String word) {
+    boolean delete(String word) {
         return delete(root, word, 0);
     }
 
-    public boolean containsNode(String word) {
+    boolean containsNode(String word) {
         TrieNode current = root;
 
         for (int i = 0; i < word.length(); i++) {
@@ -34,7 +34,7 @@ public boolean containsNode(String word) {
         return current.isEndOfWord();
     }
 
-    public boolean isEmpty() {
+    boolean isEmpty() {
         return root == null;
     }
 
@@ -51,7 +51,7 @@ private boolean delete(TrieNode current, String word, int index) {
         if (node == null) {
             return false;
         }
-        boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
+        boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord();
 
         if (shouldDeleteCurrentNode) {
             current.getChildren().remove(ch);
diff --git a/data-structures/src/main/java/com/baeldung/trie/TrieNode.java b/data-structures/src/main/java/com/baeldung/trie/TrieNode.java
@@ -4,28 +4,18 @@
 import java.util.Map;
 
 class TrieNode {
-    private Map<Character, TrieNode> children;
+    private final Map<Character, TrieNode> children = new HashMap<>();
     private boolean endOfWord;
 
-    public TrieNode() {
-        children = new HashMap<>();
-        endOfWord = false;
-    }
-
-    public Map<Character, TrieNode> getChildren() {
+    Map<Character, TrieNode> getChildren() {
         return children;
     }
 
-    public void setChildren(Map<Character, TrieNode> children) {
-        this.children = children;
-    }
-
-    public boolean isEndOfWord() {
+    boolean isEndOfWord() {
         return endOfWord;
     }
 
-    public void setEndOfWord(boolean endOfWord) {
+    void setEndOfWord(boolean endOfWord) {
         this.endOfWord = endOfWord;
     }
-
 }
diff --git a/data-structures/src/test/java/com/baeldung/trie/TrieTest.java b/data-structures/src/test/java/com/baeldung/trie/TrieTest.java
@@ -1,6 +1,7 @@
 package com.baeldung.trie;
 
 import org.junit.Test;
+import org.junit.jupiter.api.Assertions;
 
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -53,6 +54,19 @@ public void givenATrie_whenDeletingElements_thenTreeDoesNotContainThoseElements(
         assertFalse(trie.containsNode("Programming"));
     }
 
+    @Test
+    public void givenATrie_whenDeletingOverlappingElements_thenDontDeleteSubElement() {
+
+        Trie trie1 = new Trie();
+
+        trie1.insert("pie");
+        trie1.insert("pies");
+
+        trie1.delete("pies");
+
+        Assertions.assertTrue(trie1.containsNode("pie"));
+    }
+
     private Trie createExampleTrie() {
         Trie trie = new Trie();
 
diff --git a/spring-boot-ops/README.md b/spring-boot-ops/README.md
