Rake-Compress деревья — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 3 участников)
Строка 8: Строка 8:
 
==Идея==
 
==Идея==
 
===Описание===
 
===Описание===
Дано некоторое дерево <tex>T</tex>, алгоритм ''сжатия дерева'' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> в несколько раундов:
+
Пусть дано некоторое дерево <tex>T</tex>, для которого мы хотим выполнять описанные выше операции. Рассмотрим алгоритм '''сжатия дерева''' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом. Алгоритм сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> в несколько раундов:
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
 
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Строка 16: Строка 16:
 
</tr></table>
 
</tr></table>
  
Сжатие дерева требует линейного времени и логарифмическое число раундов.
+
Сжатие дерева требует линейного времени и логарифмическое число раундов.<br>
 
+
Для выбора вершин, которые будут удалены во время операции <tex>\mathrm{Compress}</tex>, применяется следующий метод: для каждой вершины генерируется рандомный бит и вершина добавляется в множество удаляемых только в том случае, когда она имеет одного ребёнка, бит для неё равен <tex>0</tex>, а для родителя и ребёнка равен <tex>1</tex>.<br>
 
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>.<br>Разобьём все вершины дерева на три группы:  
 
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>.<br>Разобьём все вершины дерева на три группы:  
 
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
 
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
Строка 39: Строка 39:
 
|about=2
 
|about=2
 
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
 
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
|proof=Математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex> (так как все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex>). Из предыдущей леммы получаем:<br>
+
|proof=Все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex> (так как мы рассматриваем три бита при выборе вершин и добавляем вершину в множество удаляемых только когда эти биты для родителя, вершины и ребёнка соответственно равны <tex>1</tex>, <tex>0</tex> и <tex>1</tex>).<br>
 +
Таким образом математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex>. Из предыдущей леммы получаем:<br>
 
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
 
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
 
}}
 
}}
Строка 56: Строка 57:
 
[[Файл:RC_graph_contraction.png|350px|right|thumb|Алгоритм сжатия дерева <tex>T</tex>.]]
 
[[Файл:RC_graph_contraction.png|350px|right|thumb|Алгоритм сжатия дерева <tex>T</tex>.]]
 
На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>:
 
На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>:
* Операция <tex>\mathrm{Rake}</tex> удаляет лист и ребро, смежное с ним и сохраняет в соседях данные {{---}} метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
+
* Операция <tex>\mathrm{Rake}</tex> удаляет лист и ребро, смежное с ним, сохраняя в соседях данные: метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
* Операция <tex>\mathrm{Compress}</tex> удаляет вершины, имеющую ровно одного сына, и два смежных с ней ребра. Например, для вершины <tex>v</tex> c сыном <tex>w</tex> и родителем <tex>u</tex> будут удалены рёбра <tex>(u, v)</tex> и <tex>(v, w)</tex>. После этого добавляется ребро <tex>(u, w)</tex>, а данные вершины <tex>v</tex> и удалённых рёбер сохраняются в соседние вершины {{---}} метку удалённой вершины, сохранённые данные и веса удалённых рёбер.
+
* Операция <tex>\mathrm{Compress}</tex> удаляет вершины, имеющие ровно одного сына, и смежные им рёбра. Например, для вершины <tex>v</tex> c сыном <tex>w</tex> и родителем <tex>u</tex> будут удалены рёбра <tex>(u, v)</tex> и <tex>(v, w)</tex>. После этого добавляется ребро <tex>(u, w)</tex>, а данные вершины <tex>v</tex> и удалённых рёбер (метка удалённой вершины, сохранённые данные и веса удалённых рёбер) сохраняются в соседние вершины.  
  
 
Например, для приведённого дерева на первом раунде сжатия применяется операция <tex>\mathrm{Rake}</tex> для вершин <tex>a</tex>, <tex>d</tex>, <tex>n</tex>, <tex>k</tex> и операция <tex>\mathrm{Compress}</tex> для <tex>g</tex> и <tex>i</tex>.<br><br>
 
Например, для приведённого дерева на первом раунде сжатия применяется операция <tex>\mathrm{Rake}</tex> для вершин <tex>a</tex>, <tex>d</tex>, <tex>n</tex>, <tex>k</tex> и операция <tex>\mathrm{Compress}</tex> для <tex>g</tex> и <tex>i</tex>.<br><br>
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один кластер. Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров.<br><br>На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <tex>A</tex>, полученный после сжатия вершины <tex>a</tex> содержит вершины <tex>a</tex>, <tex>b</tex> и ребро <tex>(a, b)</tex>; сжатая вершина <tex>g</tex> создает кластер <tex>G</tex>, содержащий эту вершину и рёбра <tex>(f, g)</tex> и <tex>(g, h)</tex>. Во втором раунде, после сжатия вершины <tex>b</tex> создается кластер <tex>B</tex>, содержащий кластер <tex>A</tex> и ребро <tex>(b, c)</tex>.<br>Представление сжатого дерева в виде кластеров:
+
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер''' (англ. ''cluster''). Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров.<br><br>На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <tex>A</tex>, полученный после сжатия вершины <tex>a</tex> содержит вершины <tex>a</tex>, <tex>b</tex> и ребро <tex>(a, b)</tex>; сжатая вершина <tex>g</tex> создает кластер <tex>G</tex>, содержащий эту вершину и рёбра <tex>(f, g)</tex> и <tex>(g, h)</tex>. Во втором раунде, после сжатия вершины <tex>b</tex> создается кластер <tex>B</tex>, содержащий кластер <tex>A</tex> и ребро <tex>(b, c)</tex>.<br>Представление сжатого дерева в виде кластеров:
 
[[Файл:RC_graph_clusters.png|400px|left|thumb|Кластеризованное дерево <tex>T</tex>.]]
 
[[Файл:RC_graph_clusters.png|400px|left|thumb|Кластеризованное дерево <tex>T</tex>.]]
  
Строка 84: Строка 85:
  
  
Определим кластер как поддерево исходного дерева, порожденное множеством вершин.  
+
 
{{Определение
+
 
|definition=Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется ''граничной вершиной'', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>.  
+
 
}}
+
Определим кластер как поддерево исходного дерева, порожденное множеством вершин.
{{Определение
+
 
|definition=''Граница кластера'' {{---}} множество граничных вершин кластера. ''Степень кластера'' {{---}} количество граничных вершин кластера.
+
Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>. '''Граница кластера''' {{---}} множество граничных вершин кластера, а '''степень кластера''' {{---}} количество граничных вершин кластера.
}}
 
  
 
Например, для рассматриваемого дерева кластер <tex>A</tex> имеет границу <tex>\{b\}</tex> и степень <tex>1</tex>, а кластер <tex>G</tex> имеет границу <tex>\{f, g\}</tex> и степень <tex>2</tex>. При сжатии дерева все кластеры, кроме последнего, имеют степени <tex>1</tex> и <tex>2</tex>. Свойством алгоритмом сжатия является то, что:
 
Например, для рассматриваемого дерева кластер <tex>A</tex> имеет границу <tex>\{b\}</tex> и степень <tex>1</tex>, а кластер <tex>G</tex> имеет границу <tex>\{f, g\}</tex> и степень <tex>2</tex>. При сжатии дерева все кластеры, кроме последнего, имеют степени <tex>1</tex> и <tex>2</tex>. Свойством алгоритмом сжатия является то, что:
Строка 175: Строка 175:
 
         diffCntChild = diffSumChild = 0
 
         diffCntChild = diffSumChild = 0
 
      
 
      
     '''func''' addChild(v)''':'''
+
     '''func''' addChild(v: '''int''')''':'''
 
         diffCntChild++
 
         diffCntChild++
 
         diffSumChild += v
 
         diffSumChild += v
 
    
 
    
     '''func''' removeChild(v)''':'''
+
     '''func''' removeChild(v: '''int''')''':'''
 
         diffCntChild--
 
         diffCntChild--
 
         diffSumChild -= v
 
         diffSumChild -= v
Строка 190: Строка 190:
  
 
  '''struct''' RCTree(n: '''int''')''':'''
 
  '''struct''' RCTree(n: '''int''')''':'''
     rand = RandBitsGenerator()
+
     '''RndGen''' rand = RandBitsGenerator()
     time = 0
+
     '''int''' time = 0
 
     '''for''' i = 0 '''to''' n
 
     '''for''' i = 0 '''to''' n
 
         lastUpdateTime[i] = 0
 
         lastUpdateTime[i] = 0
Строка 213: Строка 213:
  
 
Таким образом, алгоритм построения дерева выглядит следующим образом:
 
Таким образом, алгоритм построения дерева выглядит следующим образом:
  '''func''' build(parent: '''int[]''')''':'''
+
  '''func''' build(parent: '''int[n]''')''':'''
    n = parent.size
 
 
     alive = <tex>\{0 \dots n - 1\}</tex>
 
     alive = <tex>\{0 \dots n - 1\}</tex>
     layer = 0
+
     '''int''' layer = 0
     '''for''' i = 0 '''to''' n
+
     '''for''' i = 0 '''to''' n                                             <font color="green">// заполним таблицу вершинами изначального дерева</font>
 
         cells[i].add(Cell(parent[i]))
 
         cells[i].add(Cell(parent[i]))
 
     '''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
 
     '''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
 
         nextAlive = <tex>\emptyset</tex>
 
         nextAlive = <tex>\emptyset</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
             c = getCellForVertex(v)                        <font color="green">// получить клетку таблицы, соответствующую вершине</font>
+
             '''Cell''' c = getCellForVertex(v)                        <font color="green">// получить клетку таблицы, соответствующую вершине</font>
 
             '''if''' shouldRemoveVertex(c, rand, layer)
 
             '''if''' shouldRemoveVertex(c, rand, layer)
 
                 '''if''' c.cntChild == 1
 
                 '''if''' c.cntChild == 1
Строка 233: Строка 232:
 
         alive = nextAlive
 
         alive = nextAlive
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
 
         '''for''' <tex>v \in \mathrm{alive}</tex>
             newCell = getCellForVertex(v).clone().appleChanges()
+
             '''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
 
             cells[v].add(newCell)
 
             cells[v].add(newCell)
 
         layer++
 
         layer++
 
===Операции удаления и добавления ребра===
 
===Операции удаления и добавления ребра===
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу. А именно, найдем момент времени, когда вершина сжимается к родителю. Рассмотрим, какие вершины поменяются при сжатии данной. Это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию. Также пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка. Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из из- менившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.<br>
+
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:
 +
# Найдем момент времени, когда вершина сжимается к родителю.  
 +
# Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.  
 +
# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.  
 +
# Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.<br>
 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. <br>Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.<br>Алгоритм обновления дерева:
 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. <br>Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.<br>Алгоритм обновления дерева:
 
  '''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
 
  '''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
Строка 247: Строка 250:
 
     cells[v].cntChild--
 
     cells[v].cntChild--
 
     cells[v].sumChild -= u
 
     cells[v].sumChild -= u
     layer = 0
+
     '''int''' layer = 0
 
     '''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
 
     '''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
 
         '''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
 
         '''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
 
             markAffected(v)
 
             markAffected(v)
 
         '''for''' <tex>v \in \mathrm{affected}</tex>
 
         '''for''' <tex>v \in \mathrm{affected}</tex>
             c = getCellForVertex(v)
+
             '''Cell''' c = getCellForVertex(v)
 
             '''if''' shouldRemoveVertex(v)
 
             '''if''' shouldRemoveVertex(v)
            cells[v].size = layer + 1
+
                cells[v].size = layer + 1
            '''if''' c.cntChild == 1
+
                '''if''' c.cntChild == 1
                getCellForVertex(c.sumChild).newParent = c.parent
+
                    getCellForVertex(c.sumChild).newParent = c.parent
                getCellForVertex(c.parent).addChild(c.sumChild)
+
                    getCellForVertex(c.parent).addChild(c.sumChild)
                markAffected(c.sumChild)
+
                    markAffected(c.sumChild)
            '''if''' c.parent <tex>\neq</tex> v
+
                '''if''' c.parent <tex>\neq</tex> v
                getCellForVertex(c.parent).removeChild(v)
+
                    getCellForVertex(c.parent).removeChild(v)
                markAffected(c.parent)
+
                    markAffected(c.parent)
            affected.remove(v)
+
                affected.remove(v)
 
         '''for''' <tex>v \in \mathrm{affected}</tex>
 
         '''for''' <tex>v \in \mathrm{affected}</tex>
             newCell = getCellForVertex(v).clone().applyChanges()
+
             '''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
 
             cells[v][layer + 1] = newCell
 
             cells[v][layer + 1] = newCell
 
         layer++
 
         layer++
 
   
 
   
  '''func''' markAffected(v: '''int''')''':'''
+
  '''func''' markAffected(v: '''int''')''':'''               <font color="green">// пометить вершину как изменившуюся</font>
 
     '''if''' lastUpdateTime[v] == time
 
     '''if''' lastUpdateTime[v] == time
         '''return'''                         <font color="green">// вершина уже помечена</font>
+
         '''return'''                           <font color="green">// вершина уже помечена</font>
 
     lastUpdateTime[v] = time
 
     lastUpdateTime[v] = time
 
     affected.add(v)
 
     affected.add(v)
 
     removeEffectOfVertex(v)
 
     removeEffectOfVertex(v)
 
   
 
   
  '''func''' removeEffectOfVertex(v: '''int''')''':'''
+
  '''func''' removeEffectOfVertex(v: '''int''')''':'''       <font color="green">// удалить отметку о том, что вершина была помечена изменившийся</font>
     layer = cells[v].size
+
     '''int''' layer = cells[v].size
     c = cells[v][layer]
+
     '''Cell''' c = cells[v][layer]
 
     '''if''' c.parent == v
 
     '''if''' c.parent == v
 
         '''return'''
 
         '''return'''
Строка 285: Строка 288:
 
         cells[c.sumChild].newParent = v
 
         cells[c.sumChild].newParent = v
  
==Возможность параллельного построения==
+
==Сравнение с Link-Cut Tree==
Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров.
+
Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем <tex>\mathrm{LC}</tex> деревья. <br>
 +
Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров.<br>
 +
Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.
  
 
==См. также==
 
==См. также==
Строка 296: Строка 301:
 
==Источники информации==
 
==Источники информации==
 
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
 
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических <tex>\mathrm{Rake-Compress}</tex> деревьев в случае отсутствия ограничения на степени вершин]
+
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
 
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
 
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
 
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]
 
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]

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

Задача, которая решается с помощью динамических деревьев, формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:

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


Идея

Описание

Пусть дано некоторое дерево [math]T[/math], для которого мы хотим выполнять описанные выше операции. Рассмотрим алгоритм сжатия дерева (англ. tree-contraction algorithm), предложенный Миллером и Райфом. Алгоритм сжимает [math]T[/math] в одну вершину путем применения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] в несколько раундов:

  • [math]\mathrm{Rake}[/math] — все листья дерева сжимаются к своим родителям,
  • [math]\mathrm{Compress}[/math] — выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
Операция [math]\mathrm{Rake}[/math]
Операция [math]\mathrm{Compress}[/math]

Сжатие дерева требует линейного времени и логарифмическое число раундов.
Для выбора вершин, которые будут удалены во время операции [math]\mathrm{Compress}[/math], применяется следующий метод: для каждой вершины генерируется рандомный бит и вершина добавляется в множество удаляемых только в том случае, когда она имеет одного ребёнка, бит для неё равен [math]0[/math], а для родителя и ребёнка равен [math]1[/math].
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math].
Разобьём все вершины дерева на три группы:

  • [math]T_0[/math] — входящая степень равна нулю,
  • [math]T_1[/math] — входящая степень равна одному,
  • [math]T_2[/math] — входящая степень больше одного.
Лемма (1):
[math]T_2 \leqslant T_0 - 1[/math].
Доказательство:
[math]\triangleright[/math]

Докажем по индукции по высоте дерева.

  • База
    Для дерева из одной вершины утверждение верно.
  • Переход
    Пусть утверждение доказано для деревьев высоты меньше [math]h[/math]. Докажем для дерева высоты ровно [math]h[/math]. Рассмотрим степень корня:
    Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты [math]h - 1[/math].
    Если у дерева несколько поддеревьев, то имеем:
    [math]T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)[/math]  [math] \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1[/math].
[math]\triangleleft[/math]

Заметим, что для леса деревьев лемма также справедлива.

Лемма (2):
После применения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] к лесу, математическое ожидание количества вершин в нём не превосходит [math]\dfrac{7}{8}[/math] от их исходного числа.
Доказательство:
[math]\triangleright[/math]

Все листья будут удалены после операции [math]\mathrm{Rake}[/math], а каждая вершина, у которой ровно один сын, будет удалена с вероятностью [math]\dfrac{1}{8}[/math] после операции [math]\mathrm{Compress}[/math] (так как мы рассматриваем три бита при выборе вершин и добавляем вершину в множество удаляемых только когда эти биты для родителя, вершины и ребёнка соответственно равны [math]1[/math], [math]0[/math] и [math]1[/math]).
Таким образом математическое ожидание количества удаленных вершин [math]\mathrm{deleted} = T_0 + \dfrac{T_1}{8}[/math]. Из предыдущей леммы получаем:

[math]\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)[/math].
[math]\triangleleft[/math]
Теорема:
Математическое ожидание количества операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math], которые будут выполнены до полного сжатия дерева, равно [math]O(\log{n})[/math], где [math]n[/math] — общее количество вершин.
Доказательство:
[math]\triangleright[/math]
Из леммы 2 известно, что после каждой итерации применения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] число вершин в среднем уменьшается в константное число раз. Значит, количество итераций в среднем ограничено [math]O(\log{n})[/math].
[math]\triangleleft[/math]

Для конкретного применения можно предположить, что рёбра дерева имеют вес, а вершины имеют метки.

Пример операций

В качестве примера сжатия дерева рассмотрим следующее взвешенное дерево:

Исходное дерево [math]T[/math].
Алгоритм сжатия дерева [math]T[/math].

На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math]:

  • Операция [math]\mathrm{Rake}[/math] удаляет лист и ребро, смежное с ним, сохраняя в соседях данные: метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
  • Операция [math]\mathrm{Compress}[/math] удаляет вершины, имеющие ровно одного сына, и смежные им рёбра. Например, для вершины [math]v[/math] c сыном [math]w[/math] и родителем [math]u[/math] будут удалены рёбра [math](u, v)[/math] и [math](v, w)[/math]. После этого добавляется ребро [math](u, w)[/math], а данные вершины [math]v[/math] и удалённых рёбер (метка удалённой вершины, сохранённые данные и веса удалённых рёбер) сохраняются в соседние вершины.

Например, для приведённого дерева на первом раунде сжатия применяется операция [math]\mathrm{Rake}[/math] для вершин [math]a[/math], [math]d[/math], [math]n[/math], [math]k[/math] и операция [math]\mathrm{Compress}[/math] для [math]g[/math] и [math]i[/math].

Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один кластер (англ. cluster). Изначально вершины и рёбра составляют базовый кластер. Операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] формируют большие кластеры из нескольких меньших кластеров.

На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер [math]A[/math], полученный после сжатия вершины [math]a[/math] содержит вершины [math]a[/math], [math]b[/math] и ребро [math](a, b)[/math]; сжатая вершина [math]g[/math] создает кластер [math]G[/math], содержащий эту вершину и рёбра [math](f, g)[/math] и [math](g, h)[/math]. Во втором раунде, после сжатия вершины [math]b[/math] создается кластер [math]B[/math], содержащий кластер [math]A[/math] и ребро [math](b, c)[/math].
Представление сжатого дерева в виде кластеров:

Кластеризованное дерево [math]T[/math].













Определим кластер как поддерево исходного дерева, порожденное множеством вершин.

Для кластера [math]C[/math] скажем, что вершина [math]v[/math] из [math]C[/math] называется граничной вершиной, если [math]v[/math] смежная с вершинами не из [math]C[/math]. Граница кластера — множество граничных вершин кластера, а степень кластера — количество граничных вершин кластера.

Например, для рассматриваемого дерева кластер [math]A[/math] имеет границу [math]\{b\}[/math] и степень [math]1[/math], а кластер [math]G[/math] имеет границу [math]\{f, g\}[/math] и степень [math]2[/math]. При сжатии дерева все кластеры, кроме последнего, имеют степени [math]1[/math] и [math]2[/math]. Свойством алгоритмом сжатия является то, что:

  • операции [math]\mathrm{Rake}[/math] создают кластеры со степенью [math]1[/math],
  • операции [math]\mathrm{Compress}[/math] создают кластеры со степенью [math]2[/math],
  • финальный кластер имеет степень [math]0[/math].

Процесс сжатия исходного дерева может быть представлен в виде нового дерева, называемого [math]\mathrm{RC-tree}[/math].
Пример такого дерева для рассматриваемого исходного дерева:

RC-tree для дерева [math]T[/math].


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

Реализация

Хранение

Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math]. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.
Пример таблицы для следующей последовательности операций:

Пример выполнения операций.
Шаг Операция [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math]
4 [math]\mathrm{Rake}[/math] Родитель: —
Дети: [math]\emptyset[/math]
3 [math]\mathrm{Compress}[/math] Родитель: —
Дети: [math]\{3\}[/math]
Родитель: [math]1[/math]
Дети: [math]\emptyset[/math]
2 [math]\mathrm{Rake}[/math] Родитель: —
Дети: [math]\{2\}[/math]
Родитель: [math]1[/math]
Дети: [math]\{3\}[/math]
Родитель: [math]2[/math]
Дети: [math]\emptyset[/math]
1 Родитель: —
Дети: [math]\{2\}[/math]
Родитель: [math]1[/math]
Дети: [math]\{3\}[/math]
Родитель: [math]2[/math]
Дети: [math]\{4\}[/math]
Родитель: [math]3[/math]
Дети: [math]\emptyset[/math]



Для того, чтобы выбирать множество вершин для применения операции [math]\mathrm{Compress}[/math] будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны [math]0[/math], [math]1[/math] и [math]1[/math] соответственно.

Рассмотрим более подробно, как необходимо хранить клетки таблицы [math]\mathrm{Rake-Compress}[/math] дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за [math]O(\log{n})[/math], нужно производить операции с множеством детей за [math]O(1)[/math].

Рассмотрим, в каких случаях можно сжать вершину:

  • если детей у вершины больше одного, то ее точно нельзя сжать,
  • если у неё нет детей, то ее можно сжать только во время операции [math]\mathrm{Rake}[/math]
  • если у вершины один ребёнок, то её возможно сжать во время операции [math]\mathrm{Compress}[/math].

Чтобы определить, можно ли применить операцию [math]\mathrm{Compress}[/math] к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции [math]\mathrm{Compress}[/math]). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен [math]1[/math]. Поэтому, всю информацию о множестве можно хранить с помощью двух величин — хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за [math]O(1)[/math] получать номер ребёнка и за [math]O(1)[/math] обновлять множество детей.

Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за [math]O(1)[/math].

Псевдокод хранения клетки таблицы:

  • [math]\mathrm{id}[/math] — номер вершины,
  • [math]\mathrm{parent}[/math] — родитель вершины,
  • [math]\mathrm{cntChild}[/math] — количество детей вершины,
  • [math]\mathrm{sumChild}[/math] — сумма номеров детей,
  • [math]\mathrm{newParent}[/math] — новый родитель вершины после изменений,
  • [math]\mathrm{diffCntChild}[/math] и [math]\mathrm{diffSumChild}[/math] — изменения, произведенные с полями [math]\mathrm{cntChild}[/math] и [math]\mathrm{sumChild}[/math] соответственно.
struct Cell:
    int id, parent, cntChild, sumChild
    int newParent, diffCntChild, diffSumChild
    
    func applyChanges():
        parent = newParent
        sumChild += diffSumChild
        cntChild += diffCntChild
        diffCntChild = diffSumChild = 0
    
    func addChild(v: int):
        diffCntChild++
        diffSumChild += v
 
    func removeChild(v: int):
        diffCntChild--
        diffSumChild -= v

Для хранения [math]\mathrm{Rake-Compress}[/math] дерева будем использовать следующие данные:

  • [math]\mathrm{cells[]}[/math] — список клеток, которые ей соответствуют, для каждой вершины,
  • [math]\mathrm{rand}[/math] — генератор псевдослучайных чисел,
  • [math]\mathrm{time}[/math] — счётчик количества примененных операций по изменению структуры леса,
  • [math]\mathrm{lastUpdateTime[]}[/math] — массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.
struct RCTree(n: int):
    RndGen rand = RandBitsGenerator()
    int time = 0
    for i = 0 to n
        lastUpdateTime[i] = 0
        cells[i] = []

Кроме запросов о структуре леса, [math]\mathrm{Rake-Compress}[/math] деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве. Для этого в клетках таблицы [math]\mathrm{Rake-Compress}[/math] дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.

Построение

Рассмотрим, как работает алгоритм построения [math]\mathrm{Rake-Compress}[/math] дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:

bool shouldRemoveVertex(c: Cell, rand, layer: int):
    if c.cntChild == 0
        return true
    if c.cntChild > 1 or c.parent == c.id
        return false
    if getCellForVertex(c.sumChild).cntChild == 0
        return false
    if rand.getBit(c.id, layer) == 0 and rand.getBit(c.sumChild, layer) == 1 and rand.getBit(c.parent, layer) == 1:
        return true
    return false

Таким образом, алгоритм построения дерева выглядит следующим образом:

func build(parent: int[n]):
    alive = [math]\{0 \dots n - 1\}[/math]
    int layer = 0
    for i = 0 to n                                              // заполним таблицу вершинами изначального дерева
        cells[i].add(Cell(parent[i]))
    while [math]\mathrm{alive} \neq \emptyset[/math]
        nextAlive = [math]\emptyset[/math]
        for [math]v \in \mathrm{alive}[/math]
            Cell c = getCellForVertex(v)                        // получить клетку таблицы, соответствующую вершине
            if shouldRemoveVertex(c, rand, layer)
                if c.cntChild == 1
                    getCellForVertex(c.sumChild).newParent = c.parent
                    getCellForVertex(c.parent).addChild(c.sumChild)
                if c.parent [math]\neq[/math] v
                    getCellForVertex(c.parent).remove(v)
            else
                nextAlive.add(v)
        alive = nextAlive
        for [math]v \in \mathrm{alive}[/math]
            Cell newCell = getCellForVertex(v).clone().applyChanges()
            cells[v].add(newCell)
        layer++

Операции удаления и добавления ребра

Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:

  1. Найдем момент времени, когда вершина сжимается к родителю.
  2. Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
  3. Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
  4. Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках.

Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние.
Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения [math]\mathrm{cntChild}[/math], [math]\mathrm{sumChild}[/math] и [math]\mathrm{newParent}[/math] нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя.
Алгоритм обновления дерева:

func changeTree([math](u, v)[/math]: Edge):
    time = time + 1
    affected = [math]\emptyset[/math]
    markAffected(u)                     // пусть из дерева было удалено ребро [math](u, v)[/math]
    markAffected(v)
    cells[u].parent = u
    cells[v].cntChild--
    cells[v].sumChild -= u
    int layer = 0
    while [math]\mathrm{affected} \neq \emptyset[/math]
        for [math]v \in \mathrm{affectedOnLayer}[/math]
            markAffected(v)
        for [math]v \in \mathrm{affected}[/math]
            Cell c = getCellForVertex(v)
            if shouldRemoveVertex(v)
                cells[v].size = layer + 1
                if c.cntChild == 1
                    getCellForVertex(c.sumChild).newParent = c.parent
                    getCellForVertex(c.parent).addChild(c.sumChild)
                    markAffected(c.sumChild)
                if c.parent [math]\neq[/math] v
                    getCellForVertex(c.parent).removeChild(v)
                    markAffected(c.parent)
                affected.remove(v)
        for [math]v \in \mathrm{affected}[/math]
            Cell newCell = getCellForVertex(v).clone().applyChanges()
            cells[v][layer + 1] = newCell
        layer++

func markAffected(v: int):               // пометить вершину как изменившуюся
   if lastUpdateTime[v] == time
       return                            // вершина уже помечена
   lastUpdateTime[v] = time
   affected.add(v)
   removeEffectOfVertex(v)

func removeEffectOfVertex(v: int):       // удалить отметку о том, что вершина была помечена изменившийся
   int layer = cells[v].size
   Cell c = cells[v][layer]
   if c.parent == v
       return
   cells[c].parent.removeChild(v)
   if c.cntChild == 1
       cells[c.parent].addChild(c.sumChild)
       cells[c.sumChild].newParent = v

Сравнение с Link-Cut Tree

Для Link-Cut деревьев (основанных на splay-деревьях), как и для [math]\mathrm{Rake-Compress}[/math] деревьев, время работы операций [math]\mathrm{link}[/math] и [math]\mathrm{cut}[/math][math]O(\log{n})[/math]. В реальности [math]\mathrm{RC}[/math] деревья оказываются медленнее, чем [math]\mathrm{LC}[/math] деревья.
Отличительной особенностью [math]\mathrm{RC}[/math] деревьев является возможность параллельного построения: операции [math]\mathrm{Rake}[/math] и [math]\mathrm{Compress}[/math] можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за [math]O(1)[/math], то [math]\mathrm{Rake-Compress}[/math] дерево можно построить за [math]O(\log{n})[/math] в модели PRAM[1] в случае наличия [math]\Omega(n)[/math] процессоров.
Кроме этого, [math]\mathrm{Rake-Compress}[/math] деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.

См. также

Примечания

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