Как сжатие и объединение по рангам дополняют друг друга?

Question

Я читал о проблеме объединения-поиска. Двумя основными улучшениями являются сжатие путей и объединение по рангу. Насколько я понимаю, союз по рангу используется для определения того, как объединить непересекающиеся деревья. Если мы имеем два непересекающихся дерева T1 и T2, то мы присоединяем корень дерева меньшего ранга к дереву с более высоким рангом. Если мы не используем сжатие пути, то ранг - это только глубина дерева. Это имеет смысл, поскольку мы не хотим увеличивать глубину дерева, поскольку оно напрямую влияет на оба находок и союзов.

Моя проблема в том, что мы используем также сжатие пути. Я продолжаю читать, что две оптимизации дополняют друг друга, но я этого не вижу. Из-за сжатия пути ранг больше не является глубиной дерева (он становится верхней границей по глубине). Предположим, что T1 имеет 2 ответвления (пусть ранг T1 равен 3), а T2 имеет глубину 2 и ранг 2. Теперь предположим, что мы выполняем операцию поиска (с сжатием пути) на листе T1, отмеченном «*» ниже. Теперь, если мы объединяем корень из T1 и корень из T2, тогда T2 будет присоединен к корню T1 (так как ранг не обновляется поиском). Полученное дерево имеет глубину 3. Но мы могли бы иметь лучшую производительность, если бы мы привязали T1 к T2.

T1: o (Rank = 3) T2: o (Rank = 2) 
    /\      | 
    o o      o 
    |       | 
    o       o 
    | 
    * 

После находки на листе T1 ("*"), то объединение на корнях Т1 и Т2 мы получаем

T1: o  (Rank = 3)  T2: o (Rank = 2)  
    /| |\       | 
    * o o o      o 
            | 
            o 
Result of T1 union T2 
     o 
/| | |\ 
    * o o o o Rank = 3 and Max Depth = 3 
      | 
      o 
      | 
      o 

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

Спасибо за помощь заранее.

Answer 1

Объединение по рангам гарантирует, что максимальная глубина дерева равна log N, поэтому он помещает верхнюю границу наихудшего случая O (log N) в каждую операцию.

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

Используя оба варианта, вы получаете ограничение O (log N) в худшем случае и амортизированная граница улучшается до O ((N)), которая является фактически постоянной. Таким образом, две оптимизации дополняют друг друга.

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