Arbres équilibrés simples avec O (1) concat?

Dans les pires cas purement fonctionnels , les listes triées caténables à temps constant , Brodal et al. présentent des arbres équilibrés purement fonctionnels avec O (1) concaténé et O (lg n) insèrent, suppriment et trouvent. La structure des données est quelque peu compliquée.

Existe-t-il un arbre de recherche équilibré plus simple avec O (1) concaténé, fonctionnel ou non?

functional-programming ds.data-structures jbapple
la source

Réponses:

Vous pouvez créer trivialement une structure de données avec O (1) temps de concaténation amorti , en réinsérant simplement tout d'un arbre sur l'autre lors de la concaténation (qui a un coût O (n log n), exactement le même que celui utilisé pour construire cet arbre dans la première place, donc le temps global est toujours O (n log n)), mais c'est de la triche.

Pour le pire des cas O (1), les auteurs affirment que c'était un problème ouvert pour n'importe quelle structure de données, donc je ne pense pas que vous allez trouver une réponse facile.

Alexandre Passos
la source

Je ne sais pas si Brodal et al. signifiait que c'était un problème ouvert, même dans un cadre éphémère. Parlez-vous de la phrase dans l'abstrait qui fait référence à "un problème ouvert posé par Kaplan et Tarjan"? Si c'est le cas, je pense qu'il ressort clairement du contexte de ce document que K&T disait que la question était ouverte dans une structure purement fonctionnelle.

jbapple

J'ai téléchargé le document, mais il indique clairement qu '"Ils [K&T] ont demandé si l'opération de jointure pouvait être mise en œuvre dans le pire des cas O (1) même dans un cadre éphémère, tout en prenant en charge les recherches et les mises à jour en temps logarithmique."

Blaisorblade

Bon point, Blaisorblade. J'ai raté cette phrase.

jbapple

n

$n$

O (n \log n)

$O(n \log n)$

O (n \log^{2} n)

$O(n \log^2 n)$

J'ai téléchargé l'article que vous mentionnez et il répond "non", au moins au moment de la publication de l'article. C'est pour deux raisons:

un document est nécessaire pour examiner correctement les travaux connexes, et ils le font dans l'introduction, avec un résumé sur la figure 1, qui dit "non". Du moins s'il a été publié dans une conférence réputée, mais il ressemble à cela (Brodal est cité à quelques reprises dans "Structures de données purement fonctionnelles" par C. Okasaki, une référence sur le sujet).

Cependant, ils mentionnent dans le texte un algorithme avec le temps de recherche O (log n log log n) et la concaténation en temps O (1), esquissé dans le papier K&T du STOC '96. Cela pourrait être intéressant pour vous.
- le défi ouvert de K&T qu'ils résolvent concerne les dictionnaires avec concaténation O (1) et recherche / insertion / suppression O (log N), même pour les structures éphémères.

Le point 1. garantit également que vous pouvez simplement rechercher des articles citant celui-ci pour trouver des résultats ultérieurs, ils devraient le citer.

Si la question avait une pertinence pratique (mais ce n'est pas censé l'être), je pense que les facteurs constants sont plus importants que la différence entre O (1) et O (log N) (comme discuté dans l'introduction aux algorithmes de Sedgewick), donc vous devez rechercher uniquement des repères pour le cas d'utilisation de votre application.

Blaisorblade
la source

ESOP est une conférence réputée, si c'est ce que vous vouliez dire.

Charles Stewart

C'était ma question, mais pour l'ESA, où le document est publié, pas ESOP (peut-être que vous vouliez dire cela). Je n'étais pas sûr de pouvoir compter sur le rang de la conférence. Cette page de classement officieuse suggère également que l'ESA est assez réputée: www3.ntu.edu.sg/home/assourav/crank.htm

Blaisorblade