Quelle est la structure de données optimale pour un arbre de cartes.

Je cherche une structure de données, qui est essentiellement un arbre de cartes, où la carte à chaque nœud contient de nouveaux éléments, ainsi que les éléments de la carte de son nœud parent. Par carte ici, je veux dire une carte de programmation avec des clés et des valeurs, comme la carte dans la STL ou dict en python.

Par exemple, il pourrait y avoir un nœud racine:

root = {'car':1, 'boat':2}

et 2 enfants, chacun ajoutant un élément à la carte parent

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

Je voudrais que ce soit le plus économe en espace possible, c'est-à-dire que je ne veux pas stocker une copie complète de la carte résultante à chaque nœud, mais idéalement la recherche serait toujours O (log N), N étant le nombre total de des éléments au niveau du nœud, pas de l’arbre entier.

Je pensais qu'il y avait peut-être une fonction de hachage intelligente que je pourrais utiliser pour cela, mais je n'ai rien trouvé.

L'approche naïve consisterait à stocker les entrées nouvellement ajoutées dans une carte à chaque nœud, puis à remonter dans l'arborescence si rien n'est trouvé. Je n'aime pas ça car cela dépend de la profondeur de l'arbre.

$2^{mn}$

$O(\log N)$

$\Theta($$O(\lg\lg N)$$\Theta(\lg n)$

$x$$x$$x$$v$$v$

Pour une borne inférieure, notez que même une seule question lancinante est aussi difficile que le prédécesseur (voir les réductions de la recherche de prédécesseur colorée). Étant donné que les références papier ci-dessus montrent un comportement optimal de somme directe pour la recherche précédente, cela signifie que l'algorithme décrit ci-dessus est optimal pour toute ration entre le nombre de nœuds et le nombre total de clés.