Shulou(Shulou.com)06/03 Report--

This article mainly explains "the algorithm implementation of dictionary tree in Java". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "the algorithm implementation of dictionary tree in Java".

Preface

Dictionary tree, also known as word search tree, is a typical one-to-many string matching algorithm. "one" refers to a pattern string, and "many" refers to multiple template strings. Dictionary trees are often used to count, sort, and save a large number of strings. It uses the common prefix of strings to reduce query time and minimize unnecessary string comparisons.

Dictionary trees have three basic properties:

The root node contains no characters, and each remaining node contains one character

From the root node to a node, the characters passed on the path are concatenated to be the corresponding string of that node.

All child nodes of each node contain different characters.

The pass parameter: represents the number of words passing through this point. The root of root is the number of words in the whole tree.

The end parameter: there are several words that represent the end at this point. For example, there are two hello in the image above, and the end parameter in the o node is 2.

Realize the basic function: add, delete and check.

Algorithm analysis

The first is the parameters of the node:

Public class Node {public int pass; public int end; public Node [] nexts; / / address of the next letter public Node () {pass = 0; end = 0; nexts = new Node [26]; / / Let's take lowercase letters as an example}}

The following is the implementation of the basic functions:

Import java.util.Scanner;public class Main {public static void main (String [] args) {String [] arr = {"hello", "hello"}; Trie root = new Trie (); for (int I = 0; I < arr.length; iTunes +) {root.addWord (arr [I]);} / root.delWord ("hello"); Scanner sc = new Scanner (System.in) String s = sc.nextLine (); if (root.searchWord (s)! = 0) {System.out.println ("this dictionary tree has this" + s + "word");}} public static class Node {public int pass; public int end; public Node [] nexts / / the next letter address public Node () {pass = 0; end = 0; nexts = new Node [26];}} public static class Trie {private Node root; public Trie () {root = new Node () } / / add public void addWord (String str) {char [] arr = str.toCharArray (); root.pass++; Node node = root; for (char s: arr) {int index = s -'a' / / use the corresponding ASCII code difference to store if (node.nexts [index] = = null) {node.nexts [index] = new Node ();} node = node.nexts [index]; node.pass++ / / after this node, pass will add 1} node.end++;} / / delete public void delWord (String str) {/ / before deleting, you should query the tree for the word while (searchWord (str)! = 0) {char [] arr = str.toCharArray () Node node = root; node.pass--; for (int I = 0; I < str.length (); iTunes +) {int index = arr [I]-'asides; node = node.nexts [index]; node.pass-- } node.end--;}} / / find public int searchWord (String str) {if (str = = null) {return 0;} char [] arr = str.toCharArray (); Node node = root; for (int I = 0) I < str.length (); iTunes +) {int index = arr [I]-'asides; if (node.nexts [index] = = null) {return 0;} node = node.nexts [index];} return node.end / / return the end value of the last node} Thank you for reading. The above is the content of "algorithm implementation of Dictionary Tree in Java". After the study of this article, I believe you have a deeper understanding of the algorithm implementation of dictionary tree in Java, and the specific usage still needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.