I am having some trouble on understanding link-cut trees, so I need some help.

Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:

However, when we draw preferred paths, I should get

Am I doing something wrong when doing access(X)?

I think you might be mixing up the represented tree, $R$, and the auxiliary tree representation of the represented tree, $T$.

Recall the definition of $LINK(v, w)$:

$link(v, w)$ - Makes vertex $v$ a new child of vertex $w$.

This happens in the represented tree. Then to keep the auxiliary representation consistent we make $w$ the left child of $v$ because they are keyed by their depth in the represented tree (i.e. left children are higher, right children are lower in the represented tree). So your proposed linking should happen like so:

1. $link(A, B)$ - Make $A$ the child of $B$ in $R$. Make $B$ the left child of $A$ in $T$ (assumptions are omitted).

1. $link(B, C)$ - Make $B$ the child of $C$ in $R$. Rebalance the splay tree in $T$ and make $C$ left child of $B$.

1. $link(C, D)$ - Similar to step 2.

Then we have the preferred path in the represented tree is simply $D \rightarrow C \rightarrow B \rightarrow A$.

• Thanks for answering. I have another doubt concerning linking. Suppose that we do link(A,B), link(B,C) link(C,D) [as we did] and cut(B,A). Is it possible to link(B,A)? – Leafar May 18 '17 at 5:56
• I ask this because after cut(B,A), B is not a tree root... – Leafar May 18 '17 at 6:03
• I did some research and I found that we can do an operation called 'evert(B)'. It changes the edge direction from B to the root in the represented tree. However, it is not clear how to do this in the link-cut tree. – Leafar May 18 '17 at 15:08