faiyaz26's blog

Link Cut tree Question !!
By faiyaz26, 11 years ago, In English

I am learning link cut tree. I have seen the research paper and other slides.

But i have a question about this DS. Can LC Tree answer the number of childs under a root's subtree efficienty ? I mean, if I link root of a tree under a node, then if i ask the number of child under the great root, which is root of all the nodes. Can LC answer the question efficiently ? If yes, then how ? How can I propagate the value to all the ancestors ? I have seen one implementation here: 860934

How to modify it ?

Thanks in advance. :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The link-cut trees solves problems in paths, you want know about the amount vertices in a subtree, for this you can use Euler Tour Tree that solves problems in components, and is very close to link-cut trees.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are saying Euler tour than using segment tree to update a range, right ? But I need to update the value to all the ancestors of a node, but if i use euler tour + segment tree, it will update all the child under a node !! isn't it ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i implement euler tour trees using Splay Trees, for the problem that you talk("amount of vertices in a component") is just return the size of a subtree.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        then i need to learn splay tree too. :) Thanks.. another question.

        Can this query be done for dynamic trees ? like adding a child or disconnecting a subtree !

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Splay tree is a type of balanced BSTs that is used in link cut tree so you should learn splay trees before link cut trees after you learn link cut trees you will find answers to your questions

          → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          yes, splay trees are the heart of dinamic trees and you must learn it, not just for uses in dinamic trees with them you can solve many problems. if you implement Euler Tour trees using Segment Trees is just for static trees and you can't do dinamic operations like Link or Cut, for this you must uses a datastructure that allow this as Splay Trees. A example using just Splay Trees look this problem and my solution here.

          → Reply