BK tree

A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller^[1] specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric 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 . BK-trees can be used for approximate string matching in a dictionary ^[2].