Ternary Search Tree Java実装
12515 ワード
/**
* @author Edwin Chen
*
*/
//
class Node {
//
char storeChar;
//
boolean isComplete;
Node leftChild,centerChild,rightChild;
//
public Node(char storeChar,boolean isComplete) {
this.storeChar = storeChar;
this.isComplete = isComplete;
}
}
public class TernarySearchTree {
//
public Node root;
//
HashSet<String> result = new HashSet<String>();
// tree
public Node insert(String word,Node node,Integer index) {
if(word == null || "".equals(word))
return null;
// word char
char[] charArray = word.toCharArray();
// ， ，
if(node == null) {
node = new Node(charArray[index],false);
}
if(charArray[index] < node.storeChar) {
node.leftChild = this.insert(word, node.leftChild,index);
} else if(charArray[index] > node.storeChar) {
node.rightChild = this.insert(word, node.rightChild,index);
} else {
// word ， , ，
if(index + 1 == charArray.length) {
node.isComplete = true;
} else {
node.centerChild = this.insert(word, node.centerChild,++index);
}
}
return node;
}
//
public void insert(String word) {
root = this.insert(word,root,0);
}
public String toString()
{
traverse(root, "");
return "
Ternary Search Tree : "+ result;
}
//
private void traverse(Node node, String str)
{
if (node != null)
{
traverse(node.leftChild, str);
str = str + node.storeChar;
if (node.isComplete)
result.add(str);
traverse(node.centerChild, str);
str = str.substring(0, str.length() - 1);
traverse(node.rightChild, str);
}
}
public boolean search(String word)
{
return search(root, word.toCharArray(), 0);
}
private boolean search(Node node, char[] word, int index)
{
if (node == null)
return false;
if (word[index] < node.storeChar)
return search(node.leftChild, word, index);
else if (word[index] > node.storeChar)
return search(node.rightChild, word, index);
else
{
if (node.isComplete && index == word.length - 1)
return true;
else if (index == word.length - 1)
return false;
else
return search(node.centerChild, word, index + 1);
}
}
public Node findNode(String prefix) {
return findNode(root,prefix.toCharArray(),0);
}
public Node findNode(Node node, char[] word, int index) {
if (node == null)
return null;
if (word[index] < node.storeChar)
return findNode(node.leftChild, word, index);
else if (word[index] > node.storeChar)
return findNode(node.rightChild, word, index);
else
{
if (index == word.length - 1)
return node.centerChild;
else
return findNode(node.centerChild, word, index + 1);
}
}
// word
public HashSet<String> prefixSearch(String prefix,Node node) {
if(node != null) {
if(node.isComplete) {
result.add(prefix + node.storeChar);
}
prefixSearch(prefix,node.leftChild);
prefixSearch(prefix + node.storeChar,node.centerChild);
prefixSearch(prefix,node.rightChild);
}
if(search(prefix))
result.add(prefix);
return result;
}
public HashSet<String> prefixSearch(String prefix) {
Node node = findNode(prefix);
return prefixSearch(prefix,node);
}
public static void main(String[] args) {
TernarySearchTree t = new TernarySearchTree();
t.insert("ab");
t.insert("abba");
t.insert("abcd");
t.insert("bcd");
HashSet<String> a = t.prefixSearch("ab");
for(String s : a) {
System.out.println(s);
}
System.out.println(t);
}
}