0
$\begingroup$

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree.

The pseudo-code and code for this is:

cut(x):
   access(x);
   parent(left(x)) = null
   left(x) = null

void cut(Node *x){
   access(x);
   x->left->parent = 0;
   x->left = 0;
}

How can we define cut(u,v) for an arbitrary (u,v)?

I.e. how can we code cut(u,v) in such a way that

  1. If (u,v) is not an edge in the represented tree, then do nothing;

  2. If (u,v) is an edge of the represented tree, cut the edge in the represented tree.

The following function may help, it determines the root of the represented tree that contains the node x.

root(x):
   access(x)
   while(left(x) =/= null)
      x = left(x)
   splay(x)

LCT *root(LCT *x){
   access(x);
   while((*x).left != NULL){
       x = (*x).left;
   }
   splay(x);
   return x;
}

Additional reference (code): https://github.com/saadtaame/link-cut-tree

Thanks in advance.

$\endgroup$
3
  • $\begingroup$ I don't understand what your question is. If you are asking how to make a mathematical definition of cut(u,v), you can define a term in any way you want. Only you can tell us what definition you want to use. If your question is about how to implement something in C code, that is off-topic here. Coding questions and programming questions are off-topic here, so we ask that you eliminate all C code and replace it with concise pseudocode and ideas. $\endgroup$
    – D.W.
    Commented May 16, 2017 at 22:14
  • $\begingroup$ First of all, how to determine if a pair (u,v) is an edge of the represented tree. And if it is the case, how to cut this edge. Here code and pseudo-code are essentially the same $\endgroup$
    – Leafar
    Commented May 16, 2017 at 22:34
  • $\begingroup$ I don't think you should assume that everyone here reads C code. We already have a separate site (Stack Overflow) for implementation questions and questions about code. $\endgroup$
    – D.W.
    Commented May 16, 2017 at 22:35

1 Answer 1

2
$\begingroup$

The function $cut(v)$ is only defined for cutting $v$ from its parent for a reason, because this is the only possibility. The represented tree is first and foremost a Tree. By definition, edges will only exist from a parent to a child. Therefore, the only edge you would ever need to cut is from parent to child.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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