접두사 트리 golang 구현

접두사 트리(Trie)는 문자열 저장 및 일치에 주로 사용되는 데이터 구조입니다. 이번 글에서는 Golang을 이용하여 Prefix Tree를 구현하는 방법을 소개하겠습니다.

1. 접두사 트리란 무엇인가요?

사전 트리라고도 불리는 접두사 트리는 문자열 모음을 저장하는 데 사용되는 트리 형태의 데이터 구조로, 주로 많은 양의 텍스트에서 특정 문자열을 효율적으로 찾는 데 사용됩니다. 해시 테이블과 같은 다른 데이터 구조와 비교할 때 접두사 트리의 시간 복잡도는 O(k)입니다. 여기서 k는 찾을 문자열의 길이를 나타냅니다.

접두사 트리의 핵심 개념은 "노드"이며, 각 노드에는 다음 정보가 포함됩니다.

• a 문자 c;
• a 이 노드로 끝나는 문자열이 존재하는지 여부를 나타내는 부울 값 isLeaf; 테이블 children은 하위 노드를 저장하는 데 사용되며 키는 하위 노드에 해당하는 문자입니다.
• 다음 그림은 4개의 문자열(apple, apply, app, 바나나)을 포함하는 접두사 트리의 예입니다.

접두사 트리의 기본 작업

2. 접두사 트리의 기본 작업에는 삽입이 포함됩니다. 검색 및 삭제:

2.1 삽입

접두사 트리에 문자열을 삽입할 때 루트 노드부터 탐색을 시작해야 합니다.

구체적인 단계는 다음과 같습니다.

현재 노드를 루트 노드로 초기화합니다.

• 현재 문자가 현재 노드의 하위 노드에 없으면 새 노드를 만들고
• 현재 문자가 현재 노드의 하위 노드에 있으면 해당 노드로 이동합니다.
• 문자열을 탐색한 후 현재 노드의 isLeaf를 true로 표시합니다.
• 다음은 "apple"이라는 문자열을 삽입하는 예와 그 실행 과정이다.

2.2 찾기

문자열을 찾을 때 루트 노드부터 탐색을 시작해야 한다.

구체적인 단계는 다음과 같습니다.

현재 노드를 루트 노드로 초기화합니다.

• 현재 문자가 현재 노드의 하위 노드에 없으면 문자열을 의미합니다.
• 현재 문자가 현재 노드의 하위 노드에 있으면 해당 노드로 이동합니다.
• 문자열을 탐색한 후 현재 노드의 isLeaf 표시가 true이면 문자열이 접두사 트리에 존재합니다. 그렇지 않으면 접두사가 접두사 트리에 있지만 문자열이 접두사 트리에 존재하지 않음을 의미합니다.
• 다음은 "appl" 문자열을 찾는 예와 그 실행 과정입니다.

2.3 삭제

문자열을 삭제할 때 루트 노드부터 순회를 시작해야 합니다.

구체적인 단계는 다음과 같습니다.

현재 노드를 루트 노드로 초기화합니다.

• 현재 문자가 현재 노드의 하위 노드에 없으면 문자열을 의미합니다.
• 현재 문자가 현재 노드의 하위 노드에 있고 문자열의 마지막 문자가 탐색된 경우 노드의 isLeaf를 false로 표시합니다. 현재 노드의 하위 노드에 있고 아직 문자열의 마지막 문자로 이동하지 않은 다음 해당 노드로 이동합니다.
• 노드를 삭제한 후 현재 노드의 하위 노드가 비어 있고 isLeaf가 false인 경우 노드의 상위 노드를 계속 삭제합니다.
• 다음은 문자열 "apple"을 삭제하는 예와 그 실행 과정이다.

Golang은 접두사 트리를 구현합니다.

이전 설명에 따르면 Golang을 사용하여 접두사 트리를 구현할 수 있습니다.
3. 코드는 다음과 같습니다.

type Trie struct {
    children map[byte]*Trie
    isLeaf   bool
}

func NewTrie() *Trie {
    return &Trie{children: make(map[byte]*Trie)}
}

func (t *Trie) Insert(word string) {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            curr.children[c] = NewTrie()
        }
        curr = curr.children[c]
    }
    curr.isLeaf = true
}

func (t *Trie) Search(word string) bool {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return false
        }
        curr = curr.children[c]
    }
    return curr.isLeaf
}

func (t *Trie) Delete(word string) {
    nodes := make([]*Trie, 0)
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return
        }
        nodes = append(nodes, curr)
        curr = curr.children[c]
    }
    curr.isLeaf = false
    if len(curr.children) > 0 {
        return
    }

    for i := len(nodes) - 1; i >= 0; i-- {
        node := nodes[i]
        delete(node.children, word[i])
        if len(node.children) > 0 || node.isLeaf {
            return
        }
    }
}

코드에서 NewTrie() 함수는 새로운 접두사 트리 노드를 만드는 데 사용됩니다. Insert() 함수는 Search()에 문자열을 삽입하는 데 사용됩니다. 함수는 문자열을 찾는 데 사용됩니다. 접두사 트리에 존재하는지 여부는 문자열을 삭제하는 데 사용됩니다.

요약

접두사 트리는 문자열을 저장하고 검색하는 효율적인 데이터 구조입니다. 본 글에서는 Prefix Tree의 기본 개념과 기본 동작을 소개하고, Golang을 통해 Prefix Tree의 삽입, 검색, 삭제 기능을 구현합니다. 이 글을 공부한 후 독자들이 접두사 트리에 대한 이해를 심화하고 Golang을 사용하여 다른 효율적인 데이터 구조를 구현할 수 있기를 바랍니다.

위 내용은 접두사 트리 golang 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!