java - "Simple" Trie Implementation -

i need implement trie (in java) college project. trie should able add , remove strings (for phase 1).

i have spent several hours each day (for last few days) trying figure out how , failed miserably each time.

i require help, examples on internet , textbook (data structures , algorithms in java adam drozdek) not helping.

information

1. node classes working with:

   class node {     public boolean isleaf; }  class internalnode extends node {     public string letters;  //letter[0] = '$' always.     //see image -> if letter[1] = 'a' children[1] refers child node "ammo"     //see image -> if letter[2] = 'b' children[2] refers internal node "#eu"     public trienode[] children = new trienode[2];      public trieinternalnode(char ch)     {         letters = "#" + string.valueof(ch);//letter[0] = '$' always.         isleaf = false;     } }  class leafnode extends node {     public string word;     public trieleafnode(string word)     {         this.word = new string(word);         isleaf = true;     } } 

2. and here pseudo code insert need follow: (warning vague)

   trieinsert(string k) {     = 0;     p = root;     while (not inserted)     {         if end of word k reached             set end-of-word marker in p true;         else if (p.ptrs[k[i]] == 0)             create leaf containing k , put address in p.ptrs[k[i]];         else if reference p.ptrs[k[i]] refers leaf         {             k_l = key in leaf p.ptrs[k[i]]                         {                 create nonleaf , put address in p.ptrs[k[i]];                 p = new nonleaf;             } while (k[i] == k_l[i++]);         }         create leaf containing k , put address in p.ptrs[k[--i]];         if end of word k reached             set end-of-word marker in p true;         else             create leaf containing k_l , put address in p.ptrs[k_l[i]];         else             p = p.ptrs[k[i++]];     } } 

3. i need implement following methods.

   public boolean add(string word){...}//adds word trie structure should return true if successful , false otherwise  public boolean remove(string word){...}//removes word trie structure should return true if successful , false otherwise 

4. i cant find pseudo code remove, if insert not work delete wont me.

5. here image of how trie need implement should like.

6. i aware trie still inefficient if implemented this, @ moment need not worry this.

7. the book provides implementation similar need doesn't use end of word char ('$') , stores words without prefixes in child nodes http://mathcs.duq.edu/drozdek/dsinjava/spellcheck.java

constraints

1. i need implement trie in java.
2. i may not import or use of java's built-in data structures. (ie. no map, hashmap, arraylist etc)
3. i may use arrays, java primitive types , java strings.
4. the trie must use $ (dollar) symbol indicate end-of-word. (see image below )

5. i may asume word containing $symbol inserted.
6. i need implement trie in same style book does.
7. case of words doesn't matter ie. words considered lowercase
8. the trie should store end-of-word character , characters applicable word , not entire alphabet(like implementations).

i not expect implementation me(unless have 1 lying around :p) need help.

first of all, don't think should make leaf nodes , internal nodes separate classes. recommend making universal node class isleaf() method. method return true if node has no children.

here higher-level pseudocode functions need implement. simplicity, assume existence of method called getindex() returns index corresponding character.

insert(string str)     node current = null     each character in str         int index = getindex(character)         if current.children[index] has not been initialized             initialize current.children[index] new node         current = current.children[index] 

you can augment pseudocode fit needs. example, if want return false whenever insertion isn't successful:

• return false if input string null
• return false if input string contains invalid characters

now, here higher-level pseudocode remove.

remove(string str)     node current = null     each character in str         int index = getindex(character)         current = current.children[index]       // @ point, found node want remove. however, want      // delete many ancestor nodes possible. can delete ancestor node      // if not need more. is, can delete ancestor node      // if has 1 child.       node ancestor = current     while ancestor not null         if ancestor has 2 or more children             break out of loop          else if ancestor has less 2 children             node grandancestor = ancestor.parent             if grandancestor not null                 reinitialize grandancestor.children // has effect of removing ancestor          ancestor = ancestor.parent    

at high level, follow input string node want remove. after this, traverse tree following parent pointers , delete every node 1 child (since no longer needed). once reach node 2 children, stop.

like insert, can augment pseudocode return false whenever deletion isn't successful:

• return false if input string null
• return false if input string contains invalid characters
• return false if input string leads node doesn't exist

it easiest implement delete if node class has parent field. however, possible implement method without parent points, more difficult. can see example of trickier implementation here.