Bor

Bor ialah struktur data untuk menyimpan set rentetan, iaitu pokok berakar dengan simbol di tepi. < /div>
Setiap bucu boron sepadan dengan awalan beberapa rentetan tambahan. Awalan ini sendiri diperoleh dengan menulis aksara secara berurutan di tepi pada laluan dari akar ke puncak ini. Pada masa yang sama, tepat satu bucu sepadan dengan setiap awalan sedia ada. Akar bor sepadan dengan rentetan kosong.

Contoh boron untuk {be, bee, can, cat, cd}



Jingga menunjukkan bucu yang sepadan dengan perkataan daripada set itu sendiri. Ia dipanggil terminal.

Di bawah ialah kod untuk menyimpan boron dan menambah baris padanya. Kaedah ini menyimpan gerek melalui tatasusunan. Terdapat juga pelaksanaan melalui petunjuk, yang dibentangkan dalam kod tugas untuk latihan.
  // saiz abjad dalam perkataan yang dipertimbangkan const int alpha = 26; // struktur untuk bahagian atas gerudi struct Nod{ // vektor tepi dalam bentuk jadual bersebelahan, iaitu: // seterusnya[0] - kanak-kanak apabila melompat ke atas aksara nombor 0 ('a') // seterusnya[1] - kanak-kanak apabila melompat ke atas watak nombor 1 ('b') // dan lain-lain. vektorseterusnya; // Pilihan tambahan // dalam kes ini, ketinggian puncak h dan bendera terminaliti int h; istilah bool;; Nod(int h) { next.resize(alph, -1); // pada mulanya tanpa tepi ini->h = h; // ketinggian adalah sama dengan yang ditentukan istilah=salah; // atas bukan terminal secara lalai } }; // senarai bucu, pada mulanya akar pada ketinggian sifar vektor trie(1, Nod(0)); // fungsi untuk menambah rentetan pada boron void add(const string& s) { int v = 0; // nombor puncak semasa, bermula dari punca forn(i, (int)s.size()) { int c = s[i] - 'a'; // dapatkan nombor aksara semasa dalam rentetan // jika peralihan yang diingini belum wujud, maka kita akan buat yang baru jika (cuba[v].seterusnya[c] == -1) { trie[v].next[c] = (int)trie.size(); // nombor bucu baharu ialah   // saiz gerudi semasa (dengan penomboran 0) trie.push_back(Nod(trie[v].h + 1)); // buat bucu baharu dengan ketinggian 1 lagi } v = cuba[v].seterusnya[c]; // bergerak di sepanjang tepi yang dikehendaki } // apabila kita sampai ke puncak,   // yang sepadan dengan keseluruhan rentetan,   // kemudian tandakannya sebagai terminal cuba[v].istilah = benar; }
Sekiranya anda perlu menyokong pemadaman baris dari boron, maka ia mungkin akan menjadi tidak jujur. Iaitu, hanya keluarkan bendera terminal (atau, mungkin, bukannya bendera, anda perlu menyimpan nombor berubah-ubah), dan biarkan pokok boron itu sendiri tidak berubah.

Oleh itu, sisipan/carian/pemadaman tidak adil berfungsi dalam masa linear daripada panjang rentetan pertanyaan.

Boron itu sendiri, dalam kes yang paling teruk, akan menduduki memori O(n|Σ|), dengan n ialah jumlah panjang semua baris dan &Sigma ; > - abjad rentetan yang digunakan.