8
правок
Изменения
м
→Анализ реализации с ранговой эвристикой
В процессе выполнения каждой из операций <tex>get</tex> двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Заметим, что на каждом шаге ранг вершины строго возрастает: если <tex>\mathrm{u}</tex> - вершина, встретившаяся на пути поиска, а <tex>\mathrm{v}</tex> - следующая вершина, то есть <tex>\mathrm{v} = \mathrm{P(u)} </tex>, то <tex> \mathrm{R(v)} \leqslant \mathrm{R(u)}</tex>. Вершина <tex>\mathrm{u}</tex> может неоднократно встречаться в путях поиска, при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут идти разные вершины: если в некоторый момент за <tex>\mathrm{u}</tex> будет следовать уже не <tex>\mathrm{v}</tex>, а корень дерева, то есть вершина большего ранга, чем <tex>\mathrm{v}</tex>.
Наблюдая за ростом ранга при переходе от вершины к её родителю, отдельно оценим количество шагов, при которых ранг сильно растет, а количество шагов, когда он растет не сильно. Выберем в качестве границы некоторую функцию <tex>\mathrm{B(k)}</tex>, определенную для неотрицательных целых <tex>\mathrm{k}</tex>. Мы предполагаем, что функция <tex>\mathrm{B}</tex> является монотонно возрастающей и что <tex>\mathrm{B(k)} \leqslant geqslant \mathrm{k}</tex> при всех <tex>\mathrm{k}</tex>. При переходе от вершины <tex>\mathrm{u}</tex> к её родителю <tex>\mathrm{v} = \mathrm{P(u)} </tex> ранг сильно растет сильно растет, если <tex> \mathrm{R(v)} \geqslant \mathrm{B(R(u))} </tex>.
Оценим число шагов, при которых ранг не сильно растет, и сгруппируем их по вершинам, из которых этот шаг делается. Для вершины ранга <tex>\mathrm{k}</tex> ранги ее предка могут меняться от <tex>\mathrm{k+1}</tex> до <tex>\mathrm{B(k)}</tex> (после этого ранг растет сильно). Значит, число таких шагов(из данной вершины ранга <tex>\mathrm{k}</tex>) заведомо не больше <tex>\mathrm{B(k)}</tex>, поскольку каждый новый шаг ведёт в вершину большего ранга, чем предыдущий. Поскольку вершин ранга <tex>\mathrm{k}</tex> не более <tex>n/2^{k}</tex>, то общее число шагов, при которых ранг не сильно растет, не превосходит
<center>
