Estou pensando há algum tempo sobre como implementar um deque (ou seja, uma fila dupla) como uma estrutura de dados imutável.

Parece haver diferentes maneiras de fazer isso. ATÉ ONDE SEI,estruturas de dados imutáveis são geralmente hierárquicas, para que partes importantes possam ser reutilizadas após a modificação de operações como inserção ou remoção de um item.

Eric Lippert temdois artigos em seu blog sobre esse tópico, juntamente com exemplos de implementações em C #.

As duas implementações dele me parecem mais elaboradas do que é realmente necessário. Os deques não podiam simplesmente ser implementados como árvores binárias, onde os elementos só podem ser inseridos ou removidos à esquerda "(ofrente) e no próprio "direito" (ode volta) da árvore?

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

Além disso, a árvore seria mantida razoavelmente equilibrada com as rotações:

rotações corretas na inserção na frente ou na remoção pela parte traseira erotações à esquerda após remoção da frente ou inserção na parte de trás.

Eric Lippert é, na minha opinião, uma pessoa muito inteligente a quem eu respeito profundamente, mas ele aparentemente não considerou essa abordagem. Assim, eu me pergunto, foi por uma boa razão? Minha maneira sugerida de implementar deques é ingênua?