Анализ реализации с ранговой эвристикой

Пусть union(v1,v2) - процедура слития двух множеств содержащих v1,v2, а get(v) - поиск корня поддерева содержащего x. Рассмотрим n операций union и m операций get. Для удобства и без потери общности будем считать что у нас union принимает в качестве аргументов корни поддеревьев и (m>n), то есть (union(v1,v2) заменяем на union(get(v1),get(v2)). Тогда нам надо оценить стоимость операции get(v). Обозначим [math]R(v)[/math] - ранг вершины,[math]P(v)[/math] - отец вершины,[math]L(v) [/math] - самый первый отец вершины.

Утверждение:

[math] R(P(v))\gt R(v) [/math]

[math]\triangleright[/math]

Из того как работает функция get следует: 1.[math] R(L(v))\gt R(v) [/math] 2. Между [math] v [/math] и [math] P(v) [/math] существует путь вида : [math] v -\gt L(v) -\gt L(L(v)) ... -\gt P(v) [/math] Записав неравенство из первого пункта вдоль пути из второго пункта следует что [math] R(P(v))\gt R(v) [/math]

[math]\triangleleft[/math]