Реализовать неизменную деку как сбалансированное бинарное дерево?

Некоторое время я размышлял о том, как реализовать deque (то есть двустороннюю очередь) в качестве неизменяемой структуры данных.

Кажется, есть разные способы сделать это. НАСКОЛЬКО МНЕ ИЗВЕСТНО,неизменные структуры данных, как правило, иерархические, так что основные его части можно использовать повторно после изменения таких операций, как вставка или удаление элемента.

Эрик Липперт имеетдва статьи в своем блоге на эту тему вместе с примерами реализации на C #.

Обе его реализации кажутся мне более сложными, чем на самом деле необходимо. Невозможно просто реализовать запросы в виде двоичных деревьев, где элементы могут быть вставлены или удалены только «слева» (фронт) и на самом «правильном»назадб) дерева?

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

Кроме того, дерево будет разумно сбалансировано с помощью поворотов:

правое вращение при вставке спереди или при удалении сзади, илевые повороты при удалении спереди или вставке сзади.

Эрик Липперт, на мой взгляд, очень умный человек, которого я глубоко уважаю, но он явно не рассматривал этот подход. Таким образом, я задаюсь вопросом, это было по уважительной причине? Является ли мой предложенный способ реализации deques наивным?

Ответы на вопрос(4)

Ваш ответ на вопрос