Perlaksanaan golang pokok awalan

Pokok awalan (Trie) ialah struktur data yang digunakan terutamanya untuk penyimpanan dan pemadanan rentetan. Dalam artikel ini, kami akan memperkenalkan cara melaksanakan pokok awalan menggunakan Golang.

1. Apakah pokok awalan?

Pokok awalan, juga dipanggil pokok kamus, ialah struktur data berbentuk pepohon yang digunakan untuk menyimpan koleksi rentetan, terutamanya digunakan untuk mencari rentetan tertentu dengan cekap dalam sejumlah besar teks. Berbanding dengan struktur data lain seperti jadual cincang, kerumitan masa pokok awalan ialah O(k), dengan k mewakili panjang rentetan yang akan ditemui.

Konsep teras pepohon awalan ialah "Nod", setiap nod mengandungi maklumat berikut:

• a aksara c;
• nilai Boolean ialah Daun, Menunjukkan sama ada rentetan yang berakhir dengan nod ini wujud;
• Anak jadual cincang, digunakan untuk menyimpan nod anak, dan kuncinya ialah aksara yang sepadan dengan nod anak.

Rajah berikut ialah contoh pokok awalan yang mengandungi empat rentetan (epal, terapkan, aplikasi, pisang):

2. Operasi asas pepohon awalan

Operasi asas pepohon awalan termasuk sisipan, carian dan pemadaman:

2.1 Sisipan

Apabila memasukkan rentetan ke dalam pepohon awalan, kami perlu mula merentasi dari nod akar.

Langkah khusus adalah seperti berikut:

• Mulakan nod semasa sebagai nod akar; nod anak nod semasa , buat nod baharu dan simpan dalam nod kanak-kanak
• Jika aksara semasa berada dalam nod anak nod semasa, pindah ke nod itu; >Selepas melintasi aksara Selepas rentetan, tandakan isLeaf nod semasa sebagai benar.
• Berikut ialah contoh memasukkan rentetan "epal" dan proses pelaksanaannya:

2.2 Cari

Cari rentetan aksara, kita perlu mula merentasi dari nod akar.

Langkah-langkah khusus adalah seperti berikut:

Mulakan nod semasa sebagai nod punca; nod anak nod semasa , ini bermakna rentetan tidak wujud dalam pepohon awalan

Jika aksara semasa berada dalam nod anak nod semasa, pindah ke nod itu; 🎜>Selepas melintasi rentetan, jika Jika tanda isLeaf nod semasa adalah benar, ini bermakna rentetan itu wujud dalam pepohon awalan jika tidak, ia bermakna awalan wujud dalam pepohon awalan, tetapi rentetan itu tidak wujud dalam pokok awalan.

• Berikut ialah contoh mencari rentetan "appl" dan proses pelaksanaannya:
• 2.3 Padam

Padam rentetan aksara, kita perlu mula merentasi dari nod akar.

Langkah-langkah khusus adalah seperti berikut:

Mulakan nod semasa sebagai nod punca; nod anak nod semasa , ini bermakna rentetan tidak wujud dalam pepohon awalan

Jika aksara semasa berada dalam nod anak nod semasa dan aksara terakhir rentetan telah dilalui; , tandakan isLeaf bagi nod sebagai palsu; 🎜>Jika nod dipadamkan, semasa Jika anak nod kosong dan isLeaf adalah palsu, teruskan padamkan nod induk nod.

Berikut ialah contoh pemadaman rentetan "epal" dan proses pelaksanaannya:

• Golang melaksanakan pokok awalan
• Mengikut penerangan sebelum ini, kita boleh menggunakan Golang untuk melaksanakan pokok awalan.
• Kod adalah seperti berikut:

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
        }
    }
}

Dalam kod, fungsi NewTrie() digunakan untuk mencipta nod pokok awalan baharu fungsi Insert() digunakan untuk memasukkan rentetan ke dalam pepohon awalan; fungsi Cari() digunakan untuk mencari sama ada rentetan wujud dalam pepohon awalan () fungsi Delete() digunakan untuk memadam rentetan.

Ringkasan

Pokok awalan ialah struktur data yang cekap untuk menyimpan dan mencari rentetan. Artikel ini memperkenalkan konsep asas pepohon awalan dan operasi asasnya serta melaksanakan fungsi sisipan, carian dan pemadaman pepohon awalan melalui Golang. Saya berharap pembaca dapat mendalami pemahaman mereka tentang pepohon awalan melalui kajian artikel ini dan dapat menggunakan Golang untuk melaksanakan struktur data cekap yang lain.

Atas ialah kandungan terperinci Perlaksanaan golang pokok awalan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!