Mantendo uma ordem eficiente, na qual é possível inserir elementos "entre" outros dois elementos na ordem?

Imagine que eu tenho um pedido em vários elementos como este:

Onde uma flecha $X \leftarrow Y$ significa $X < Y$. Também é transitivo:$\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$.

Para responder com eficiência a consultas como $A \stackrel {?}{<} D$, é necessário algum tipo de rotulagem ou estrutura de dados. Por exemplo, você pode numerar os nós da esquerda para a direita e, portanto, pode simplesmente fazer uma comparação de números inteiros para responder à consulta:$A \stackrel {?}{<} D \implies 1 < 4 \implies T$. Seria algo como isto:

Onde o número é o pedido e a letra é apenas um nome.

Mas e se você precisasse inserir elementos "entre" dois outros elementos na ordem, assim:

Como você pode manter essa ordem? Com a numeração simples, você encontra o problema de que não há números inteiros "entre"$2,3$ usar.

Isso é conhecido como o problema "manutenção da ordem" . Existe uma solução relativamente simples usando$O(1)$tempo amortizado para consultas e inserções. Agora, com "relativamente simples", quero dizer que você precisa entender alguns blocos de construção, mas que depois de obtê-los, o resto não é difícil de ver.

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

A ideia básica é uma estrutura de dados em dois níveis. O nível superior é como a solução em árvore AVL da Realz Slaw, mas

• Os nós são rotulados diretamente com cadeias de bits de comprimento $O(\lg n)$com uma ordem que corresponda à ordem deles na árvore. A comparação, portanto, leva tempo constante

• Uma árvore com menos rotações do que uma árvore AVL é usada, como uma árvore de bode expiatório ou uma árvore com equilíbrio de peso, para que as novas rotulagens ocorram com menos frequência.

O nível inferior são as folhas da árvore. Esse nível usa o mesmo comprimento de rótulos,$O(\lg n)$, mas mantém apenas $O(\lg n)$itens em cada folha em uma lista vinculada simples. Isso fornece bits extras suficientes para re-rotular agressivamente.

As folhas ficam muito grandes ou muito pequenas a cada $O(\lg n)$ inserções, induzindo uma alteração no nível superior, o que leva $O(\lg n)$ tempo amortizado ($\Omega(n)$pior caso). Amortizado, isso é apenas$O(1)$.

Estruturas muito mais complexas existem para executar atualizações em $O(1)$ pior das hipóteses.

Em vez de numeração simples, você pode distribuir os números por um intervalo grande (de tamanho constante), como número inteiro mínimo e máximo de um número inteiro da CPU. Então você pode continuar colocando os números "no meio" calculando a média dos dois números ao redor. Se os números ficarem muito lotados (por exemplo, você acabará com dois números inteiros adjacentes e não houver um número intermediário), poderá renumerar uma vez toda a ordem inteira, redistribuindo os números uniformemente no intervalo.

Obviamente, você pode ter a limitação de que todos os números dentro do intervalo da constante grande são usados. Em primeiro lugar, isso geralmente não é um problema, pois o tamanho inteiro em uma máquina é grande o suficiente para que, se você tivesse mais elementos, provavelmente não caberia na memória. Mas se for um problema, você pode simplesmente renumerá-los com um intervalo inteiro maior.

Se a ordem de entrada não for patológica, esse método poderá amortizar as renumerações.

Responder a consultas

Uma simples comparação de números inteiros pode responder à consulta $\left(X \stackrel{?}{<}Y\right)$.

O tempo de consulta seria muito rápido ( $\mathcal{O}\left(1\right)$) se estiver usando números inteiros da máquina, pois é uma comparação inteira simples. Usar um intervalo maior exigiria números inteiros maiores e a comparação levaria$\mathcal{O}\left(\log{|integer|}\right)$.

Inserção

Em primeiro lugar, você manteria a lista vinculada da ordem, demonstrada na pergunta. A inserção aqui, dados os nós para colocar o novo elemento no meio, seria$\mathcal{O}\left(1\right)$.

Rotular o novo elemento geralmente seria rápido $\mathcal{O}\left(1\right)$porque você calcularia o novo número facilmente, calculando a média dos números ao redor. Ocasionalmente, você pode ficar sem números "no meio", o que acionaria o$\mathcal{O}\left(n\right)$ procedimento de renumeração de tempo.

Evitando renumeração

Você pode usar flutuadores em vez de números inteiros; portanto, quando você obtém dois números inteiros "adjacentes", eles podem ser calculados como média. Assim, você pode evitar a renumeração ao enfrentar dois números inteiros: apenas divida-os ao meio. No entanto, eventualmente, o tipo de ponto flutuante ficará sem precisão e dois flutuadores "adacentes" não poderão ser calculados pela média (a média dos números circundantes provavelmente será igual a um dos números circundantes).

Da mesma forma, você pode usar um número inteiro "casa decimal", onde você mantém dois números inteiros para um elemento; um para o número e um para o decimal. Dessa forma, você pode evitar a renumeração. No entanto, o número inteiro decimal eventualmente excederá.

Usar uma lista de números inteiros ou bits para cada rótulo pode evitar completamente a renumeração; isso é basicamente equivalente ao uso de números decimais com comprimento ilimitado. A comparação seria feita lexicograficamente, e os tempos de comparação aumentarão para o comprimento das listas envolvidas. No entanto, isso pode desequilibrar a rotulagem; alguns rótulos podem exigir apenas um número inteiro (sem decimal), outros podem ter uma lista de comprimento longo (decimais longos). Isso é um problema e a renumeração também pode ajudar aqui, redistribuindo a numeração (aqui listas de números) uniformemente em um intervalo escolhido (intervalo aqui possivelmente significando o comprimento das listas) para que, após essa renumeração, as listas tenham o mesmo comprimento .

Este método é realmente usado neste algoritmo ( implementação , estrutura de dados relevante ); no decorrer do algoritmo, uma ordem arbitrária deve ser mantida e o autor usa números inteiros e renumeração para fazer isso.

Tentar manter os números torna seu espaço chave um pouco limitado. Pode-se usar seqüências de comprimento variável, usando a lógica de comparação "a" <"ab" <"b". Ainda há dois problemas a serem resolvidos A. As chaves podem se tornar arbitrariamente longas B. A comparação de chaves longas pode se tornar cara

Você pode manter uma árvore AVL sem chave ou semelhante.

Funcionaria da seguinte maneira: A árvore mantém uma ordem nos nós da mesma forma que uma árvore AVL normalmente, mas em vez da chave determinar onde o nó "deve" se encontrar, não há chaves e você deve inserir explicitamente os nós "após "outro nó (ou em outras palavras" entre "dois nós), em que" depois "significa que vem depois dele na travessia ordenada da árvore. A árvore, portanto, manterá a ordem para você naturalmente e também se equilibrará, devido às rotações integradas do AVL. Isso manterá tudo uniformemente distribuído automaticamente.

Inserção

Além da inserção regular na lista, conforme demonstrado na pergunta, você manteria uma árvore AVL separada. A inserção na própria lista é$\mathcal{O}\left(1\right)$, como você tem os nós "antes" e "depois".

O tempo de inserção na árvore é $\mathcal{O}\left(\log {n}\right)$, o mesmo que inserção em uma árvore AVL. A inserção envolve ter uma referência ao nó que você deseja inserir depois e você simplesmente insere o novo nó à esquerda do nó mais à esquerda do filho direito; esse local é "próximo" na ordenação da árvore (é o próximo no percurso em ordem). Em seguida, faça as rotações típicas do AVL para reequilibrar a árvore. Você pode executar uma operação semelhante para "inserir antes"; isso é útil quando você precisa inserir algo no início da lista e não há um nó "antes".

Responder a consultas

Para responder a consultas de $\left(X \stackrel{?}{<}Y\right)$, você simplesmente encontra todos os ancestrais de $X$ e $Y$na árvore, e você analisa a localização de onde na árvore os ancestrais divergem; o que diverge para a "esquerda" é o menor dos dois.

Este procedimento leva $\mathcal{O}\left(\log{n}\right)$tempo subindo na árvore até a raiz e obtendo as listas de ancestrais. Embora seja verdade que isso pareça mais lento que a comparação com números inteiros, a verdade é que é a mesma; somente essa comparação inteira em uma CPU é limitada por uma constante grande para torná-la$\mathcal{O}\left(1\right)$; se você exceder essa constante, precisará manter vários números inteiros ($\mathcal{O}\left(\log{n}\right)$ inteiros, na verdade) e faça o mesmo $\mathcal{O}\left(\log{n}\right)$comparações. Como alternativa, você pode "vincular" a altura da árvore em uma quantidade constante e "trapacear" da mesma maneira que a máquina faz com números inteiros: agora as consultas parecerão$\mathcal{O}\left(1\right)$.

Demonstração da operação de inserção

Para demonstrar, você pode inserir alguns elementos com seus pedidos na lista da pergunta:

Passo 1

Começar com $D$

Lista:

Árvore:

Passo 2

Inserir $C$, $\emptyset < C < D$.

Lista:

Árvore:

Observe, você coloca explicitamente $C$ "antes" $D$, não porque a letra C esteja antes de D, mas porque $C < D$ na lista.

etapa 3

Inserir $A$, $\emptyset < A < C$.

Lista:

Árvore:

Rotação AVL:

Passo 4

Inserir $B$, $A < B < C$.

Lista:

Árvore:

Não são necessárias rotações.

Etapa 5

Inserir $E$, $D < E < \emptyset$

Lista:

Árvore:

Etapa 6

Inserir $F$, $B < F < C$

Nós colocamos isso "depois" $B$ na árvore, neste caso, simplesmente anexando-o ao $B$está certo; portanto$F$ agora é logo depois $B$ no percurso em ordem da árvore.

Lista:

Árvore:

Rotação AVL:

Demonstração da operação de comparação

$A \stackrel{?}{<} F$

ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

$D \stackrel{?}{<} F$

ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

$B \stackrel{?}{<} A$

ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

Fontes gráficas

• gist.github.com/realazthat/9299877a83cba4720aec