Link-Cut Tree — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
'''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях: [[Определение сети, потока|потоки]] и динамические графы.
 
'''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях: [[Определение сети, потока|потоки]] и динамические графы.
 
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
 
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Изменения нужно быстро обрабатывать, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи.  Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
+
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи.  Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
  
 
'''Link-cut tree'''  {{---}} это структура данных, которая хранит [[Дерево, эквивалентные определения |лес деревьев]] и позволяет выполнять следующие операции:
 
'''Link-cut tree'''  {{---}} это структура данных, которая хранит [[Дерево, эквивалентные определения |лес деревьев]] и позволяет выполнять следующие операции:
Строка 18: Строка 18:
 
* '''<tex>\mathrm{link(v, u)}</tex>''' {{---}} подвешивать голову одного пути к хвосту другого.  
 
* '''<tex>\mathrm{link(v, u)}</tex>''' {{---}} подвешивать голову одного пути к хвосту другого.  
  
Если бы не последние две операции, то можно было бы применить [[Несогласованные поддеревья. Реализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи декартового дерева по неявному ключу. Также, если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.
+
Если бы не последние две операции, то можно было бы применить [[Несогласованные поддеревья. Реализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]]. Также, если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.
 
В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревья]], в которых ключи выбираются равными глубине вершины.  
 
В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревья]], в которых ключи выбираются равными глубине вершины.  
  
Строка 75: Строка 75:
  
 
===min(v)===
 
===min(v)===
Построим splay-дерево для пути и сравним минимум корня <tex>v</tex> c минимумом в левом поддереве:
+
Построим splay-дерево для пути и сравним вес корня <tex>v</tex> c минимумом в левом поддереве:
 
  '''function''' min(v: '''tree'''): '''int'''
 
  '''function''' min(v: '''tree'''): '''int'''
 
     expose(v)
 
     expose(v)
Строка 84: Строка 84:
  
 
===link(v, u)===
 
===link(v, u)===
Если <tex>v</tex> {{---}} корень, а <tex>u</tex> {{---}} вершина в другом дереве, то <tex>\mathrm{link(v, u)}</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>.
+
Если <tex>v</tex> {{---}} корень, а <tex>u</tex> {{---}} вершина в другом дереве, то <tex>\mathrm{link(v, u)}</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>v</tex> становится родителем <tex>u</tex>.
  
 
  '''function''' link(v: '''tree''', u: '''tree'''): '''tree'''
 
  '''function''' link(v: '''tree''', u: '''tree'''): '''tree'''
Строка 96: Строка 96:
  
 
===cut(v)===
 
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{---}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
+
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержаться все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{---}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
  
 
  '''function''' cut(v: '''tree'''):
 
  '''function''' cut(v: '''tree'''):
Строка 102: Строка 102:
 
     <tex>\vartriangle</tex>w(left(v)) += <tex>\vartriangle</tex>w(v)
 
     <tex>\vartriangle</tex>w(left(v)) += <tex>\vartriangle</tex>w(v)
 
     <tex>\vartriangle</tex>min(v) <tex>=</tex> min{0, <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w(right(v))}
 
     <tex>\vartriangle</tex>min(v) <tex>=</tex> min{0, <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w(right(v))}
 +
    parent(left(v)) <tex>=</tex> null
 
     left(v) <tex>=</tex> null
 
     left(v) <tex>=</tex> null
    parent(left(v)) <tex>=</tex> null
 
  
 
==Оценка времени работы==
 
==Оценка времени работы==
Строка 114: Строка 114:
 
}}
 
}}
  
Операция <tex>u</tex> осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество сплошных ребер, преобразованных в пунктирные в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество пунктирных ребер, преобразованных в сплошные.
+
Операция <tex>\mathrm{expose(u)}</tex> осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество сплошных ребер, преобразованных в пунктирные в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество пунктирных ребер, преобразованных в сплошные.
  
 
<tex>M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|</tex>
 
<tex>M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|</tex>
Строка 141: Строка 141:
 
Докажем, что [[Амортизационный анализ|амортизационная стоимость операции]] <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.
 
Докажем, что [[Амортизационный анализ|амортизационная стоимость операции]] <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.
  
Пусть <tex>s(v)</tex> {{---}} количество вершин в поддеревьях <tex>v</tex> ( здесь имеется в виду splay-дерево пути, котоый строится в ходе выполнения <tex>\mathrm{expose}</tex>), <tex>r(v) = \log s(v)</tex>. По  [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>\mathrm{splay}</tex> не превосходит <tex>1 + 3 \cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>\mathrm{expose}</tex> ограничена следующим значением:
+
Пусть <tex>s(v)</tex> {{---}} количество вершин в поддеревьях <tex>v</tex> ( здесь имеется в виду splay-дерево пути, который строится в ходе выполнения <tex>\mathrm{expose}</tex>), <tex>r(v) = \log s(v)</tex>. По  [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>\mathrm{splay}</tex> не превосходит <tex>1 + 3 \cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>\mathrm{expose}</tex> ограничена следующим значением:
  
 
<tex>3 \cdot \log n - 3 \cdot \log (s(v)) + M</tex>
 
<tex>3 \cdot \log n - 3 \cdot \log (s(v)) + M</tex>

Текущая версия на 19:05, 4 сентября 2022

Динамические деревья (англ.dynamic tree) используются в двух областях: потоки и динамические графы. В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов link и cut.

Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:

  • [math]\mathrm{min(v)}[/math] — искать минимум на пути от вершины до корня,
  • [math]\mathrm{add(v, c)}[/math] — прибавлять константу на пути от вершины до корня,
  • [math]\mathrm{link(u, w)}[/math] — подвешивать одно дерево на другое,
  • [math]\mathrm{cut(v)}[/math] — отрезать дерево с корнем в вершине [math]\mathrm{v}[/math].

Среднее время выполнения каждой операции — [math]O(\log n)[/math]. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.

Решение задачи в частном случае

Сначала рассмотрим частный случай, в котором все деревья — это пути, и мы хотим уметь:

Пример построения дерева для пути
  • [math]\mathrm{add(v, c)}[/math] и [math]\mathrm{min(v)}[/math] — прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня),
  • [math]\mathrm{cut(v)}[/math] — разбить один путь на два,
  • [math]\mathrm{link(v, u)}[/math] — подвешивать голову одного пути к хвосту другого.

Если бы не последние две операции, то можно было бы применить дерево отрезков, сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи декартового дерева по неявному ключу. Также, если использовать какие-нибудь сливаемые деревья, то [math]\mathrm{link}[/math] и [math] \mathrm{cut}[/math] реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах. В качестве сливаемых деревьев выберем splay-деревья, в которых ключи выбираются равными глубине вершины.

Тогда операции [math]\mathrm{cut}[/math] будет соответствовать [math]\mathrm{split}[/math].

[math]\mathrm{link(path1, path2)}[/math] соединяет голову первого пути с хвостом второго. Используем функцию [math]\mathrm{merge(path2, path1)}[/math], которая вызовет [math]\mathrm{splay}[/math] от хвоста второго пути и сделает первый путь правым ребенком корня [math]\mathrm{path2}[/math], то есть теперь [math]\mathrm{path1}[/math] находится ниже, чем [math]\mathrm{path2}[/math].

Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину [math]\Delta w[/math], которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:

[math]w(u) = \displaystyle \sum_v^{} \Delta w(v)[/math], где [math] v [/math] — все предки вершины [math] u [/math].

При прибавлении [math]\alpha[/math] на пути от вершины [math]v[/math] до корня, сначала вызывается [math]\mathrm{splay(v)}[/math], после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить [math]\alpha[/math] к [math]\Delta w(v)[/math] и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть [math]\alpha[/math] от [math]\Delta w(right(v))[/math].


Для реализации [math]\min[/math] будем хранить минимум уже для всего поддерева. Чтобы искать минимум от вершины [math]v[/math], надо вызвать [math]\mathrm{splay(v)}[/math] и сравнить её вес с минимумом левого поддерева, в котором теперь находятся все вершины пути кроме [math]v[/math]. Определим [math]\Delta \min (v)[/math] таким образом, чтобы сохранялся следующий инвариант: [math]\min (v) = \Delta \min (v) + w(v) [/math]. Пусть [math]l[/math] и [math]r[/math] дети [math]v[/math], тогда

[math]\min (v) = \min \{w(v), \min(l), \min(r)\}[/math]

[math]\Delta \min(v) = \min(v) - w(v) \\ = \min\{w(v) - w(v), \min(l) - w(v), \min(r) - w(v)\} \\ = \min\{0, \ (\Delta \min(l) + w(l)) - w(v), \ (\Delta \min(r) + w(r)) - w(v)\} \\ = \min\{0, \ \Delta \min(l) + \Delta w(l), \ \Delta \min(r) + \Delta w(r)\}[/math]

Linkcut weights.png

Link-cut tree

Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо сплошным, либо пунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель [math]pathparent[/math].

Разбиение дерева на пути

expose(u)

Ключевая операция в link-cut-деревьях — [math]\mathrm{expose(u)}[/math]. После её выполнения [math]u[/math] лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от [math]u[/math] до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее сплошное ребро пунктирным ребром.

Разбиение дерева на пути
function expose(u: tree):
    splay(u)
    v [math]=[/math] u
    while v [math] \ne [/math] root
        p [math]=[/math] pathparent(v)        //получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня
        splay(p)                  //теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,
        parent(right(p)) [math]=[/math] null  //поэтому правое поддерево p делаем новым путем
        pathparent(right(p)) [math]=[/math] p
        right(p) [math]=[/math] v             //объединяем оставшийся и построенный пути
        [math]\vartriangle[/math]w(v) -= [math]\vartriangle[/math]w(p)
        [math]\vartriangle[/math]min(p) [math]=[/math] min{0, [math]\vartriangle[/math]min(left(p)) + [math]\vartriangle[/math]w(left(p)), [math]\vartriangle[/math]min(right(p)) + [math]\vartriangle[/math]w(right(p))}
        pathparent(v) [math]=[/math] null
        v [math]=[/math] p
    splay(u)

add(v, c)

Чтобы прибавить константу на пути от [math]v[/math] до корня link-cut-дерева вызовем [math]\mathrm{expose(v)}[/math], что построит запрашиваемый путь в виде splay-дерева, в котором [math]v[/math] — корень, и в левом поддереве находятся вершины, которые находятся выше чем [math]v[/math] в link-cut-дереве (то есть все вершины пути без [math]v[/math]), а в правом — те, что ниже. Тогда прибавим [math]c[/math] к [math]\Delta w(v)[/math] и вычтем константу от правого ребенка [math]v[/math], чтобы скомпенсировать разницу и сохранить инвариант.

function add(v: tree, c: int):
    expose(v)
    [math]\vartriangle[/math]w(v) += c
    [math]\vartriangle[/math]w(right(v)) -= c

min(v)

Построим splay-дерево для пути и сравним вес корня [math]v[/math] c минимумом в левом поддереве:

function min(v: tree): int
    expose(v)
    if [math]\vartriangle[/math]min(left(v)) + [math]\vartriangle[/math]w(left(v)) < [math]\vartriangle[/math]w(v)
        return [math]\vartriangle[/math]min(left(v)) + [math]\vartriangle[/math]w(left(v))
    else
        return [math]\vartriangle[/math]w(v)

link(v, u)

Если [math]v[/math] — корень, а [math]u[/math] — вершина в другом дереве, то [math]\mathrm{link(v, u)}[/math] соединяет два дерева добавлением ребра [math](v, u)[/math], причем [math]v[/math] становится родителем [math]u[/math].

function link(v: tree, u: tree): tree
    expose(v)      //теперь v — корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)
    expose(u)
    [math]\vartriangle[/math]w(u) -= [math]\vartriangle[/math]w(v) //чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве
    parent(u) [math]=[/math] v //                                              2. обновляем [math]\vartriangle[/math]w, [math]\vartriangle[/math]min
    left(v) [math]=[/math] u
    [math]\vartriangle[/math]min(v) [math]=[/math] min{0, [math]\vartriangle[/math]min(u) + [math]\vartriangle[/math]w(u), [math]\vartriangle[/math]min(right(v)) + [math]\vartriangle[/math]w((right(v)))}
    return v

cut(v)

Отрезает дерево с корнем [math]v[/math]. После вызова [math]\mathrm{expose(v)}[/math] вершина [math]v[/math] станет корнем splay-дерева, и в правом поддереве будут содержаться все вершины, которые были ниже [math]v[/math] в link-cut дереве, а в левом — те что выше. Обнулив указатель на левого ребенка [math]v[/math] и на родителя в левом поддереве, получим требуемое.

function cut(v: tree):
    expose(v)
    [math]\vartriangle[/math]w(left(v)) += [math]\vartriangle[/math]w(v)
    [math]\vartriangle[/math]min(v) [math]=[/math] min{0, [math]\vartriangle[/math]min(right(v)) + [math]\vartriangle[/math]w(right(v))}
    parent(left(v)) [math]=[/math] null
    left(v) [math]=[/math] null

Оценка времени работы

Назовем ребро из [math]u[/math] в её родителя [math]v[/math] тяжелым, если количество детей [math]u[/math] равное [math]d(u) \gt \dfrac{1}{2} d(v)[/math].

Лемма:
На пути от вершины до корня не больше [math]\log n[/math] легких ребер.
Доказательство:
[math]\triangleright[/math]
Пусть [math]m[/math] — количество вершин в дереве с корнем в вершине, в которой мы сейчас находимся. Поднимаясь по легкому ребру, [math]m[/math] увеличивается в два раза, поэтому, пройдя больше [math]\log n[/math] легких ребер, получим [math]m \gt n[/math]. Значит, в дереве не больше [math]\log n[/math] легких ребер.
[math]\triangleleft[/math]

Операция [math]\mathrm{expose(u)}[/math] осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за [math]M[/math]. Найдем количество преобразований сделанных в течение [math]\mathrm{expose(u)}[/math]. Пусть [math]H[/math] — множество всех тяжелых ребер, [math]L[/math] — все легкие ребра, [math]S \rightarrow D[/math] — множество сплошных ребер, преобразованных в пунктирные в течение одного [math]\mathrm{expose}[/math], [math]D \rightarrow S[/math] — множество пунктирных ребер, преобразованных в сплошные.

[math]M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|[/math]

По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем [math]\log n[/math].

Обозначим за [math]F[/math] лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, a [math]F'[/math] — лес, получившийся из [math]F[/math] после одного вызова [math]\mathrm{expose}[/math]. Определим потенциал [math]\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|[/math], [math]\Delta \Phi _{a}[/math] — увеличение [math]\Phi _{a}[/math] после одной операции [math]\mathrm{expose}[/math].

Лемма:
[math]V = M + \Delta \Phi _{a} \leqslant 1 + 2\log n [/math]
Доказательство:
[math]\triangleright[/math]
[math]V = M + \Delta \Phi _{a}\\ = M + |H \cap S \rightarrow D| - |H \cap D \rightarrow S| \\ \leqslant M + |L \cap D \rightarrow S| - |H \cap D \rightarrow S| \\ = 2 \cdot |L \cap D \rightarrow S| \\ =2 \cdot \log n [/math]
[math]\triangleleft[/math]


Теперь проанализируем [math]M[/math]. Используя тот факт, что начальное значение [math]\Phi _{a}[/math] не превосходит [math]n - 1[/math], приходим к тому, что для деревьев с [math]n[/math] вершинами, по крайней мере за [math]n - 1[/math] операцию [math]\mathrm{expose}[/math], среднее [math]M[/math] на одну операцию будет не больше, чем [math]1 + 2\log n[/math].

Докажем, что амортизационная стоимость операции [math]\mathrm{expose}[/math] равна [math]O(\log n)[/math].

Пусть [math]s(v)[/math] — количество вершин в поддеревьях [math]v[/math] ( здесь имеется в виду splay-дерево пути, который строится в ходе выполнения [math]\mathrm{expose}[/math]), [math]r(v) = \log s(v)[/math]. По лемме стоимость i-той операции [math]\mathrm{splay}[/math] не превосходит [math]1 + 3 \cdot (r(t) - r(v))[/math]. Это приводит к тому, что амортизационная стоимость [math]\mathrm{expose}[/math] ограничена следующим значением:

[math]3 \cdot \log n - 3 \cdot \log (s(v)) + M[/math]

Здесь [math]M = O(\log n)[/math], поэтому амортизационная стоимость [math]\mathrm{expose}[/math] равна [math]O(\log n)[/math].

Применение

LCA

C помощью link-cut-дерева можно найти наименьшего общего предка:

function lca(u: tree, v: tree): tree
    expose(u)
    expose(v)
    return pathparent(splay(u))

Первый вызов [math]\mathrm{expose}[/math] построит путь от [math]u[/math] до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит [math]u[/math], хранится указатель [math]pathparent[/math] на [math]\mathrm{lca}[/math], после [math]\mathrm{splay}(u)[/math] он будет находиться в [math]u[/math].

См. также

Источники информации