Блог пользователя freto

Link cut trees kth ancestor

Автор freto, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -13 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +8 Проголосовать: не нравится

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]

→ Ответить