freto's blog

Link cut trees kth ancestor

By freto, history, 7 years ago, In English

I have been studying link cut trees nowadays but don't seem to figure out how to find the kth ancestor of a particular node. Can this be done? If yes then how?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

Can you find the kth ancestor in a splay tree? A link-cut tree is just a splay tree.

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

    i do not understand. well yes it is just a splay tree, but how to get the kth ancestor query along with link/cut queries supported?

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

    can you please be clear about whether it can be done or not?

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

when you're asked for kth ancestor of node V:

  1. Store in each node the size of its subtree (in the splay tree not the original tree)

  2. Access V

  3. Now there should be >= K nodes to the left of node V, go to the left child of V and use sub tree sizes to find kth node from the right

How to do it:

Let's say you have L nodes to left and R nodes to the right

if R == K-1: current node is the kth ancestor

if R > K-1: kth ancestor is in right subtree

if R < K-1: kth ancestor is in left subtree, when you go left, you're objective changes to finding the (K — R — 1)th node (as K nodes from the right and root node were discarded)

In case the root was fixed, you can just do dfs from the root and use a stack to keep track of all ancestors, when you get to Node V, the answer is in stack[size — K]

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

    kth ancestor is not the same as the kth element in an ordered sequence.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      Not the kth node in the whole tree, I meant the kth in left subtree from the right as they are keyed by depth

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

        hmm what you say seems correct...are you sure about it?

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

          Yes

          Assuming all nodes are connected, access(v) will place v in the same preferred path as the root node, since all nodes in the path are keyed by depth and (usually) stored in a splay tree, splaying v will leave all its ancestors in the left subtree

          I personally don't suggest using linkcut tree unless necessary, if you can get by just dfs and a stack, it will be much faster and easier to code and debug

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

            and how would you maintain the size of subtree, after a cut and link operation alot of data has to be changed? do all the operations still remain logn??

            → Reply