3
$\begingroup$

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:

  1. Link(A,B)

  2. Link(B,C)

  3. Link(C,D)

Following instructions of https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/MIT6_851S12_L19.pdf, I get enter image description here

However, when we draw preferred paths, I should get

enter image description here

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

Thanks in advance.

$\endgroup$
1
$\begingroup$

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).

step1

  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$.

step2

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

step3

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Leafar May 18 '17 at 5:56
  • $\begingroup$ I ask this because after cut(B,A), B is not a tree root... $\endgroup$ – Leafar May 18 '17 at 6:03
  • $\begingroup$ 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. $\endgroup$ – Leafar May 18 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.