Une alternative à deux arborescences AVL

Question

J'ai actuellement des données dont j'ai besoin triées de deux manières différentes, à partir d'une PoV de complexité temporelle et spatiale, existe-t-il une alternative au maintien de deux arbres, triés par date et par numéro d'identification? Je dois être capable de retourner les listes dans l'ordre des données, et les utilisateurs individuels par ID, et je préférerais ne pas avoir à traverser ou même pire, traverser et ensuite trier les retours de tableau.

Toute idée ou aide est très appréciée, merci!

Answer 1

Vous pouvez le faire dans une arborescence, mais vous obtiendrez des performances O (logN) uniquement pour la date. La récupération directe ID serait O (N) (c'est-à-dire traverser l'arbre entier pour trouver une correspondance exacte) de toute façon, puisque l'ordre serait indéterminé. Si votre ID peut être basé sur la date dont vous avez besoin (je veux dire si l'ID peut être généré en se basant sur la date), alors vous pouvez réduire la complexité temporelle O (N) à O (logN + M), où M - est un sous-ensemble d'ID pour une date particulière. En fonction de votre temps de réponse et de vos besoins en mémoire, vous pouvez conserver un seul arbre ou l'associer à un HashMap ID.

Answer 2

TreeMap implémente Red-Black tree qui est une alternative à AVL.

Answer 3

Vous pourriez faire avec un LinkedHashMap (objets stockés et récupérés dans l'ordre d'ajout ou last access + toutes les opérations HashMap standard avec la complexité O (1)).

Si vous avez besoin de modèles d'accès à la date plus complexes (plages, requêtes ponctuelles), vous pouvez utiliser la même idée mais avec un skip list au lieu d'une liste liée. Dans ce cas, l'accès par date sera O (logN).

Et puis il y a aussi une option pour construire le même (liste chaînée ou liste de choix) sur un arbre où vous mettez des valeurs par id.