Ternary Search Tree Java 구현
12591 단어 search
/**
* @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);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
선형 검색수색 프로그래밍에서 이는 값 목록에서 주어진 값 위치를 찾는 프로세스입니다. 일상 생활에서 데이터 수집에서 무언가를 찾는 것과 같이 중요한 역할을 합니다. 사전에서 단어를 찾거나 군중에서 친구를 찾아야 할 수도 있습...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.