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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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
  

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

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

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

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