プレフィックスツリーの golang 実装

プレフィックス ツリー (トライ) は、主に文字列の保存と照合に使用されるデータ構造です。この記事では、Golangを使ってプレフィックスツリーを実装する方法を紹介します。

1. プレフィックス ツリーとは何ですか?

プレフィックス ツリー (辞書ツリーとも呼ばれる) は、文字列コレクションを格納するために使用されるツリー状のデータ構造で、主に大量のテキストの中から特定の文字列を効率的に見つけるために使用されます。ハッシュ テーブルなどの他のデータ構造と比較すると、プレフィックス ツリーの時間計算量は O(k) です。ここで、k は検索する文字列の長さを表します。

プレフィックス ツリーの中心概念は「ノード」であり、各ノードには次の情報が含まれます:

• A 文字 c;
• A ブール値 isLeaf、示します。このノードで終わる文字列が存在するかどうか;
• 子ノードを格納するために使用されるハッシュ テーブルの子、およびキーは子ノードに対応する文字です。

#次の図は、4 つの文字列 (apple、apply、app、banana) を含むプレフィックス ツリーの例です。

# #プレフィックス ツリーの基本操作

プレフィックス ツリーの基本操作には、挿入、検索、削除が含まれます。

2.1 挿入

プレフィックス ツリーに文字列を挿入する場合、ルートノードからトラバースを開始する必要があります。

具体的な手順は次のとおりです:

現在のノードをルート ノードとして初期化します;
• 現在の文字がルート ノードでない場合は、文字列内の各文字を走査します。現在のノードの子ノード、新しいノードを作成して子ノードに保存します;
• 現在のキャラクターが現在のノードの子ノードにある場合は、そのノードに移動します;
• string 以降の文字を走査した後、現在のノードの isLeaf を true としてマークします。

次は、文字列「apple」の挿入例とその実行プロセスです。

2.2 Find

Find文字列の場合は、ルート ノードからトラバースを開始する必要があります。

具体的な手順は次のとおりです:

現在のノードをルート ノードとして初期化します;
• 現在の文字がルート ノードでない場合は、文字列内の各文字を走査します。現在のノードの子ノード、これは文字列がプレフィックス ツリーに存在しないことを意味します;
• 現在の文字が現在のノードの子ノードにある場合は、そのノードに移動します;
• 文字列を走査した後、現在のノードの isLeaf マークが true の場合、文字列がプレフィックス ツリーに存在することを意味し、それ以外の場合は、プレフィックスがプレフィックス ツリーに存在するが、文字列がプレフィックス ツリーに存在しないことを意味します。プレフィックスツリー。

次は、文字列「appl」とその実行プロセスを検索する例です。

2.3 削除

削除文字列の場合は、ルート ノードからトラバースを開始する必要があります。

具体的な手順は次のとおりです:

現在のノードをルート ノードとして初期化します;
• 現在の文字がルート ノードでない場合は、文字列内の各文字を走査します。現在のノードの子ノード、これは文字列がプレフィックス ツリーに存在しないことを意味します;
• 現在の文字が現在のノードの子ノードにあり、文字列の最後の文字が走査されている場合、ノードの isLeaf を false としてマークします;
• 現在の文字が現在のノードの子ノードにあり、文字列の最後の文字がまだトラバースされていない場合は、そのノードに移動します;
• ノードが削除された場合、現在のノードの子が空で isLeaf が false の場合、ノードの親ノードの削除を続行します。

以下は、文字列「apple」を削除する例とその実行プロセスです。

Golang はプレフィックス ツリーを実装します

前の説明によると、Golang を使用してプレフィックス ツリーを実装できます。

コードは次のとおりです:

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() 関数はプレフィックス ツリーに文字列が存在するかどうかを検索するために使用され、Delete() 関数は文字列を削除するために使用されます。

概要

プレフィックス ツリーは、文字列を保存および検索するための効率的なデータ構造です。この記事では、プレフィックス ツリーの基本概念とその基本操作を紹介し、Golang を使用してプレフィックス ツリーの挿入、検索、削除機能を実装します。読者がこの記事を学習することでプレフィックス ツリーについての理解を深め、Golang を使用して他の効率的なデータ構造を実装できるようになることを願っています。

以上がプレフィックスツリーの golang 実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。