A '''Bk-tree''' is a [[metric trees|metric tree]] suggested by Burkhard and Keller {{ref|BK73}} specifically adapted to discrete [[metric space]]s.
For simplicity, let us consider '''integer''' discrete metric $\backslash varrho(x,y)$. Then, Bk-tree is defined in the following way. An arbitrary element ''a'' is selected as root node. Root node may have zero or more subtrees. The ''k-th'' subtree is recursively built of all elements ''b'' such that
$\backslash varrho(a,b)\; =\; k$. Bk-trees can be used for approximate string matching in a dictionary {{ref|BN98}}.
{{compu-sci-stub}}
== References and external links ==
* {{note|BK73}} W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
* {{note|BN98}} [http://www.dcc.uchile.cl/~gnavarro/ps/spire98.2.ps.gz Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98]
[[Category:Trees (structure)]]