Trouver la première valeur null dans l'arborescence binaire avec une mémoire limitée

Question

J'ai un arbre binaire où chaque nœud peut avoir une valeur.

Je souhaite trouver dans l'arborescence le nœud ayant la valeur null et se rapprochant le plus de la racine. S'il y a deux nœuds à la même distance de la racine, l'un ou l'autre fera l'affaire. J'ai besoin de minimiser le nombre d'accès en lecture à l'arbre binaire. Supposons que la mémoire de travail soit limitée à k nœuds.

DFS à la profondeur k est exhaustif mais ne trouvera pas le nœud le plus proche à moins que je ne parcoure d'abord l'arbre en entier. BFS trouvera le plus proche, mais cela peut échouer car DFS peut trouver des valeurs NULL plus profondes avec la même mémoire.

J'aimerais avoir le plus petit nombre d'accès en lecture à l'arbre et trouver le nœud nul le plus proche.

(Je devrai éventuellement implémenter ceci dans plusieurs arbres, alors une solution générale serait bien. Pas d'accès en écriture à l'arbre, il suffit de le lire.)

Answer 1

Vous pouvez consulter la Recherche approfondie en profondeur par la première fois . Il trouvera automatiquement le nœud le plus proche, mais pourra atteindre la même profondeur que DFS. Il utilisera cependant plus d’accès en lecture.

Vous pouvez également commencer par BFS et, si vous ne trouvez pas un null avec la mémoire autorisée, exécutez DFS.

Answer 2

Je mettrais en œuvre un DFS avec un élagage simple. Ainsi, il n’est pas vrai que vous devez exécuter l’arbre entier.

Par exemple, si vous avez localisé une valeur nulle à la hauteur h, vous pouvez ignorer les nœuds situés dans le même ou position plus profonde.

Answer 3

Si vous ne pouvez pas modifier la structure de données, vous devrez lire chaque nœud - largeur d'abord.

Si vous pouvez modifier la structure de données, chaque nœud peut enregistrer la profondeur relative du premier nœud enfant null. (Chacun travaille à partir des valeurs équivalentes de ses enfants).

Ensuite, vous savez quelle ligne de l’arbre à chasser lorsque vous recherchez la valeur null la plus ancienne.

Answer 4

Il existe un moyen simple, si vous souhaitez stocker votre arborescence dans un tableau. Au lieu que chaque nœud ait des pointeurs sur ses enfants gauche et droit, les enfants du nœud n sont 2n + 1 et 2n + 2 dans le tableau. (Et le parent du noeud n est (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
...,
};

Simplement parcourir le tableau linéairement équivaut à un BFS, mais avec un espace requis de O (1).

Cela peut facilement être étendu aux arbres n-aire. Par exemple, dans un arbre ternaire, l'enfant de gauche est 3n + 1, le centre est 3n + 2, droit est 3n + 3 et le parent est (n-1) / 3 si n! = 0.