234
правки
Изменения
→Ссылки
Первый вызов <tex>\mathrm{expose}</tex> построит путь от <tex>u</tex> до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит <tex>u</tex>, хранится указатель <tex>pathparent</tex> на <tex>\mathrm{lca}</tex>, после <tex>\mathrm{splay}(u)</tex> он будет находиться в <tex>u</tex>.
==СсылкиСм. также==*[[Метод двоичного подъема| Метод двоичного подъема]]*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн | Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]*[[Алгоритм Шибера-Вишкина | Алгоритм Шибера-Вишкина]]==Источники информации==*[http://www.lektorium.tv/lecture/14464 А.С.Станкевич, Дополнительные главы алгоритмов, Link-cut 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]
