Bor

Bor è una struttura dati per memorizzare un insieme di stringhe, che è un albero con radici e simboli sui bordi. < /div>
Ogni vertice di boro corrisponde a un prefisso di qualche stringa aggiunta. Questo stesso prefisso si ottiene scrivendo in sequenza i caratteri sui bordi del percorso dalla radice a questo vertice. Allo stesso tempo, esattamente un vertice corrisponde a ciascun prefisso esistente. Bor root corrisponde a una stringa vuota.

Esempio di boro per {be, bee, can, cat, cd}



L'arancione indica i vertici che corrispondono alle parole dell'insieme stesso. Si chiamano terminali.

Di seguito è riportato il codice per conservare il boro e aggiungere linee ad esso. Questo metodo memorizza il foro attraverso un array. Esiste anche un'implementazione tramite puntatori, che viene presentata nel codice dell'attività per l'addestramento.
  // dimensione dell'alfabeto nelle parole considerate const int alfa = 26; // struttura per la parte superiore del trapano struct Nodo{ // vettore di spigoli sotto forma di tabella di adiacenza, ovvero: // next[0] - bambino quando si salta sul carattere numero 0 ('a') // next[1] - bambino quando si salta sul carattere numero 1 ('b') // eccetera. vettoresuccessivo; // Opzioni aggiuntive // in questo caso, l'altezza del vertice h e il flag di terminalita' int h; termine bool;; Nodo(int h) { next.resize(alph, -1); // inizialmente senza spigoli questo->h = h; // l'altezza è uguale a quella specificata termine=falso; // top non è il terminale per impostazione predefinita } }; // elenco di vertici, inizialmente root ad altezza zero vettore trie(1, Nodo(0)); // funzione per aggiungere una stringa al boro void add(const string& s) { intero v = 0; // numero del vertice corrente, partendo dalla radice forn(i, (int)s.size()) { int c = s[i] - 'a'; // ottiene il numero del carattere corrente nella stringa // se la transizione desiderata non esiste ancora, ne creeremo una nuova if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // il nuovo numero di vertice è   // dimensione del trapano corrente (con numerazione 0) trie.push_back(Node(trie[v].h + 1)); // crea un nuovo vertice con altezza 1 in più } v = trie[v].next[c]; // si sposta lungo il bordo desiderato } // quando siamo arrivati ​​in cima,   // che corrisponde all'intera stringa,   // quindi contrassegnalo come terminale trie[v].term = vero; }
Se hai bisogno di supportare l'eliminazione delle righe dal boro, probabilmente si rivelerà disonesto. Cioè, rimuovi semplicemente il flag terminale (o, forse, invece del flag, dovrai memorizzare un numero variabile) e lascia invariato l'albero di boro stesso.

Pertanto, inserimento/ricerca/cancellazione scorretta funzionano in tempo lineare dalla lunghezza della stringa di query.

Lo stesso boro, nel peggiore dei casi, occuperà O(n|Σ|) memoria, dove n è la lunghezza totale di tutte le stringhe, e Σ > - l'alfabeto delle stringhe utilizzate.