Mostrar código-fonte de Árvore Burkhard-Keller

Um '''árvore''' '''Burkhard-Keller''' ou '''árvore BK''' é uma [[árvore métrica]] sugerida por [[Walter Austin Burkhard]] e [[Robert Keller]]{{Ref|BK73}}, especificamente adaptada para [[Espaço métrico|espaços métricos]] discretos.
Para simplicidade, vamos considerar uma [[Topologia discreta|métrica discreta]] com '''inteiros''' <math>d(x,y)</math>. Em seguida, uma árvore BK é definida da seguinte maneira. Um elemento arbitrário ''a'' é escolhido como nó raiz. Então, é usada uma função de distância que retorna um valor discreto para particionar os demais objetos do universo.<ref name="Nadvorny">{{citar tese |tipo=Dissertação |grau=Mestrado |sobrenome=Nadvorny |nome=César Feijó |titulo=TM-tree: um método de acesso para consultas por similaridade |publicado=Universidade Federal do Rio Grande do Sul |ano=2005 |lingua=pt}}</ref> O nó raiz pode ter zero ou mais subárvores. A ''k-ésima'' subárvore é recursivamente construída a partir de todos os elementos de ''b'' tais que <math>d(a,b) = k</math>. Árvores BK podem ser usadas para determinar correspondência aproximada de strings em um dicionário {{Ref|BN98}}. Existem variações dessa árvore, por exemplo, pode-se fazer a restrição de que todos pivôs de um mesmo nı́vel na árvore sejam o mesmo objeto.<ref name="Nadvorny" />

== Ver também ==
* [[Distância Levenshtein]] – a distância métrica comumente utilizada durante a criação de uma árvore BK

{{Referências}}

* {{note|BK73}} [http://doi.acm.org/10.1145/362003.362025 W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973]
* {{note|BCMW04}} R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees. In M. Crochemore and D. Gusfield, editors, 5th Combinatorial   Pattern Matching, LNCS 807, pages 198–212, Asilomar, CA, June 1994.
* {{note|BN98}}  [https://web.archive.org/web/20110825210139/http://reference.kfupm.edu.sa/content/f/a/fast_approximate_string_matching_in_a_di_269284.pdf Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98]

== Ligações externas ==
* Implementação em [https://github.com/vy/bk-tree Common Lisp] {{en}} de uma árvore BK com os resultados dos testes e gráficos de desempenho.
* Uma explicação de Árvores BK e a sua relação com espaços métrica [http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees] {{en}}
* Uma explicação sobre Árvores BK, com uma implementação em C#[http://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/] {{en}}
* Implementação de uma árvore BK em [[Lua (linguagem de programação)|Lua]] [https://profan.github.io/lua-bk-tree/] {{en}}

{{Esboço-estrutura de dados}}
{{Árvores (estrutura de dados)}}

[[Categoria:Estruturas de dados]]
[[Categoria:!Esboços sobre ciência da computação]]