[Link Cut Tree] 3. 연산 (2) 이번 글에서는 트리에서 루트나 부모를 구하는 방법, 노드의 깊이를 구하는 방법을 알아보겠습니다. node * findRoot(node * x) { access(x); while (x->l) x = x->l; splay(x); return x; } FindRoot 연산은 x가 포함된 트리의 루트를 반환하는 연산입니다.일단 x에 access하고, Splay Tree에서 가장 깊이가 작은 노드가 루트가 됩니다.따라서 x에서 왼쪽으로 계속 이동할 수 없을 때까지 이동해주면 루트를 찾을 수 있습니다.amortized log n 시간복잡도를 보장하기 위해서 찾은 루트를 splay해줍니다. node * parent(node * x) { access(x); x = x->l; if (!x) return 0; while .. 더보기 이전 1 ··· 18 19 20 21 22 23 24 다음