Объединение по рангу: откуда берётся логарифм

Если ты можешь доказать, что дерево ранга r содержит не меньше 2^r узлов, и объяснить, почему отсюда следует высота log₂ n, листай до «Теперь сам».

Как думаешь, какой корень подвешивать

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

На что это похоже

Слияние двух компаний. Если маленькую контору из трёх человек подчинить корпорации, цепочка подчинения удлинится у троих. Если наоборот - у всей корпорации. Решение очевидно: присоединяем меньшего к большему, и число пострадавших минимально. А теперь ключевое наблюдение, из которого вырастет доказательство: чтобы у конкретного человека цепочка удлинилась, его компания должна влиться в компанию НЕ МЕНЬШЕГО размера, то есть общий размер минимум удвоится. Удвоений до миллиона - двадцать.

Механизм: два способа мерить и одно правило

по РАЗМЕРУ:                            по РАНГУ:
size[x] - число элементов в дереве     rank[x] - верхняя оценка высоты дерева

union(a, b):                           union(a, b):
  ra = find(a); rb = find(b)             ra = find(a); rb = find(b)
  если ra == rb: выход                   если ra == rb: выход
  если size[ra] < size[rb]:              если rank[ra] < rank[rb]:
      поменять ra и rb                       поменять ra и rb
  parent[rb] = ra                        parent[rb] = ra
  size[ra] += size[rb]                   если rank[ra] == rank[rb]:
                                             rank[ra] += 1

Разница между ними невелика: размер точнее описывает дерево, ранг компактнее и не требует складывать большие числа. Гарантия у обоих одна - высота O(log n). Важная тонкость про ранг: после сжатия пути (следующий урок) ранг перестаёт быть точной высотой и остаётся лишь ВЕРХНЕЙ ОЦЕНКОЙ - его не пересчитывают, и это правильно; оценка сверху - всё, что нужно для доказательства. И сама граница r ≤ log₂ n сжатие переживает: ранги меняются ТОЛЬКО в union, а сжатие трогает лишь ссылки parent, поэтому доказанное ниже неравенство «дерево ранга r собрано минимум из 2^r узлов» остаётся верным - оно про историю объединений, а не про текущую форму дерева.

Правило

Объединение по рангу (или по размеру): меньшее дерево подвешивают к большему; при равных рангах ранг нового корня увеличивают на единицу. Тогда дерево ранга r содержит не меньше 2^r узлов, значит ранг и высота не больше log₂ n, а find - O(log n) в худшем случае. Ранг после сжатия пути не пересчитывают: он остаётся верхней оценкой высоты, и этого достаточно.

Разбор: почему дерево ранга r содержит не меньше 2^r узлов

Докажем индукцией по числу операций - это тот же приём, что в разделе про корректность.

База. Дерево ранга 0 - это один узел: 2⁰ = 1, верно.

Шаг. Ранг корня меняется только в одном случае: когда сливают два дерева РАВНОГО ранга r, и новый корень получает ранг r+1. По предположению индукции в каждом из них было не меньше 2^r узлов, значит в объединении не меньше 2^r + 2^r = 2^(r+1) - ровно то, что требовалось. Если ранги разные, ранг корня не меняется, а число узлов только растёт - условие не нарушается.

Следствие. Если дерево ранга r содержит не меньше 2^r узлов, а всего элементов n, то 2^r <= n, откуда r <= log₂ n. Высота дерева не превосходит его ранга, значит find поднимается не больше чем по log₂ n рёбрам. Для миллиона элементов это двадцать шагов вместо миллиона у вырожденной цепочки.

Обрати внимание, ЧТО именно заставило работать доказательство: ранг растёт только при слиянии равных, то есть только при удвоении размера. Правило «меньшее к большему» превращает рост высоты в удвоение числа элементов, а удвоений от единицы до n ровно log₂ n. Тот же аргумент встречался в оценке динамического массива и встретится ещё не раз - это универсальный способ получить логарифм.

Считаем вместе: сколько раз может углубиться один элемент

Посмотрим на версию с размером, с точки зрения ОТДЕЛЬНОГО элемента x. Его путь до корня удлиняется на единицу тогда и только тогда, когда дерево, в котором он лежит, подвешивают к другому - а по правилу это происходит, лишь если другое дерево не меньше. Значит после каждого такого события размер дерева, содержащего x, увеличивается минимум вдвое.

после 1-го углубления в дереве с x минимум 2 элемента
после 2-го                          минимум 4
после k-го                          минимум 2^k

Элементов всего n, значит 2^k <= n и k <= log₂ n: ни один элемент не может углубиться больше двадцати раз при миллионе элементов. Это то же самое утверждение, что и про ранг, но доказанное «со стороны элемента», и такой взгляд часто удобнее: он сразу даёт ответ на вопрос «сколько СУММАРНО стоят все find'ы», если объединения перемежаются с запросами.

Что ломается без этого

Первое: подвешивать без сравнения - например, всегда корень ВТОРОГО аргумента к корню первого, как в коде прошлого урока: тогда вход union(1,0), union(2,1), union(3,2), ... даёт цепочку (parent[0] = 1, затем parent[1] = 2, затем parent[2] = 3). Ошибка не видна на случайных тестах и вылезает на данных, отсортированных по порядку, а такие данные встречаются чаще случайных. Второе: сравнивать ранги, но забыть увеличивать ранг при равенстве - тогда ранг перестаёт расти вовсе, правило превращается в «подвесить как попало», а гарантия исчезает. Третье: поменять местами КОРНИ ra и rb, но подвесить по старым именам (сами a и b после find уже не нужны) - типичная ошибка при переписывании кода, и она даёт ровно обратное правило: большое к малому. Четвёртое: пересчитывать ранг после сжатия пути в попытке «держать его точным» - это лишняя работа, а иногда и ошибка; ранг обязан быть лишь верхней оценкой. Пятое: хранить размер не в корне, а во всех узлах и обновлять везде - корректно, но дорого; поддерживать его нужно ТОЛЬКО у корня, остальные значения бессмысленны.

Зачем это в работе

Логарифм здесь - не конечная цель (следующий урок сделает из него почти константу), но в двух случаях он и есть весь ответ. Первый: когда сжатие пути применить нельзя - например, структура должна уметь откатывать объединения, и переписывать указатели при find нельзя, потому что это ломает историю; там оставляют только ранг и живут с O(log n). Второй: когда важна ГАРАНТИЯ на каждую операцию, а не в среднем: ранг даёт худший случай O(log n) для каждого find, тогда как сжатие пути даёт амортизированную оценку - хорошую в сумме, но с отдельными дорогими вызовами.

И более общий навык. Приём «сливай меньшее в большее» работает далеко за пределами этой структуры: на нём держится приём «малое к большому» (когда в узле дерева сливают множества детей, всегда переливая меньшее в большее: каждый элемент меняет хозяина не больше log n раз, отсюда лишний логарифм в оценке), оценка объединения хеш-таблиц, слияние списков в алгоритмах на деревьях. Всякий раз аргумент один и тот же: элемент меняет владельца, только когда размер его группы удваивается, а удвоений log₂ n.

Теперь сам

В лесу с объединением по рангу сделали union семь раз, и все семь оказались результативными. Какой максимальный ранг может быть у корня и сколько элементов минимум в его дереве? Хватит ли восьми элементов, чтобы получить ранг 3?