#algorithm
#алгоритм
Вопрос:
Непересекающееся объединение — анализ сжатия поиска.
Мы разделим узлы по их рангам. Затем мы делим ранги на ранговые группы. При каждой находке мы помещаем несколько американских монет в общую корзину, а несколько канадских — в определенные вершины. Чтобы вычислить общее количество депонированных канадских монет, мы вычислим депозиты на узел. Суммируя все депозиты для каждого узла в ранге r, мы получим общее количество депозитов для каждого ранга r. Затем мы сложим все депозиты для каждого ранга r в группе g и, таким образом, получим общие депозиты для каждой ранговой группы g. Наконец, мы суммируем все депозиты для каждой ранговой группы g, чтобы получить общее количество канадских монет, депонированных в лесу. Добавление этого к количеству американских монет в кошельке дает нам ответ.
Для каждой вершины v на пути от вершины, представляющей i, до корня мы вносим один пенни на один из двух счетов:
Если v является корнем, или если родительский элемент v является корнем, или если родительский элемент v находится в другой ранговой группе, чем v, то начислите одну единицу в соответствии с этим правилом. Это вносит американский пенни в котенка.
В противном случае внесите канадский пенни в вершину.
Чтобы получить хорошую оценку для всех канадских месторождений в соответствии с правилом 2, мы будем суммировать месторождения по вершинам, а не по инструкциям поиска. Если монета помещается в вершину v в соответствии с правилом 2, v будет перемещен путем сжатия пути и получит новый родительский элемент более высокого ранга, чем его старый родительский элемент. (Здесь мы используем тот факт, что выполняется сжатие пути.) Таким образом, вершина v в ранговой группе g> 0 может быть перемещена не более F (g) — F (g — 1) раз, прежде чем ее родительский элемент будет вытеснен из ранговой группы g, поскольку это размер ранговой группы. * После этого все будущие начисления на v будутследуйте правилу 1.
Мой вопрос по приведенному выше тексту
- Как автор пришел к выводу, что «вершина v в ранговой группе g> 0 может быть перемещена не более F (g) — F (g — 1) раз»
Спасибо!
Ответ №1:
В оригинале, над процитированным вами разделом, говорится, что «Количество рангов в любой ранговой группе, g> 0, таким образом, равно F (g) — F (g — 1)»
Автор не делает точного вывода о том, что вы запрашиваете, и узел действительно может быть перемещен произвольное количество раз. Автор приходит к выводу, что после того, как узел был перемещен F (g) — F (g — 1) раз путем сжатия пути, родительский элемент, к которому он был перемещен, не может находиться в той же ранговой группе, что и узел, потому что каждый раз, когда узел перемещается, он получаетродительский элемент с более высоким рангом. После того, как это произошло F (g) — F (g — 1) раз, его родительский элемент не может находиться в той же ранговой группе.
Значение этого заключается в том, что все дальнейшие шаги сжатия пути этого узла подпадают под правило (1) и вносят американские пенни, а не канадские пенни.