Árvore Burkhard-Keller

Um árvore Burkhard-Keller ou árvore BK é uma árvore métrica sugerida por Walter Austin Burkhard e Robert Keller, especificamente adaptada para espaços métricos discretos. Para simplicidade, vamos considerar uma métrica discreta com inteiros ${\displaystyle d(x,y)}$. 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.[1] 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 ${\displaystyle d(a,b)=k}$. Árvores BK podem ser usadas para determinar correspondência aproximada de strings em um dicionário . 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.[1]