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$
  • $\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. May 16 '17 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 May 16 '17 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. May 16 '17 at 22:35
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, privacy policy and cookie policy

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