Ich habe eine Weile darüber nachgedacht, wie eine Deque (doppelseitige Warteschlange) als unveränderliche Datenstruktur implementiert werden kann.

Es scheint verschiedene Möglichkeiten zu geben, dies zu tun. SO VIEL ICH WEISS,immutable Datenstrukturen sind in der Regel hierarchisch, sodass große Teile davon nach dem Ändern von Vorgängen wie dem Einfügen oder Entfernen eines Elements wiederverwendet werden können.

Eric Lippert hatzwe Artike in seinem Blog zu diesem Thema, zusammen mit Beispielimplementierungen in C #.

Beide seiner Implementierungen erscheinen mir aufwändiger als eigentlich nötig. Deques können nicht einfach als binäre Bäume implementiert werden, bei denen Elemente nur ganz "links" eingefügt oder entfernt werden können (dasVorderseit) und ganz "rechts" (daszurüc) des Baumes?

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

Zusätzlich würde der Baum mit Rotationen einigermaßen ausgeglichen gehalten:

Rechtsdrehung beim Einsetzen vorne oder beim Entfernen von hinten undLinksdrehungen beim Entfernen von der Vorderseite oder beim Einsetzen von hinten.

Eric Lippert ist meiner Meinung nach ein sehr kluger Mensch, den ich zutiefst respektiere, aber er hat diesen Ansatz anscheinend nicht in Betracht gezogen. Ich frage mich also, ob das einen guten Grund hat. Ist meine vorgeschlagene Methode zur Implementierung von Deques naiv?