Implementation of tri-tree in Java

Java implementation of tri-tree

What is a trie tree?

Untitled Diagram.png

A trie tree is a kind of ordered tree, and it is an algorithm in which characters are stored in each node and a search can be performed by tracing the nodes.

Write in Java

Create a class that represents a node

public class Node {
	private int id;
	private String str;
	private ArrayList<Node> child = new ArrayList<>();
	public int getId() {
		return this.id;
	}
	public String getStr() {
		return this.str;
	}
	public ArrayList<Node> getChild(){
		return this.child;
	}
	public void setId(int id) {
		this.id = id;
	}
	public void setStr(String str) {
		this.str = str;
	}
	public void setChild(Node node) {
		this.child.add(node);
	}
}

The id identifies the node and does not have to be separate str is the character to store in the node child is supposed to store the child of the node

Trees can be built as follows

public class Main {
	private static ArrayList<Node> nodeList = new ArrayList<>();
	private static int id = 1;
	public static void insert(Node parent, String word, int charIndex) {
		String w = String.valueOf(word.charAt(charIndex));
		//System.out.println(w);
		if(charIndex == word.length()-1) { //For the last character
			for(Node n:parent.getChild()) { //If the last node is an existing node
				if(n.getStr() != null&&n.getStr().equals(w)) {
					return;
				}
			}
			Node node = new Node();
			node.setStr(w);
			parent.setChild(node);
			node.setChild(node);
			node.setId(id);
			id += 1;
			nodeList.add(node);
			return;
		}
		for(Node n:parent.getChild()) { //If the child contains the current ward
			if(n.getStr() != null&&n.getStr().equals(w)) {
				insert(n,word,charIndex+1);
				return;
			}
		}
		Node node = new Node();
	        node.setStr(w);
		parent.setChild(node);
		node.setId(id);
		id += 1;
		nodeList.add(node);
		if(charIndex < word.length()-1) { //Recursive processing
		     insert(node, word, charIndex+1);
		}
	}

I'm sorry if I made a mistake because it was rewritten for the article that I wrote when I was making another algorithm with a little ingenuity in the trie tree (_ _)

Summary

This time, I had a chance to use a tri-tree, so I tried to implement it in java, but it took a long time to understand because it uses recursive processing. After all, I am not good at recursive processing, so I want to actively use it to eliminate my weakness ...

Recommended Posts

Implementation of tri-tree in Java
Implementation of like function in Java
Interpreter implementation in Java
Implementation of DBlayer in Java (RDB, MySQL)
Boyer-Moore implementation in Java
Heapsort implementation (in java)
[Java] Implementation of Faistel Network
Implementation of HashMap in kotlin
Implementation of asynchronous processing in Tomcat
List of members added in Java 9
List of types added in Java 9
Get the result of POST in Java
Let's create a TODO application in Java 4 Implementation of posting function
Partization in Java
Implementation of multi-tenant asynchronous processing in Tomcat
Let's create a TODO application in Java 6 Implementation of search function
Changes in Java 11
Let's create a TODO application in Java 8 Implementation of editing function
Rock-paper-scissors in Java
Mechanism and characteristics of Collection implementation class often used in Java
The story of writing Java in Emacs
Pi in Java
[Java] Overview of Java
Role of JSP in Web application [Java]
FizzBuzz in Java
Discrimination of Enums in Java 7 and above
This and that of the implementation of date judgment within the period in Java
Comparison of thread implementation methods in Java and lambda expression description method
The story of low-level string comparison in Java
[Java] Handling of JavaBeans in the method chain
The story of making ordinary Othello in Java
About the idea of anonymous classes in Java
Do you need a memory-aware implementation of Java?
Implementation of digit grouping in flea market apps
The story of learning Java in the first programming
Measure the size of a folder in Java
SKStoreReviewController implementation memo in Swift UI of iOS14
[Java] Use of final in local variable declaration
Feel the passage of time even in Java
[JQuery] Implementation procedure of AutoComplete function [Java / Spring]
[Rails] Implementation of "notify notification in some way"
Method name of method chain in Java Builder + α
Import files of the same hierarchy in Java
Expired collection of java
Read JSON in Java
Predicted Features of Java
Make Blackjack in Java
Rock-paper-scissors app in Java
Constraint programming in Java
[Java] Significance of serialVersionUID
Put java8 in centos7
NVL-ish guy in Java
Combine arrays in Java
"Hello World" in Java
Check Java toString () implementation
Callable Interface in Java
NIO.2 review of java
Review of java Shilber
Comments in Java source
Azure functions in java
Implementation of search function