보르

Bor는 가장자리에 기호가 있는 루트 트리인 일련의 문자열을 저장하기 위한 데이터 구조입니다. < /사업부>
각 붕소 정점은 추가된 문자열의 접두사에 해당합니다. 이 접두사 자체는 루트에서 이 꼭짓점까지 경로의 가장자리에 문자를 순차적으로 작성하여 얻습니다. 동시에 정확히 하나의 꼭짓점이 각각의 기존 접두사에 해당합니다. Bor 루트는 빈 문자열에 해당합니다.

{be, bee, can, cat, cd}에 대한 붕소 예



주황색은 세트 자체의 단어에 해당하는 정점을 나타냅니다. 이를 터미널이라고 합니다.

아래는 붕소를 저장하고 여기에 줄을 추가하는 코드입니다. 이 방법은 배열을 통해 보어를 저장합니다. 교육용 작업 코드에 표시되는 포인터를 통한 구현도 있습니다.
  // 고려된 단어의 알파벳 크기 const int 알파 = 26; // 드릴 상단 구조 구조체 노드{ // 인접 테이블 형식의 모서리 벡터, 즉: // next[0] - 문자 번호 0('a') 위로 점프할 때의 자식 // next[1] - 문자 번호 1 위로 점프할 때의 자식('b') // 등. 벡터다음; // 추가 옵션 // 이 경우 정점 h의 높이와 종단 플래그 정수 h; 부울항;; 노드(정수 h) { next.resize(alph, -1); // 처음에는 가장자리가 없습니다. 이것->h = h; // 높이가 지정된 것과 같음 용어=거짓; // top은 기본적으로 터미널이 아닙니다. } }; // 정점 목록, 처음에는 높이가 0인 루트 vector<노드> trie(1, 노드(0)); // boron에 문자열을 추가하는 함수 void add(const string& s) { 정수 V = 0; // 루트부터 시작하여 현재 정점의 번호 forn(i, (int)s.size()) { int c = s[i] - 'a';; // 문자열에서 현재 문자의 번호를 얻습니다. // 원하는 전환이 아직 존재하지 않으면 새 전환을 만듭니다. if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // 새로운 정점 번호는   // 현재 드릴 크기(0 번호 지정) trie.push_back(노드(trie[v].h + 1)); // 높이가 1 더 높은 새 정점을 만듭니다. } v = 트리[v].다음[c]; // 원하는 가장자리를 따라 이동 } // 정상에 도달했을 때,   // 전체 문자열과 일치하는   // 그런 다음 터미널로 표시 trie[v].term = 참; }
붕소에서 행 삭제를 지원해야 하는 경우 부정직한 것으로 판명될 수 있습니다. 즉, 단순히 터미널 플래그를 제거하고(또는 플래그 대신 변수 번호를 저장해야 할 수도 있음) 붕소 트리 자체를 변경하지 않은 상태로 둡니다.

따라서 삽입/검색/불공정 삭제는 질의 문자열의 길이부터 직선적으로 작용한다.

최악의 경우 Boron 자체는 O(n|Σ|) 메모리를 차지합니다. 여기서 n은 모든 문자열의 총 길이이고 Σ > - 사용된 문자열의 알파벳.