Амортизированная стоимость Splay Tree: стоимость + объяснение P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x))

Question

Читая о деревьях сплайнов, я нашел некоторое выражение о ранге сплайс-узла «X» и амортизированной стоимости в википедии. Это дано как, { Мы можем связать амортизированную стоимость любой зигзагообразной или зигзагообразной операции следующим образом:

amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)),

где x - это узел, перемещаемый в направлении корня, а нижние индексы «f» и «i» указывают после и до операции, соответственно. При суммировании по всей операции сплайсинга это телескопическое значение равно 3 (rank (root)), что равно O (log n). Поскольку существует не более одной операции zig, это добавляет только константу.}

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

Пожалуйста, предоставьте некоторые ссылки для объяснения других теорем о splay-деревьях

Спасибо

Answer 1

Вы хотите провести простой амортизированный анализ статических деревьев наложения.Если вы берете один базовый зигзаг, как пример в Википедии.это худший случай сенарио.И у вас есть:

P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x))

Доказательство: с нотацией, используемой в Википедии, поскольку хв корне дерева после преобразования вы легко получаете:

rankf (x)> = rankf (g) и rankf (x)> = rankf (f)

, таким образом,

Ptf = rankf (x) + rankf (g) + rankf (p) <= 3 * rankf (x) </p>

С противоположным рассуждением с x перед преобразованием вы получаете:

Pti = ranki (x) + ranki (g) + ranki (p)> = 3 * ranki (x)

Вы можете обобщить это на всю операцию для расчета амортизированной стоимости.

Полагаю, это доказывает ваш результат, но я не уверен, что это то, что вы искали.