У меня возникают проблемы с пониманием следующего из начала раздела 2.5 «Хензингер и Кинг» (FOCS 1995):
Мы кодируем произвольное дерево T с n вершинами, используя последовательность из 2n - 1 символов, которая генерируется следующим образом: Укореняем дерево в произвольной вершине.
Затем пройдитесь по T в порядке поиска в глубину, пройдя по каждому ребру дважды (по одному в каждом направлении) и посетив каждую вершину степени-d d раз, за исключением корня, который посещается d + 1 раз. Каждый раз, когда встречается любая вершина u, мы называем это вхождением вершины. Пусть ET (T) будет последовательностью вхождений узлов, представляющих произвольное дерево T.
Для каждого связующего дерева T (B) блока B из H_i каждое вхождение ET (T (B)) сохраняется в узле сбалансированного бинарного дерева поиска, называемого ET (T (B)) - деревом , Для каждой вершины u в T (B) мы произвольно выбираем одно вхождение как активное вхождение u.
При активном вхождении каждой вершины v мы сохраняем (неупорядоченный) список ненулевых ребер в B, инцидентных u, сохраняемых в виде сбалансированного двоичного дерева. Каждый узел в ET-дереве содержит количество ненулевых ребер, хранящихся в его поддереве.
Используя эту структуру данных для каждого уровня, мы можем выбрать границу T_1 за время O (logn).
Мои вопросы следуют за некоторыми объяснениями некоторых терминов.
Из раздела 2.2,
A block - это максимальный набор узлов, которые являются двусвязными.
H_i - это подграф графа G, динамическую двусвязность которого (который является основной темой статьи) мы хотим сохранить. (Более конкретно, набор ребер G был разбит на l = log (| E (G) |) наборов, и каждый набор индуцирует граф H_i для 1 <= <em>i < = л .)
Вот мое понимание. Выберите T (B) из H_i. Ключ каждого активного узла в соответствующем дереве ET - это число «нетривых ребер в B [которые] инцидентны u». Значением каждого узла является соответствующий список ребер.
Вопросы:
- Чтобы завершить ET-дерево, каждый узел должен хранить сумму ключей всех узлов в своем поддереве (включая сам узел)?
- Список для каждого узла не является сбалансированным деревом, верно?
- Если важны только активные узлы, зачем вообще создавать дерево ET?
- Чтобы выбрать ребро, мы генерируем число от 1 до | E (B)) |. Если число находится в диапазоне от 1 до | V (B) | - 1 тогда мы выбираем какой-нибудь край дерева. В противном случае мы пересекаем сбалансированное дерево и затем выбираем соответствующее ребро из списка?