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

Question

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

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

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

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

РЕДАКТИРОВАТЬ: Подумав еще немного, кажется, что наращивание из листьев может быть единственным способом создать неизменное дерево.Я прав?

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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

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

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

Вот еще один пример этой структуры данных , включая способы полезного доступа к узлам.

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

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

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

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

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

Answer 4

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