algorithm - recorrido - Árboles binarios: Obteniendo la ruta de un elemento desde su firma

operaciones con arboles binarios

Question

Supongamos que tiene un árbol binario que clasifica las imágenes. Cada nodo es una prueba binaria diferente. Cuando se alimenta una imagen al árbol, se genera una ruta única a través del árbol.

Un camino se describe como una palabra binaria que es tan larga como la profundidad del árbol.

Por ejemplo, para un árbol binario de 2 etapas, un ejemplo de ruta sería (0,1) ((izquierda, derecha), terminando así en la segunda hoja del árbol desde la izquierda).

También suponemos que para cualquier imagen que se alimenta al árbol, todas las pruebas de nodo son ejecutables. Por lo tanto, podemos definir una firma para cualquier imagen: esta firma es una palabra binaria cuya longitud es la cantidad de nodos.

Por ejemplo, para un árbol binario de 2 etapas, un ejemplo de firma sería s = {0,1,1}

s[i] es el resultado binario de la prueba del i-ésimo nodo.

Estoy buscando una manera de obtener la ruta de una imagen desde su firma.

Una forma ingenua de hacerlo sería pasar de un índice a otro de la firma con una longitud de salto decreciente apropiada.

Sin embargo, me pregunto si podría haber un cálculo bit a bit que podría arrojar el resultado (los índices en la firma se pueden reorganizar si es necesario).

es posible? Si es así, ¿cómo?

Answer 1

Con 1 etapa hay 1 prueba.

Con 2 etapas hay 1 + 2 pruebas.

Con 3 etapas hay 1 + 2 + 4 pruebas.

Con 4 etapas hay 1 + 2 + 4 + 8 pruebas.

Con 5 etapas hay 1 + 2 + 4 + 8 + 16 = 31 pruebas.

Un enfoque para calcular la ruta más rápido es probar el primer bit, y luego extraer el conjunto correspondiente de 15 bits que se correlaciona con las 4 etapas siguientes. Solo hay 2 ** 15 = 32768 opciones diferentes, por lo que la ruta se puede buscar en una tabla.

Pseudocódigo:

 if (x&(1<<30))
    x >>= 15;
 path = lookup[x & 0x7fff];

búsqueda es una matriz de 2 ** 15 de longitud que puede precalcular.