Нужны ли нам как сжатие пути, так и объединение по рангу вместе в непересекающейся структуре данных набора?

Question

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

Answer 1

Теперь, когда мы выполняем объединение по рангу, высота результирующего дерева всегда минимальна

Если вы объединяете по дереву ранга два высоты h, то вы получите деревовысоты h + 1.Таким образом, у вас есть два дерева высотой 1, вы получите дерево высотой 2. Затем, если вы получите другое дерево высотой 2, вы можете объединить их в дерево высотой 3 и так далее.Это может дать вам очень высокое дерево.

Я читаю это давно, и у меня нет CLRS под рукой, но мне кажется, что ни одной из эвристик не достаточно, чтобы гарантировать лучшую сложность (материал Акермана).Нам нужны они оба.Но на практике, возможно, можно использовать только один.