collection séquentielle fonctionnelle rapide

Question

Je suis à la recherche d'une structure de données de collecte séquentielle (à savoir quelque chose qui peut être considéré comme une liste) pour lesquels:

1. Les opérations d'épissage de base (ajouter ou supprimer des éléments partout dans le list) sont amortis O (log N) ou mieux (donc un tableau ne se qualifie pas, car il est seulement rapide d'ajouter ou de supprimer des éléments à la fin). Ceci est vrai même s'il est utilisé de manière fonctionnelle, c'est-à-dire que les opérations sont non destructives (une liste doublement chaînée n'est donc pas qualifiée car pour une opération non destructive, vous devez copier toute la liste. Je vois).

Existe-t-il une structure de données répondant à ces critères?

Answer 1

Oui, vous voulez un arbre binaire équilibré. Ils viennent dans des saveurs purement fonctionnelles et sont bons non seulement pour les cartes triées mais aussi pour les séquences.

L'adaptation requise consiste à mapper des index de séquence à des valeurs. Pour éviter une renumérotation coûteuse sur les opérations de mi-séquence, ne représentez pas les clés directement; Au lieu de cela, chaque nœud doit stocker le nombre total de nœuds dans son sous-arbre gauche. Au cours d'une traversée vers le bas, conservez l'index du nœud actuel en ajoutant le nombre chaque fois que la traversée passe à droite.