Потенциальная функция Splay Tree: зачем суммировать журналы размеров?

Я преподаю курс по структурам данных и в начале следующей недели расскажу о деревьях сплайнов. Я много раз читал статью о деревьях сплайнов и знаком с анализом и интуицией, стоящими за структурой данных. Тем не менее, я не могу найти твердую интуицию для потенциальной функции, которую Слеатор и Тарьян используют в своем анализе.

Анализ работает путем присвоения каждому элементу дерева произвольного веса , а затем установки размера узла равным сумме весов узлов в поддереве с корнем в . Затем они берут лог этого значения, чтобы получить ранг узла, поэтому . Наконец, потенциальная функция дерева определяется как сумма рангов всех узлов. $w_i$ $s(x)$ $x$ $r(x)$ $r(x) = \log s(x)$

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

Соответствует ли потенциальная функция дерева сплайнов некоторому естественному свойству дерева? Есть ли какая-то особая причина, кроме «это работает», что они выбрали бы этот потенциал? (Мне особенно любопытно, потому что этот набор заметок, конечно, упоминает, что «анализ - это черная магия. [Не] идея, как обнаружить»)

Благодарность!

ds.data-structures intuition amortized-analysis templatetypedef
источник

Я слышал это объяснение "это черная магия" и раньше. Вы пытались написать Слеатору и Тарьяну по электронной почте?

Jbapple

@jbapple Я еще не писал им по электронной почте, так как надеялся, что «сообщество в целом» сможет помочь. Я также полагал, что пинг кого-то о работе, которую он сделал 30 лет назад, не обязательно вызывает ответ. :-)

templatetypedef

Я не очень знаком с этим, но я просто смотрю на бумагу очень грубо, я думаю, единственная причина в том, что они хотят иметь небольшие изменения в потенциальных функциях после операции Splay, например, если мы заменим

на

или

кажется , до сих пор все работает отлично (я ничего не докажу , но , кажется , просто нужен простой mathwork). Но если мы оставим это как

, то этот анализ амортизации пока верен, но он не является хорошим верхним пределом (что-то вроде

). Это никак не связано с каким-либо свойством дерева.

\log

$\log$

\log \log

$\log\log$

l o g^{*}

$log^*$

s

$s$

(m + n)^{2}

$(m+n)^2$

Саид

Я всегда помечал ранг х как «глубину идеального бинарного дерева поиска, содержащего потомков х», но это скорее мнемоника, чем полезная интуиция.

Джеффс

Ответы:

Как придумать потенциал суммы логов

Давайте рассмотрим алгоритм BST который для каждого доступа к элементу переставляет только элементы в пути поиска из называемого before-path, в некоторое дерево, называемое after-tree. Для любого элемента , пусть и быть размером поддерева с корнем в до и после перегруппировки соответственно. Таким образом, и могут отличаться, если $A$ $x$ $P$ $x$ $a$ $s(a)$ $s'(a)$ $a$ $s(a)$ $s'(a)$ $a \in P$ .

Кроме того, $A$ только постоянно переставляет множество элементов в пути поиска в любой момент. Давайте назовем этот тип алгоритма «локальным» алгоритмом. Например, Splay Tree является локальным. Зигзаг, зигзаг и зигзаг перестраивает не более 3 элементов одновременно.

Теперь любой локальный алгоритм, который создает «много» листьев в последующем дереве, например, Splay Tree, имеет следующее приятное свойство.

Мы можем создать отображение такое, что $f: P \rightarrow P$

Линейно много , где . $a \in P$ $s'(f(a)) \le s(a)/2$

Постоянно много , где может быть большим, но тривиально не более $a \in P$ $s'(f(a))$ $n$ .

Другие элементы , . $a \in P$ $s'(f(a)) \le s(a)$

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

Зная этот факт, очень естественно выбрать потенциал суммы логов. Потому что мы можем использовать потенциальное изменение элементов типа 1 для оплаты всей перестановки. Более того, для элементов другого типа мы должны платить за потенциальное изменение не более чем логарифмически. Следовательно, мы можем получить логарифм амортизированной стоимости.

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

PS В статье даже показано некоторое ограничение потенциала суммы логарифмов. То есть можно доказать выполнимость леммы доступа с помощью потенциала суммы логарифмов только для локального алгоритма.

Интерпретация суммы сумм бревен

Есть еще один способ определить потенциал BST в статье Георгакопулоса и МакКларкина, который по сути совпадает с потенциалом суммы логарифмов в статье Слеатора Тарьяна. Но это дает мне хорошую интуицию.

Теперь я переключаюсь на обозначения бумаги. Мы присваиваем вес каждому узлу . Пусть - сумма веса поддерева . (Это просто размер поддерева , когда вес каждого узла равен единице.) $w(u)$ $u$ $W(u)$ $u$ $u$

Теперь, вместо того, чтобы определять ранг на узлах, мы определяем ранг для ребер, который они называют фактором прогресса .

п е (е) знак равно журнал (W (U) / W (v)),

$pf(e)=\log(W(u)/W(v)).$

$S$

Φ (S) знак равно \underset{е \in S}{Σ} п е (е),

$\Phi(S) = \sum_{e\in S} pf(e).$

$(u,v)$ $u$ $v$ $W(u)/W(v)$

Заметьте, что это почти равный потенциал Слеатора Тарьяна, и он аддитивен на путях.

редактировать: оказывается, что это альтернативное определение и интуиция за ним были описаны давно Kurt Mehlhorn. См. Его книгу «Структуры данных и алгоритмы», том I, раздел III. 6.1.2 Splay Trees, стр. 263 - 274.

Thatchaphol
источник