Изменения

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

Rake-Compress деревья

455 байт добавлено, 00:45, 17 мая 2016
Нет описания правки
alive = <tex>\{0 \dots n - 1\}</tex>
layer = 0
'''for''' i = 0 '''to''' n <font color="green">// заполним таблицу вершинами изначального дерева</font>
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
newCell = getCellForVertex(v).clone().appleChangesapplyChanges()
cells[v].add(newCell)
layer++
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 <tex>\neq</tex> v getCellForVertex(c.parent).removeChild(v) markAffected(c.parent) affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
newCell = getCellForVertex(v).clone().applyChanges()
layer++
'''func''' markAffected(v: '''int''')''':''' <font color="green">// пометить вершину как изменившуюся</font>
'''if''' lastUpdateTime[v] == time
'''return''' <font color="green">// вершина уже помечена</font>
lastUpdateTime[v] = time
affected.add(v)
removeEffectOfVertex(v)
'''func''' removeEffectOfVertex(v: '''int''')''':''' <font color="green">// удалить отметку о том, что вершина была помечена изменившийся</font>
layer = cells[v].size
c = cells[v][layer]
188
правок

Навигация