Структуры данных и модели вычислений
Представление разделенных множеств древовидной структурой
Пусть, по-прежнему, — множество, из элементов которого будет строиться коллекция. Каждое подмножество коллекции представляется корневым деревом, узлы которого являются элементами этого подмножества, то есть отождествляются с номерами из множества . Корень дерева используется в качестве имени соответствующего подмножества (канонический элемент). Для каждого узла дерева определяется узел , являющийся его родителем в дереве; если — корень, то полагаем .
Фактически в памяти компьютера это дерево будем представлять массивом так, что будет предком узла , если не является корнем, и , если — корень. Если же не входит ни в одно из подмножеств коллекции, то .
Рассмотрим пример. Пусть и коллекция состоит из двух подмножеств и . Деревья, представляющие эти подмножества, могут быть такими, как на рис.3.1. Кружочки обозначают узлы дерева; указатели на родителей представлены при помощи стрелок. Именем одного из этих подмножеств является 3, другого — 6:
Рис. 3.1.
