목록2017/08/21 (1)
The Story of Joon
Link/Cut Tree (2)
Link/Cut Tree (1) 앞선 포스트에서 LCT에 대한 기본적인 내용을 다루었는데, 이번 포스트에서는 LCT가 어떻게 활용될 수 있는지 간단하게만 알아보려고 한다. 보충 자료 같은 느낌의 포스트이다. 1. Link 연산의 확장 원래의 Link 연산은 붙이는 쪽이 represented tree의 루트인 경우에만 가능했다. 그러나 실제로 루트가 아닌 노드를 붙이고 싶을 때도 있을 것이다. 이를 위해서는 represented tree의 루트를 변경하는 작업이 필요하다. 어떤 represented tree의 한 노드를 $v$라고 했을 때, access($v$)를 하면 v에서 루트로 연결되는 preferred path가 생긴다는 점은 이전 포스트에서 알아보았다. 그런데 여기서 주목할 점은 이 preferr..
Computer Science/알고리즘
2017. 8. 21. 17:13