BK-tree

A BK-tree is a <a href="/facts/Metric_trees/wmyxmJ5x">metric tree</a> suggested by Walter Austin Burkhard and Robert M. Keller<a href="https://en.wikipedia.org/wiki/BK-tree#endnote_BK73">[1]</a> specifically adapted to discrete <a href="/facts/Metric_space/gnBBRXtc">metric spaces</a>.
For simplicity, consider integer discrete metric 
 
 
 
 d
 (
 x
 ,
 y
 )
 
 
 {\displaystyle d(x,y)}
 
. Then, BK-tree is defined in the following way. An arbitrary element a is selected as root node. The root node may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that 
 
 
 
 d
 (
 a
 ,
 b
 )
 =
 k
 
 
 {\displaystyle d(a,b)=k}
 
. BK-trees can be used for <a href="/facts/Approximate_string_matching/aotktvNI">approximate string matching</a> in a dictionary.<a href="https://en.wikipedia.org/wiki/BK-tree#endnote_BN98">[2]</a>[example needed]

BK-tree open-in-new

BK-tree