Existe um equivalente a árvores de van Emde Boas para cordas?

Alguém que eu conheço está planejando implementar um editor de texto em um futuro próximo, o que me levou a pensar em que tipo de estruturas de dados são rápidas para um editor de texto. As estruturas mais utilizadas são aparentemente cordas ou tampões de abertura .

As árvores Van Emde Boas são praticamente as filas de prioridade mais rápidas, se você não se importa com um limite superior no número de itens que você pode colocar nela e um grande custo de inicialização. Minha pergunta é se existe alguma estrutura de dados tão rápida quanto a árvore de van Emde Boas, mas que suporta operações de editor de texto.

Precisamos apenas suportar até caracteres em nossa estrutura de dados (portanto, se log m = 32 , suportamos até 4 GB de caracteres ASCII). Nós somos permitidos $m$$\log m = 32$ tempo para inicializar uma nova estrutura de dados. Gostaríamos de apoiar as seguintes operações:$\sqrt{m}$

• Insira um caractere na posição em O ( log log m ) (aumentando assim a posição de cada caractere subsequente em 1).$i$$O(\log \log m)$
• Exclua um caractere na posição em O ( log log m ) .$i$$O(\log \log m)$
• Retorne o caractere na posição em O ( log log m ) .$i$$O(\log \log m)$

Portanto, insert (0, 'a') seguido de insert (0, 'b') resulta em "ba".

Ainda melhor seria o seguinte:

• Retorne um 'ponteiro' para algum índice em O ( log log m ) .$i$$O(\log \log m)$
• Dado um 'ponteiro', retorne o caractere nesta posição em .$O(1)$
• Dado um 'ponteiro', remova o caractere nesta posição em .$O(1)$
• Dado um 'ponteiro', adicione um caractere nesta posição em e retorne um ponteiro para a seguinte posição.$O(1)$
• (opcional) Dado um 'ponteiro', retorne um 'ponteiro' para o caractere próximo / anterior em .$O(1)$

$\Theta\left(\frac{\lg m}{\lg \lg m}\right)$

Dietz apresentou uma estrutura de dados em "Algoritmos ótimos para indexação de listas e classificação de subconjuntos" que atingem esse limite.