Почему нет циклов в неизменяемом двоичном дереве Эрика Липперта?

Question

Я просто смотрел на простую реализацию Эрика Липперта immutable binary tree, и у меня есть вопрос об этом. После показа реализации, Эрик утверждает, что

Обратите внимание, что еще одна приятная особенность неизменных структур данных является то, что невозможно случайно (или намеренно !) Создать дерево, которое содержит цикл.

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

Я прав в своем мышлении, или невозможность циклов в этом случае исходит из неизменности в одиночку? Учитывая источник, я задаюсь вопросом, не хватает ли я чего-то.

EDIT: Подумав об этом чуть больше, кажется, что создание из листьев может быть единственным способом создания неизменяемого дерева. Я прав?

Answer 1

Если вы используете неизменяемую структуру данных, в строгом (в отличие от ленивого) языке невозможно создать цикл; так как вы должны создать элементы в некотором порядке, и как только элемент будет создан, вы не сможете мутировать его, чтобы указать на элемент, созданный позже. Так что если вы создали узел п, а затем созданный узел м который указал на п (возможно, косвенно), вы никогда не могли завершить цикл, вызывая п указать на м как вы не можете mutate n, или ничего, что n уже указывает на.

Да, вы правы, что вы можете создавать только неизменяемое дерево, создавая из листьев; если вы начали с корня, вам придется изменить корень, чтобы указать на его дочерние элементы по мере их создания. Только начиная с листьев и создавая каждый узел, чтобы указать на его дочерние элементы, вы можете построить дерево из неизменяемых узлов.

Answer 2

Вы не можете создать его из корня, он требует, чтобы вы мутировали узлы, которые вы уже добавили.

Answer 3

Когда вы говорите «построенный из листьев», я предполагаю, что вы включаете тот факт, что конструктор принимает детей, но никогда не берет родителя.

кажется, что, если вы построили дерево в другом направлении, вы бы ввести возможность циклов.

Нет, потому что тогда у вас будет противоположное ограничение: конструктор должен будет взять родителя, но никогда не будет дочерним. Поэтому вы никогда не сможете создать потомка, пока не будут созданы все его предки. Поэтому никакие циклы не возможны.

Обдумав это немного больше, это кажется, что создание из листьев может быть единственным способом создания непреложного дерева. Я прав?

Нет ... см. Мои комментарии к Брайану и ergosys.

Для многих приложений дерево, дочерние узлы которого указывают на родителей, не очень полезно. Я даю это. Если вам нужно пересечь дерево в порядке, определяемом его иерархией, дерево с восходящим указателем делает это трудным.

Однако для других приложений такое дерево является именно тем видом, который мы хотим. Например, у нас есть база данных статей. Каждая статья может иметь один или несколько переводов. В каждом переводе могут быть переводы. Мы создаем эту структуру данных как таблицу реляционных баз данных, где каждая запись имеет «внешний ключ» (указатель) для своего родителя. Ни одна из этих записей никогда не должна менять свой указатель на родителя. Когда добавляется новая статья или перевод, запись создается с указателем на соответствующий родительский элемент.

Общим примером является запрос таблицы переводов, поиск переводов для определенной статьи или переводы на определенном языке. Ах, вы говорите, таблица переводов - изменяемая структура данных.

Несомненно. Но он отделен от дерева. Мы используем (неизменяемое) дерево для записи иерархических отношений и изменяемой таблицы для итерации по элементам. В ситуации, отличной от базы данных, вы можете иметь хеш-таблицу, указывающую на узлы дерева. В любом случае, само дерево (т. Е. Узлы) никогда не будет изменено.

Here's another example of this data structure, включая способы доступа к узлам.

Моя точка зрения заключается в том, что ответ на вопрос ОП «да», я согласен с остальными вами, что предотвращение циклов делает исходит из неизменности в одиночку. В то время как вы можете построить дерево в другом направлении (сверху вниз), если вы это сделаете, и оно неизменное, оно все еще не может иметь циклов.

Когда вы говорите о мощных теоретических гарантий, как

еще одна приятная особенность неизменных структур данных является то, что невозможно случайно (или намеренно !) Создать дерево, которое содержит цикл [акцент в оригинале]

«такое дерево не очень полезно» бледнеет в сравнении - даже если это правда. Люди создают бесполезные структуры данных случайно, не говоря уже о создании якобы бесполезных намеренно. Предполагаемая бесполезность не защищает программу от ошибок циклов в ваших структурах данных. Теоретическая гарантия (если вы действительно соответствуете указанным критериям).

P.S. одна хорошая особенность деревьев, указывающих вверх, заключается в том, что вы можете гарантировать один аспект определения деревьев, что структуры дерева древовидных деревьев (например, Эрик Липперт) не делают: каждый узел имеет не более одного родителя. (См. David's comment и мой ответ.)

Answer 4

Если вы действительно хотите попробовать, вы можете создать дерево с циклами в нем, которые неизменны.Например, вы могли бы определить неизменный класс графа, а затем сказать:

Graph g = Graph.Empty 
    .AddNode("A") 
    .AddNode("B") 
    .AddNode("C") 
    .AddEdge("A", "B") 
    .AddEdge("B", "C") 
    .AddEdge("C", "A"); 

И эй, у вас есть «дерево» с «циклов» в ней - потому что, конечно, вы не получили дерево в на первом месте у вас есть ориентированный граф.

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