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

16

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

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

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

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

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

templatetypedef
источник
Я слышал это объяснение "это черная магия" и раньше. Вы пытались написать Слеатору и Тарьяну по электронной почте?
Jbapple
@jbapple Я еще не писал им по электронной почте, так как надеялся, что «сообщество в целом» сможет помочь. Я также полагал, что пинг кого-то о работе, которую он сделал 30 лет назад, не обязательно вызывает ответ. :-)
templatetypedef
Я не очень знаком с этим, но я просто смотрю на бумагу очень грубо, я думаю, единственная причина в том, что они хотят иметь небольшие изменения в потенциальных функциях после операции Splay, например, если мы заменим на log log или л о г * кажется , до сих пор все работает отлично (я ничего не докажу , но , кажется , просто нужен простой mathwork). Но если мы оставим это как s , то этот анализ амортизации пока верен, но он не является хорошим верхним пределом (что-то вроде ( m + n ) 2 ). Это никак не связано с каким-либо свойством дерева. logloglogLограмм*s(м+N)2
Саид
Я всегда помечал ранг х как «глубину идеального бинарного дерева поиска, содержащего потомков х», но это скорее мнемоника, чем полезная интуиция.
Джеффс

Ответы:

13

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

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

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

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

Мы можем создать отображение такое, чтое:пп

  1. Линейно много , где s ( f ( a ) ) s ( a ) / 2 .aпs'(е(a))s(a)/2
  2. Постоянно много , где s ( f ( a ) ) может быть большим, но тривиально не более naпs'(е(a))N .
  3. Другие элементы , s ( f ( a ) ) s ( a ) .aпs'(е(a))s(a)

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

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

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

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

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

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

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

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

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

S

Φ(S)знак равноΣеSпе(е),

(U,v)UvW(U)/W(v)

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

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

Thatchaphol
источник