波尔

Bor是一种用于存储一组字符串的数据结构，它是一个边上有符号的有根树。 < /分区>
每个硼顶点对应于一些添加字符串的前缀。这个前缀本身是通过在从根到这个顶点的路径上的边上顺序写入字符得到的。同时，每个存在的前缀恰好对应一个顶点。 Bor根对应一个空字符串。

硼的例子 {be, bee, can, cat, cd}



橙色表示对应于集合本身的单词的顶点。它们被称为终端。

下面是存储硼​​并向其添加线条的代码。此方法通过数组存储钻孔。还有一种通过指针的实现，在训练任务的代码中给出。
  // 考虑单词的字母大小 const int alpha = 26; // 钻头顶部的结构 结构节点{ // 邻接表形式的边向量，即： // next[0] - 跳过字符号 0 ('a') 时的子节点 // next[1] - 跳过字符号 1 ('b') 时的子节点 // ETC。 向量下一个； // 额外选项 // 在这种情况下，顶点 h 的高度和终端标志 诠释 h; 布尔项；； 节点（int h）{ next.resize(alph, -1); // 最初没有边 this->h = h; // 高度等于指定的 术语=假； // top 默认不是终端 } }; // 顶点列表，初始根在零高度 矢量<节点>特里（1，节点（0））； // 向硼添加字符串的函数 void add(const string& s) { 整数 v = 0； // 当前顶点的序号，从根开始 forn(i, (int)s.size()) { int c = s[i] - 'a'; // 获取字符串中当前字符的个数 // 如果所需的转换尚不存在，那么我们将创建一个新的 如果（trie[v].next[c] == -1）{ trie[v].next[c] = (int)trie.size(); // 新的顶点号是   // 当前钻孔尺寸（带 0 编号） trie.push_back(节点(trie[v].h + 1)); // 再创建一个高度为 1 的新顶点 } v = trie[v].next[c]; // 沿着想要的边移动 } // 当我们到达顶部时，   // 匹配整个字符串，   // 然后将其标记为终端 trie[v].term = true; }
如果您需要支持从硼中删除行，那么它可能会被证明是不诚实的。也就是说，只需删除终端标志（或者，也许您需要存储一个可变数字而不是标志），并保持硼树本身不变。

因此，插入/搜索/不公平删除的工作时间与查询字符串的长度成线性关系。

Boron本身，在最坏的情况下，会占用O(n|Σ|)内存，其中n是所有字符串的总长度，Σ > - 所用字符串的字母表。