Редактирование: Link-Cut Tree

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Динамические деревья''' (англ.''dynamic tree'') используются в двух областях: [[Определение сети, потока|потоки]] и динамические графы.
+
Динамические деревья (англ.''link-cut trees'') используются в двух областях: потоки и динамические графы.
 
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
 
В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи.  Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
+
В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Изменения нужно быстро обрабатывать, а также уметь проверять связность, искать диаметр. Динамические деревья являются инструментом, который позволяет легко решать эти задачи.  Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''.
  
'''Link-cut tree''' {{---}} это структура данных, которая хранит [[Дерево, эквивалентные определения |лес деревьев]] и позволяет выполнять следующие операции:
+
'''Link-cut tree''' (''dynamic tree'') {{---}} это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
* '''<tex>\mathrm{min(v)}</tex>''' {{---}} искать минимум на пути от вершины до корня,
+
* '''min(v)''' {{---}} искать минимум на пути от вершины до корня;
* '''<tex>\mathrm{add(v, c)}</tex>''' {{---}} прибавлять константу на пути от вершины до корня,
+
* '''add(v, c)''' {{---}} прибавлять константу на пути от вершины до корня;
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} подвешивать одно дерево на другое,
+
* '''link(u, w)''' {{---}} подвешивать одно дерево на другое;
* '''<tex>\mathrm{cut(v)}</tex>''' {{---}} отрезать дерево с корнем в вершине <tex>\mathrm{v}</tex>.
+
* '''cut(v)''' {{---}} отрезать дерево с корнем в вершине v.
 
Среднее время выполнения каждой операции {{---}} <tex>O(\log n)</tex>. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
 
Среднее время выполнения каждой операции {{---}} <tex>O(\log n)</tex>. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
  
Строка 14: Строка 14:
  
 
[[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
 
[[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
* '''<tex>\mathrm{add(v, c)}</tex>'''  и '''<tex>\mathrm{min(v)}</tex>''' {{---}} прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня),  
+
* прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня),  
* '''<tex>\mathrm{cut(v)}</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-деревья]], в которых ключи выбираются равными глубине вершины.  
  
Строка 44: Строка 44:
  
 
==Link-cut tree==
 
==Link-cut tree==
Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо сплошным, либо пунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>pathparent</tex>.
+
Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>pathparent</tex>.
 
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
 
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
  
 
===expose(u)===
 
===expose(u)===
Ключевая операция в link-cut-деревьях {{---}} <tex>\mathrm{expose(u)}</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от <tex>u</tex> до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее сплошное ребро пунктирным ребром.
+
Ключевая операция в link-cut-деревьях {{---}} <tex>\mathrm{expose(u)}</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от <tex>u</tex> до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее solid-ребро dashed-ребром.
 
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
 
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
  
 
  '''function''' expose(u: '''tree'''):
 
  '''function''' expose(u: '''tree'''):
 
     splay(u)
 
     splay(u)
     v <tex>=</tex> u
+
     v <tex>\leftarrow</tex> u
 
     '''while''' v <tex> \ne </tex> root
 
     '''while''' v <tex> \ne </tex> root
         p <tex>=</tex> pathparent(v)        <font color=green>//получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня</font>
+
         p <tex>\leftarrow</tex> pathparent(v)        <font color=green>//получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня</font>
 
         splay(p)                  <font color=green>//теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,</font>
 
         splay(p)                  <font color=green>//теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,</font>
         parent(right(p)) <tex>=</tex> null  <font color=green>//поэтому правое поддерево p делаем новым путем</font>
+
         parent(right(p)) <tex>\leftarrow</tex> null  <font color=green>//поэтому правое поддерево p делаем новым путем</font>
         pathparent(right(p)) <tex>=</tex> p
+
         pathparent(right(p)) <tex>\leftarrow</tex> p
         right(p) <tex>=</tex> v            <font color=green>//объединяем оставшийся и построенный пути</font>
+
         right(p) <tex>\leftarrow</tex> v            <font color=green>//объединяем оставшийся и построенный пути</font>
 
         <tex>\vartriangle</tex>w(v) -= <tex>\vartriangle</tex>w(p)
 
         <tex>\vartriangle</tex>w(v) -= <tex>\vartriangle</tex>w(p)
         <tex>\vartriangle</tex>min(p) <tex>=</tex> min{0, <tex>\vartriangle</tex>min(left(p)) + <tex>\vartriangle</tex>w(left(p)), <tex>\vartriangle</tex>min(right(p)) + <tex>\vartriangle</tex>w(right(p))}
+
         <tex>\vartriangle</tex>min(p) <tex>\leftarrow</tex> min{0, <tex>\vartriangle</tex>min(left(p)) + <tex>\vartriangle</tex>w(left(p)), <tex>\vartriangle</tex>min(right(p)) + <tex>\vartriangle</tex>w(right(p))}
         pathparent(v) <tex>=</tex> null
+
         pathparent(v) <tex>\leftarrow</tex> null
         v <tex>=</tex> p
+
         v <tex>\leftarrow</tex> p
 
     splay(u)
 
     splay(u)
  
Строка 75: Строка 75:
  
 
===min(v)===
 
===min(v)===
Построим splay-дерево для пути и сравним вес корня <tex>v</tex> c минимумом в левом поддереве:
+
Построим splay-дерево для пути и сравним минимум корня <tex>v</tex> c минимумом в левом поддереве:
  '''function''' min(v: '''tree'''): '''int'''
+
  '''int''' min(v : '''tree'''):
 
     expose(v)
 
     expose(v)
 
     '''if''' <tex>\vartriangle</tex>min(left(v)) + <tex>\vartriangle</tex>w(left(v)) < <tex>\vartriangle</tex>w(v)
 
     '''if''' <tex>\vartriangle</tex>min(left(v)) + <tex>\vartriangle</tex>w(left(v)) < <tex>\vartriangle</tex>w(v)
Строка 86: Строка 86:
 
Если <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>u</tex> становится родителем <tex>v</tex>.
  
  '''function''' link(v: '''tree''', u: '''tree'''): '''tree'''
+
  '''tree''' link(v: '''tree''', u: '''tree'''):
 
     expose(v) <font color=green>    //теперь v {{---}} корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)</font>
 
     expose(v) <font color=green>    //теперь v {{---}} корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)</font>
 
     expose(u)
 
     expose(u)
 
     <tex>\vartriangle</tex>w(u) -= <tex>\vartriangle</tex>w(v) <font color=green>//чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве</font>
 
     <tex>\vartriangle</tex>w(u) -= <tex>\vartriangle</tex>w(v) <font color=green>//чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве</font>
     parent(u) <tex>=</tex> v <font color=green>//                                              2. обновляем <tex>\vartriangle</tex>w, <tex>\vartriangle</tex>min</font>
+
     parent(u) <tex>\leftarrow</tex> v <font color=green>//                                              2. обновляем <tex>\vartriangle</tex>w, <tex>\vartriangle</tex>min</font>
     left(v) <tex>=</tex> u
+
     left(v) <tex>\leftarrow</tex> u
     <tex>\vartriangle</tex>min(v) <tex>=</tex> min{0, <tex>\vartriangle</tex>min(u) + <tex>\vartriangle</tex>w(u), <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w((right(v)))}
+
     <tex>\vartriangle</tex>min(v) <tex>\leftarrow</tex> min{0, <tex>\vartriangle</tex>min(u) + <tex>\vartriangle</tex>w(u), <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w((right(v)))}
 
     '''return''' v
 
     '''return''' v
  
 
===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'''):
 
     expose(v)
 
     expose(v)
 
     <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>\leftarrow</tex> min{0, <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w(right(v))}
     parent(left(v)) <tex>=</tex> null
+
     left(v) <tex>\leftarrow</tex> null
     left(v) <tex>=</tex> null
+
     parent(left(v)) <tex>\leftarrow</tex> null
  
 
==Оценка времени работы==
 
==Оценка времени работы==
Назовем ребро из <tex>u</tex> в её родителя <tex>v</tex> тяжелым, если количество детей <tex>u</tex> равное <tex>d(u) > \dfrac{1}{2} d(v)</tex>.
+
Назовем ребро из <tex>u</tex> в её родителя <tex>v</tex> тяжелым, если количество детей <tex>u</tex> равное <tex>d(u) > \frac{1}{2} d(v)</tex>.
 
{{Лемма
 
{{Лемма
 
|id = Lemma1
 
|id = Lemma1
Строка 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>u</tex> осуществляется с помощью последовательности преобразований dashed-ребра в solid-ребро и другого solid-ребра в dashed-ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество solid-ребер, преобразованных в dashed в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество dashed-ребер, преобразованных в solid.
  
 
<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>
  
По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем <tex>\log n</tex>.
+
По лемме, количество легких dashed-ребер, преобразованных в solid, будет не больше, чем <tex>\log n</tex>.
  
Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, a <tex>F'</tex> {{---}} лес, получившийся из <tex>F</tex> после одного вызова <tex>\mathrm{expose}</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|</tex>, <tex>\Delta \Phi _{a}</tex> {{---}} увеличение <tex>\Phi _{a}</tex> после одной операции <tex>\mathrm{expose}</tex>.
+
Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solid, либо dashed, a <tex>F'</tex> {{---}} лес, получившийся из <tex>F</tex> после одного вызова <tex>\mathrm{expose}</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|</tex>, <tex>\Delta \Phi _{a}</tex> {{---}} увеличение <tex>\Phi _{a}</tex> после одной операции <tex>\mathrm{expose}</tex>.
  
 
{{Лемма
 
{{Лемма
Строка 137: Строка 137:
  
  
Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>\mathrm{expose}</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2\log n</tex>.
+
Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>\mathrm{expose}</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2\log n</tex>
  
Докажем, что [[Амортизационный анализ|амортизационная стоимость операции]] <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>
  
Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.
+
Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>
  
 
==Применение==
 
==Применение==
 
===LCA===
 
===LCA===
 
C помощью link-cut-дерева можно найти наименьшего общего предка:
 
C помощью link-cut-дерева можно найти наименьшего общего предка:
  '''function''' lca(u: '''tree''', v: '''tree'''): '''tree'''
+
  '''tree''' lca(u: '''tree''', v: '''tree'''):
 
     expose(u)
 
     expose(u)
 
     expose(v)
 
     expose(v)
Строка 158: Строка 158:
  
 
==См. также==
 
==См. также==
* [[Метод двоичного подъема]]
+
*[[Метод двоичного подъема| Метод двоичного подъема]]
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
+
*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн | Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
* [[Алгоритм Шибера-Вишкина]]
+
*[[Алгоритм Шибера-Вишкина | Алгоритм Шибера-Вишкина]]
 
 
 
==Источники информации==
 
==Источники информации==
* [http://www.lektorium.tv/lecture/14464 А.С. Станкевич, "Дополнительные главы алгоритмов"]
+
*[http://www.lektorium.tv/lecture/14464 А.С. Станкевич, Дополнительные главы алгоритмов, Link-cut trees]
* [https://sites.google.com/site/indy256/algo/link-cut-tree-lca Реализация LCA на link-cut дереве]
+
*[https://sites.google.com/site/indy256/algo/link-cut-tree-lca Реализация LCA на link-cut дереве]
* [http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf D. Sleator and R. Tarjan, "A Data Structure for Dynamic Trees"]
+
*[http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf D. Sleator and R. Tarjan. A Data Structure for Dynamic Trees]
* [http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf Jeff Erickson. Lecture 7. Link-Cut Trees]
+
*[http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf Jeff Erickson. Lecture 7. Link-Cut Trees]
* [http://planarity.org/Klein_splay_trees_and_link-cut_trees.pdf Optimization Algorithms for Planar Graphs. Splay trees and link-cut trees]
+
*[http://planarity.org/Klein_splay_trees_and_link-cut_trees.pdf Optimization Algorithms for Planar Graphs. Splay trees and link-cut trees]
* [http://en.wikipedia.org/wiki/Link/cut_tree Wikipedia {{---}} Link/cut tree]
+
*[http://en.wikipedia.org/?title=Link/cut_tree Wikipedia {{---}} Link/cut tree]
  
 +
[[Категория: Дискретная математика и алгоритмы]]
  
[[Категория: Алгоритмы и структуры данных]]
 
 
[[Категория: Задача о наименьшем общем предке]]
 
[[Категория: Задача о наименьшем общем предке]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: