Java의 Trie 데이터 구조-java지도 시간-php.cn

Java의 Trie 데이터 구조

王林

풀어 주다： 2024-08-30 16:19:11

원래의

558명이 탐색했습니다.

다음 문서에서는 Java의 Trie 데이터 구조에 대한 개요를 제공합니다. 기본적으로 데이터 구조는 컴퓨터 프로그래밍에서 매우 중요한 역할을 하며, 컴퓨터 프로그래밍에서 다양한 유형의 데이터 구조를 언제, 왜 사용하는지 알아야 합니다. 일반적으로 trie는 이산형 데이터 구조이며 이는 익숙하지 않습니다. 또는 널리 사용되는 데이터 구조는 아니지만 이는 일반적인 알고리즘에 사용된다고 말할 수 있습니다. trie는 디지털 트리라고도 알려져 있습니다. 기수 또는 접두사라는 다른 이름도 있습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

트리 데이터 구조를 사용하여 키가 있는 잘 구조화된 트리에서 접두사로 요소를 검색하며, 문자열을 저장하는 것이 유리합니다. 또한 삽입, 삭제, 검색 등 다양한 데이터 구조 연산을 수행할 수 있습니다.

Java의 Trie 데이터 구조 구문

다음은 언급된 구문입니다.

public void insert_node(specified string of word){
TrieNode present = rootNode;
For (char i: word.toCharArray()){
Present = present.getChildren().computeIfAbsent(I, c->new TrieNode());
}
Present.setEndOfWord(true)
}

로그인 후 복사

설명:

위 구문을 사용하여 trie 데이터 구조에 요소를 삽입하려고 합니다. 이를 위해서는 다음 단계를 따라야 합니다.

먼저 삽입 작업을 위해 현재 노드를 루트 노드로 설정해야 합니다.
이후에는 현재 문자를 단어의 첫 번째 문자로 설정해야 합니다.
디지털 트리에 현재 노드가 있으면 현재 문자를 참조하고, 현재 노드가 없으면 새 노드를 생성해야 합니다.
마지막으로 디지털 횡단에 Trie 키를 사용할 수 있습니다.

마찬가지로 삭제 및 검색 작업을 위한 구문을 작성할 수 있습니다.

Java에서 Trie 데이터 구조는 어떻게 작동하나요?

아래는 java에서 trie 데이터 구조가 어떻게 작동하는지 보여줍니다.

일반적으로 다음과 같이 트리 데이터 구조에서 3가지 다른 작업을 수행할 수 있습니다.

1. 요소 삽입 작업

위 항목에서는 이미 Java에서 삽입 작업이 어떻게 작동하는지 설명했습니다. 삽입 연산의 복잡도는 O(n)입니다. 여기서 n은 키의 크기를 나타냅니다.

2. 요소 연산 찾기

삽입 연산 후에는 다음과 같은 알고리즘을 사용하여 trie 데이터 구조에 대한 검색이나 찾기 연산을 수행할 수 있습니다.

코드:

public void find_node(specified string of word){
TrieNode present = rootNode;
For (char j = 0; j < word.length(); j++){
char c = word.charAt(j);
TrieNode node = present.getChildren().get(c);
If (node = = null){
return false;
}
Present = node;
}
return present.isEndOfWord();
}

로그인 후 복사

설명:

이제 다음과 같이 trie 데이터 구조의 검색 요소에 대해 다음 단계를 따르세요.

먼저 루트에서 하위 노드를 가져옵니다.
문자열의 모든 문자를 반복해야 하는 경우
이제 지정된 문자가 있는지 확인하거나 하위 트리의 일부라고 말할 수 있습니다. 지정된 문자가 하위 트리의 일부가 아닌 경우 false를 반환하고 종료합니다.
문자열에 문자가 없을 때까지 두 번째와 세 번째 단계를 반복합니다.
삽입 연산의 복잡도는 O(n)입니다. 여기서 n은 키의 크기를 나타냅니다.

3. 요소 삭제 작업

삽입 작업 외에도 요소를 찾습니다. 분명히 작업을 삭제할 수 있는 옵션도 있어야 하므로 다음 단계를 따라야 합니다.

지정된 요소가 현재 트라이의 일부인지 확인하세요.
요소가 발견되면 트리에서 제거하세요.
이 계산의 복잡성은 O(n)입니다. 여기서 n은 키 길이를 나타냅니다.

Java의 Trie 데이터 구조 예

아래는 Java의 Trie 데이터 구조의 예입니다.

코드:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// created class to store node into the trie data structure
class trie_data
{
// Define the size of alphabet size
private static final int CHAR_AlPHA_SIZE = 26;
private boolean isLeaf;
private List<trie_data> child = null;
// Created Constructor of class
trie_data()
{
isLeaf = false;
child = new ArrayList<>(Collections.nCopies(CHAR_AlPHA_SIZE, null));
}
// function for insertion operation
public void trie_insert(String id)
{
System.out.println("We inserted new element into the data structure \"" + id + "\"");
// Staritng from the parent node that is root node
trie_data present = this;
for (char ch: id.toCharArray())
{
// if node is not exist then create new node in trie
if (present.child.get(ch - 'a') == null) {
present.child.set(ch - 'a', new trie_data());
}
// visit next node
present = present.child.get(ch - 'a');
}
// mark present as leaf node
present.isLeaf = true;
}
// search function to search element into trie data structure
// if key value is not present then it return the false
public boolean trie_search(String id)
{
System.out.print("We searched element\"" + id + "\" : ");
trie_data present = this;
for (char ch: id.toCharArray())
{
// visit next node
present = present.child.get(ch - 'a');
if (present == null) {
return false;
}
}
return present.isLeaf;
}
}
class Main
{
public static void main (String[] args)
{
// construct a new Trie node
trie_data head = new trie_data();
head.trie_insert("the");
head.trie_insert("they");
head.trie_insert("final");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // false
head.trie_insert("Sample");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // true
}
}

로그인 후 복사

설명:

위의 예에서는 Java에서 trie 데이터 구조를 구현하려고 시도합니다. 여기서는 먼저 trie 데이터 구조에 노드를 저장하는 클래스를 만들었습니다. 그런 다음 CHAR_AlPHA_SIZE를 사용하여 알파벳 크기를 정의했습니다. 그런 다음 클래스의 생성자를 만들었습니다.
위 프로그램에 표시된 것처럼 삽입 작업 'trie_insert'()를 위한 함수와 trie 데이터 구조에서 요소를 검색하는 함수가 있습니다. 프로그램이 끝나면 trie 데이터 구조에 삽입하고 검색해야 하는 다른 값을 사용하여 삽입 및 검색 기능을 호출하기만 하면 됩니다.

출력:

Java의 Trie 데이터 구조