Encuentra el primer nulo en árbol binario con memoria limitada

Question

Tengo un árbol binario donde cada nodo puede tener un valor.

Quiero encontrar el nodo en el árbol que tenga un valor nulo y esté más cerca de la raíz. Si hay dos nodos con la misma distancia desde la raíz, cualquiera de los dos funcionará. Necesito minimizar el número de accesos de lectura al árbol binario. Suponga que la memoria de trabajo está limitada a solo k nodos.

DFS a profundidad k es exhaustivo pero no encontrará el nodo más cercano a menos que primero recorra todo el árbol. BFS encontrará el más cercano, pero podría fallar porque DFS puede encontrar nulos más profundos con la misma memoria.

Me gustaría tener el menor número de accesos de lectura al árbol y encontrar el nodo nulo más cercano.

(Necesitaré implementar esto en árboles n-way eventualmente, también, por lo que una solución general sería buena. No hay acceso de escritura al árbol, solo lea).

Answer 1

Es posible que desee ver Búsqueda por profundidad de profundización iterativa . Encontrará el nodo más cercano automáticamente, pero podrá alcanzar la misma profundidad que DFS. Sin embargo, utilizará más accesos de lectura.

También puede comenzar con BFS, y si no encuentra un valor nulo con la memoria permitida, ejecute DFS.

Answer 2

Implementaría un DFS con una simple poda de árboles. Por lo tanto, no es cierto que deba ejecutar todo el árbol.

Por ejemplo, si ha ubicado un valor nulo en la altura h, puede omitir los nodos que están en el mismo o posición más profunda.

Answer 3

Si no puede cambiar la estructura de datos, deberá leer cada nodo, primero en amplitud.

Si puede cambiar la estructura de datos, cada nodo podría registrar la profundidad relativa del primer nodo hijo nulo. (Cada uno se resuelve con los valores equivalentes de sus hijos).

Entonces sabes qué línea del árbol perseguir cuando buscas el nulo más temprano.

Answer 4

Hay una manera simple, si está dispuesto a almacenar su árbol en una matriz. En lugar de que cada nodo tenga punteros a sus hijos izquierdo y derecho, los hijos del nodo n son 2n + 1 y 2n + 2 en la matriz. (Y el padre del nodo n es (n-1) / 2, si n! = 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

Simplemente iterar a través de la matriz linealmente es equivalente a un BFS, pero con requisitos de espacio de O (1).

Esto puede extenderse fácilmente a árboles n-arios. por ejemplo, en un árbol ternario, el hijo izquierdo es 3n + 1, el centro es 3n + 2, el derecho es 3n + 3 y el padre es (n-1) / 3 si n! = 0.