Почему нет циклов в Эрик Липперт Неизменяемое двоичное дерево?
Я только что посмотрел на простую реализацию Эриком Липпертом неизменяемого двоичного дерева , и у меня возник вопрос по этому поводу. Показав реализацию, Эрик заявляет, что
Обратите внимание, что еще одна приятная особенность неизменные структуры данных в том, что это невозможно случайно (или намеренно!) создать дерево, которое содержит цикл.
Кажется, что эта особенность реализации Эрика происходит не только от неизменности, но и от того факта, что дерево построено из листьев. Это естественно препятствует тому, чтобы у узла был любой из его предков как дети. Кажется, что если бы вы построили дерево в другом направлении, вы бы представили возможность циклов.
Прав ли я в своем мышлении, или невозможность циклов в этом случае проистекает только из неизменности? Учитывая источник, мне интересно, что я что-то упустил.
РЕДАКТИРОВАТЬ: Подумав еще немного, кажется, что наращивание из листьев может быть единственным способом создать неизменное дерево. Я прав?
3 ответа
Если вы используете неизменяемую структуру данных, в строгом (в отличие от ленивого) языке невозможно создать цикл; поскольку вы должны создавать элементы в определенном порядке, и после создания элемента вы не можете изменить его, чтобы он указывал на элемент, созданный позже. Таким образом, если вы создали узел n, а затем создали узел m, указывающий на n (возможно, косвенно), вы никогда не сможете завершить цикл, вызвав n, чтобы указать на m, так как вам не разрешено изменять n, и ничего, на что уже указывает n.
Да, вы правы в том, что вы можете создать неизменное дерево, только построив его из листьев; если вы начнете с корня, вам придется изменить корень, чтобы он указывал на его дочерние элементы при их создании. Только начиная с листьев и создавая каждый узел так, чтобы он указывал на своих дочерних элементов, вы можете построить дерево из неизменяемых узлов.
Если вы действительно хотите попробовать, вы можете создать дерево с неизменными циклами. Например, вы можете определить неизменяемый класс графа, а затем сказать:
Graph g = Graph.Empty
.AddNode("A")
.AddNode("B")
.AddNode("C")
.AddEdge("A", "B")
.AddEdge("B", "C")
.AddEdge("C", "A");
И, эй, у вас есть «дерево» с «циклами» в нем — потому что, во-первых, у вас, конечно, нет дерева, у вас есть ориентированный граф.
Но с типом данных, который на самом деле использует традиционную реализацию бинарного дерева «левое и правое поддеревья», тогда невозможно создать циклическое дерево (конечно, по модулю хитрых уловок, таких как использование отражения или небезопасного кода.)
Вы не можете собрать его из корня, это требует от вас изменения узлов, которые вы уже добавили.