プレフィックスツリーの golang 実装-Golang-php.cn

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

WBOY

リリース： 2023-05-14 14:17:39

オリジナル

853 人が閲覧しました

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

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

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

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

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

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

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

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

2.1 挿入

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

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

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

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

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

2.2 Find

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

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

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

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

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

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 サイトの他の関連記事を参照してください。