Existe uma estrutura de dados para manipulação rápida de listas e consultas de pedidos?

9

Temos um conjunto, , de listas de elementos do conjunto . Cada elemento de aparece em uma lista única em . Estou procurando uma estrutura de dados que possa executar as seguintes atualizações: $L$ $N = \{ 1, 2, 3, ..., n \}$ $N$ $L$

$concat(x, y)$ : concatena a lista que contém no final da lista que contém $y$ $x$
$split(x)$ : divide a lista que contém diretamente após $x$ $x$

Ele também precisa executar as seguintes consultas:

$follows(x, y)$ : retorna se e são o mesmo em relação e vem depois (mas não é necessariamente adjacente a ) $true$ $x$ $y$ $y$ $x$ $x$
$first(x)$ : retorna o primeiro elemento da lista que contém $x$
$next(x)$ : retorna o próximo elemento após na lista que contém $x$ $x$

Eu já criei uma estrutura de dados que executa essas atualizações em e consultas em . Estou mais interessado em saber se já existe ou não uma estrutura de dados que pode fazer isso (espero mais rápido?). $O(lg^2 (n))$ $O(lg (n))$

Motivação: as florestas direcionadas enraizadas podem ser representadas com dois desses conjuntos de listas e permitem o cálculo rápido da acessibilidade nessas florestas. Quero ver para que mais eles podem ser usados e se tudo isso já é conhecido.

ds.algorithms graph-algorithms ds.data-structures bbejot
fonte

11

Mantenha seus números inteiros em pular listas. As listas de ignorados normais são ordenadas por chave, mas as usaremos apenas como representação de sequências. Além disso, mantenha uma matriz de ponteiros de tamanho . Cada elemento da matriz deve apontar para um nó em uma lista de pulos. Eu acredito que isso suporta a em e todas as outras operações em . $n$ $next$ $O(1)$ $O(\lg n)$

Especificamente:

$concat$ ou duas listas de pulos leva tempo e, portanto, invalida no máximo ponteiros . $split$ $O(\lg n)$ $O(\lg n)$
$next$ basta seguir o ponteiro para a frente no nível da folha, levando tempo . $O(1)$
$first$ leva o tempo : siga os ponteiros até ficar preso e siga o ponteiro esquerdo. Quando você não pode mais seguir os ponteiros da esquerda, está no topo da sua lista de pulos. Siga os ponteiros para a folha e, em seguida, um ponteiro para a frente. Este é o primeiro elemento da lista. $O(\lg n)$
$follows$ é um pouco mais complicado. Prossiga como no para , mas registre uma lista dos valores em que você fica preso (ou seja, onde você não pode mais acompanhar os ponteiros). Vamos chamar essa lista de gravar um "rastreamento". Faça o mesmo com , mas siga os ponteiros da direita quando ficar preso, não da esquerda. Se preceder , seus traços se cruzarão. Os traços são do tamanho . Se cada elemento no rastreio for anotado com o nível travado, podemos verificar uma interseção no tempo . $first$ $y$ $x$ $x$ $y$ $O(\lg n)$ $O(\lg n)$

$next$ é o pior caso , todos os outros são com alta probabilidade . Eles podem ser usados na pior das hipóteses, usando listas de pulos deterministas. $O(1)$ $O(\lg n)$

Eu acho que pode ser tornado usando árvores ligadas ao nível da folha (2,5) e dando tapinhas nas espinhas. Para o truque de inicialização, consulte " Representações puramente funcionais de listas classificadas com possibilidade de catenismo " por Kaplan e Tarjan. $concat$ $O(\lg \lg n)$

jbapple
fonte

legal. Eu estava pensando em ignorar listas, mas não conseguia ver como seguir sem os valores-chave associados.

Sasho Nikolov

O (l g (n))

$O(lg(n))$

1

$O(n + m \log \log n)$ $n$ $m$

Shaun Harker
fonte

O (l g l g (n))

$O(lg lg(n))$

Existe uma estrutura de dados para manipulação rápida de listas e consultas de pedidos?

Respostas: