如何建立Patricia-Trie图的模型
如何建立Patricia-Trie图的模型
提问于 2015-11-18 18:07:33
我正在尝试为Patricia Trie数据结构实现insert方法。因此，如果我插入字符串aba，那么字符串abc就会在屏幕截图中得到下面的trie。
我尝试过这段代码，但我不知道如何将图形建模为输出，以及如何在不使用node1、node2、node3等的情况下根据需要创建多个节点？
配子类：
package patriciaTrie;
import java.util.Scanner;
public class Patricia {
private Node root;
private Node parent;
private Node node1;
private Node node2;
// create a new node
public Patricia() {
root = null;
parent = null;
}
// inserts a string into the trie
public void insert(String s) {
if (root == null) {
root = new Node(s, "o-");
parent = new Node("-o");
} else {
insert(root, s);
}
}
private void insert(Node root, String s) {
int len1 = root.edge.length();
int len2 = s.length();
int len = Math.min(len1, len2);
for (int index = 0; index < len; index++) {
if (s.charAt(index) != root.edge.charAt(index)) {
// In case the string are not equal, then split them.
String samesubString = s.substring(0, index);
String substringSplit1 = root.edge.substring(index);
String substringSplit2 = s.substring(index);
root.edge = samesubString;
node1 = new Node(substringSplit1, "-o");
node2 = new Node(substringSplit2, "-o");
System.out.println(root.value + root.edge + node1.value +node1.edge + node2.value + node2.edge);
} else {
System.out.println("They are the same - " + index);
}
}
}
public static void main(String[] args) {
Patricia p = new Patricia();
Scanner s = new Scanner(System.in);
while (s.hasNext()) {
String op = s.next();
if (op.equals("INSERT")) {
p.insert(s.next());
}
}
}
}节点类：
package patriciaTrie;
public class Node {
String edge;
String value;
Node(String edge, String value) {
this.edge = edge;
this.value = value;
}
Node(String value){
this.value = value;
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2015-11-18 18:13:34
使用跟随者边的数组或列表，而不是只使用一条边。通常在图中使用跟随边的列表，这对于trie来说没有什么特别的。
要构建Patricia trie，请使用Node类simillar：
public class TrieNode {
String value;
// The outgoing (downstream) neighbour nodes
List<TrieNode> next; // probably LinkedList
/** Default Constructor with value */
public TrieNode(String value) {
this.value = value
}
}一旦它建立起来，您就可以使用较少的内存转换为只读图(尝试通常用于在运行时不再更改的字典)。
为了最终实现一个低内存消耗的trie，它使用数组而不是列表。列表总是比数组使用更多的内存。
public class TrieNode {
String value;
TrieNode[] next;
}在您的示例中，您可以构建图形：
TrieNode nodeRoot = new TrieNode ("ab");
TrieNode nodeLeft = new TrieNode ("a");
TrieNode nodeRight = new TrieNode ("c");
nodeRoot.next.add(nodeLeft);
nodeRoot.next.add(nodeRight);页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33787202
复制相关文章
相似问题
腾讯云开发者
