BK树（Burkhard-Keller Tree）原理与实现

BK树是一种专门用于快速查找与给定字符串相似（在一定编辑距离内）的字符串的数据结构。它特别适用于拼写检查、模糊搜索等场景。编辑距离（Levenshtein距离）是指将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除、替换）次数。

1. BK树的核心思想
BK树利用编辑距离的度量性质（非负性、对称性、三角不等式）来组织数据。树中每个节点代表一个字符串，节点之间的边权值表示两个字符串间的编辑距离。通过这种结构，可以在搜索时快速剪枝，避免不必要的比较。

2. BK树构建过程
假设有一组字符串：["book", "books", "cake", "boo", "cape", "cart", "boon"]。

步骤：

• 选择根节点：通常随机选一个字符串，例如选"book"作为根节点。
• 插入其他节点：对于每个待插入字符串，计算它与当前节点的编辑距离d。如果当前节点的子节点中已有编辑距离为d的节点，则递归进入该子节点继续插入；否则，创建一个新的子节点，边权为d。

详细构建示例：

1. 根节点："book"
2. 插入"books"：与"book"的编辑距离=1（插入's'）。根节点无距离1的子节点，因此创建子节点"books"，边权=1。
3. 插入"cake"：与"book"的编辑距离=4。根节点无距离4的子节点，创建子节点"cake"，边权=4。
4. 插入"boo"：与"book"的编辑距离=1（删除'k'）。根节点已有距离1的子节点"books"，递归将"boo"插入以"books"为根的子树。
   • 在"books"子树中："boo"与"books"的编辑距离=1（删除's'）。"books"无距离1的子节点，创建子节点"boo"，边权=1。
5. 插入"cape"：与"book"的编辑距离=4。根节点已有距离4的子节点"cake"，递归插入到"cake"的子树。
   • 在"cake"子树中："cape"与"cake"的编辑距离=1（替换'k'为'p'）。"cake"无距离1的子节点，创建子节点"cape"，边权=1。
6. 插入"cart"：与"book"的编辑距离=4。根节点有距离4的子节点"cake"，递归插入。
   • 在"cake"子树中："cart"与"cake"的编辑距离=2（替换'k'为'r'，插入't'）。"cake"无距离2的子节点，创建子节点"cart"，边权=2。
7. 插入"boon"：与"book"的编辑距离=1（替换'k'为'n'）。根节点有距离1的子节点"books"，递归插入。
   • 在"books"子树中："boon"与"books"的编辑距离=2（替换's'为'n'，删除's'？注意：正确编辑是替换'k'为'n'，但比较对象是"books"，需重新计算）。实际上：
     • "boon"与"books"的编辑距离：b=b, o=o, o=o, n≠k（替换），长度一致，因此距离=1（一次替换）。"books"无距离1的子节点（已有"boo"距离1），创建子节点"boon"，边权=1。

最终树结构（括号内为编辑距离）：

         book
        /    \
      1(books)  4(cake)
      /        /    \
    1(boo)  1(cape) 2(cart)
    /
  1(boon)

3. BK树搜索过程
搜索与目标字符串Q编辑距离不超过k的所有字符串。从根节点开始，递归遍历所有满足条件的子树。

搜索算法：

1. 从根节点开始，计算当前节点字符串S与Q的编辑距离d。
2. 如果d ≤ k，将S加入结果集。
3. 递归遍历所有子节点，其中子节点的边权值在区间[d-k, d+k]内。因为根据三角不等式，只有这些子节点可能包含满足条件的字符串。

示例：在以上树中搜索Q="cane"，k=1（允许最多1次编辑）。

1. 根节点"book"：与"cane"的编辑距离d=4。
   • d=4 > k=1，不加入结果。
   • 需遍历边权在[4-1, 4+1] = [3,5]的子节点。根节点有边权4的子节点"cake"。
2. 进入"cake"子树："cake"与"cane"的编辑距离d=1（替换'k'为'n'）。
   • d=1 ≤ k=1，将"cake"加入结果。
   • 需遍历边权在[1-1, 1+1] = [0,2]的子节点。"cake"有边权1的子节点"cape"和边权2的子节点"cart"。
3. 进入"cape"子树："cape"与"cane"的编辑距离d=1（替换'p'为'n'）。
   • d=1 ≤ k=1，将"cape"加入结果。
   • 遍历边权在[0,2]的子节点（无）。
4. 进入"cart"子树："cart"与"cane"的编辑距离d=2（替换'r'为'n'，'t'为'e'？实际计算：c=c, a=a, r≠n（替换），t≠e（替换），距离=2）。
   • d=2 > k=1，不加入结果。
   • 遍历边权在[2-1,2+1]=[1,3]的子节点（无）。
5. 搜索结束，结果集为["cake", "cape"]。

4. 时间复杂度分析

• 构建：最坏情况O(n²)（树退化为链），但平均情况下由于编辑距离的度量性质，树高通常为O(log n)，构建复杂度为O(n log n)。
• 搜索：取决于k和字符串分布，平均复杂度可优于暴力比较的O(n)。

5. 实现要点

• 节点结构：包含字符串、子节点字典（键为编辑距离，值为子节点指针）。
• 编辑距离计算：使用动态规划算法，时间复杂度O(mn)，其中m、n为字符串长度。
• 优化：可通过限制最大编辑距离或使用阈值提前终止来加速搜索。

BK树通过度量空间的特性高效组织数据，特别适用于字典规模大、搜索阈值k较小的场景，是模糊匹配中的经典数据结构。