Daily Archives: December 22, 2014

In the structure of my PatriciaTree, it has following parameters:
char c, indicate the char the node has.
HashMap<Character, PatriciaTree> children, indicate the children the node has.
String leftString, this a bit difficult to explain. So let me raise an example. If root only has a word “dog”. So the structure would be like:
.root…….
..\………
…d(og)….
But not:
.root…….
..\………
…d……..
….\…….
…..o……
……\…..
…….g….
So, in this case, I use the leftString to store the string after ‘d’, which is ‘og’. And I call the node d(og) string leaf.

is that I define 4 types of nodes:
1. STATE_ROOT, the root the patricia tree.
2. STATE_STRINGLEAF, it is a leaf, and it has left string in it. Like the example I showed above.
3. STATE_LEAF, it is a leaf, and it doesn’t has left string.
For example, the ‘g’ and ‘t’ nodes are both LEAF node, but not string leaf node.
.root………
..\………..
…d……….
….\………
…..o……..
…../.\…….
…g….t…..
4. STATE_MIDDLE, in the above case, the ‘d’ and ‘o’ are middle nodes.

In the following code. it demonstrate how to build a patricia tree, and the method to find if a word exists in a patricia tree.

1. import java.util.HashMap;
2. public class PatriciaTree {
3.     public static final int STATE_ROOT = 0;
4.     public static final int STATE_LEAF = 1;
5.     public static final int STATE_STRINGLEAF = 2;
6.     public static final int STATE_MIDDLE = 3;
8.     char c;
9.     HashMap<Character, PatriciaTree> children;
10.     int state;    //0 is root, 1 is leaf, 2 is leaf with string, 3 is middle
11.     String leftString;    //if the node is leaf with string, it has a rest word
12.     PatriciaTree parent;
14.     //store word into this PatriciaTree, word starts from pos
15.     public boolean addNode(String word, int pos, PatriciaTree parent){
16.         if(word==null||pos>=word.length()){
17.             return false;
18.         }
19.         PatriciaTree child;
20.         if(state==STATE_ROOT||state==STATE_MIDDLE){
21.             //if it is root, then find if it children have tree with character pos[0]
22.             child = children.get(word.charAt(pos));
23.             if(child==null){    //it doesn’t has word.charAt[pos], then create tree under it.
24.                 child = new PatriciaTree(word, pos, this);
25.                 children.put(word.charAt(pos), child);
26.                 return true;
27.             }
28.             return child.addNode(word, pos+1, this);    //it has char, then create tree under its child.
29.         }
30.         if(state==STATE_LEAF){
31.             //now it is leaf, and there is still chars, then just change it to a STRINGLEAF
32.             this.state = STATE_STRINGLEAF;
33.             this.leftString = word.substring(pos, word.length()-1);
34.             return true;
35.         }
36.         if(state==STATE_STRINGLEAF){
37.             if(word.charAt(pos)!=leftString.charAt(0)){
38.                 //1st char of leftString doesn’t match word[pos], so create the tree under it.
39.                 //And create leftString as its subtree.
40.                 child = new PatriciaTree(word, pos, this);
41.                 children.put(word.charAt(pos), child);
42.                 child = new PatriciaTree(leftString, 0, this);
43.                 children.put(leftString.charAt(0), child);
44.                 this.state = STATE_MIDDLE;
45.                 return true;
46.             }
47.             //1st char of leftString match word[pos], so break the stringleaf into middle,
48.             //and create its child with char of the 1st leftString
49.             this.state = STATE_MIDDLE;
50.             child = new PatriciaTree(leftString, 0, this);
51.             children.put(leftString.charAt(0), child);
52.             this.leftString = “”;
53.             child.addNode(word, pos+1, child);
54.             return true;
55.         }
57.         return false;
58.     }
60.     public boolean findString(String word, int pos){
61.         if(pos>=word.length()){
62.             if(this.state==STATE_MIDDLE){
63.                 return false;    //is in the middle, is not counted as found.
64.             }
65.             if(this.state==STATE_LEAF){
66.                 return true;    //return true if this is leaf
67.             }
68.             return false;
69.         }
70.         PatriciaTree child;
71.         if(this.state==STATE_ROOT||this.state==STATE_MIDDLE){
72.             child = this.children.get(word.charAt(pos));
73.             return child==null?false:child.findString(word, pos+1);
74.         }
75.         if(this.state==STATE_LEAF){
76.             return false;    //the word is larger than the leaf string
77.         }
78.         if(this.state==STATE_STRINGLEAF){
79.             String strInWord = word.substring(pos, word.length());
80.             if(leftString.equals(strInWord)){
81.                 return true;
82.             }
83.         }
84.         return false;
85.     }
87.     public PatriciaTree(){
88.         this.children = new HashMap<Character, PatriciaTree>();
89.     }
91.     public PatriciaTree(String word, int pos, PatriciaTree parent){
92.         this.c = word.charAt(pos);
93.         this.parent = parent;
94.         this.state = STATE_LEAF;
95.         this.children = new HashMap<Character, PatriciaTree>();
96.         if(pos<word.length()-1){
97.             this.state = STATE_STRINGLEAF;
98.             this.leftString = word.substring(pos+1, word.length());
99.         }
100.     }
102.     public static void main(String[] args) {
103.         PatriciaTree root = new PatriciaTree();
104.         root.state = STATE_ROOT;
105.         String[] words = {“zebra”, “zero”, “dog”, “dot”, “ducks”, “duh”, “ducky”};
106.         for(int i=0;i<words.length;i++){
107.             root.addNode(words[i], 0, root);
108.         }
109.         System.out.println(root.findString(“dogg”, 0));
110.     }
111. }