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

Constructing a Tree Using It's Timestamp.
Автор dusht0814, история, 8 лет назад, По-английски

I'm interested in whether we can Construct a tree if we know the Starting Time and Ending Time of all the Vertices.

For Example:

  • Number of Vertices :4
  • Starting time ST[i]:2 4 1 3
  • Ending time FT[i]:2 4 4 4

The Tree Looks Like:

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

There exists a unique tree for each VALID start and end time arrays.

A small hint for the tree construction : The direct parent of a node i shall be a node j with maximum start time, following the constraint that start[j] < start[i] and end[j] ≥ end[i].

There exists such a node j for each node i, except the root.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

A node having s_t == f_t must be leaf node. First insert the node having s_t == 1 into the tree and set pos(a variable) equal to this node. This "pos" will tell u the the position where to append the next_node into the tree. Along with it maintain a parent array. After appending a node(say i) at pos, check if s_t[i] == f_t[i], If yes then backtrack to the parent until u find a parent having f_t greater than the s_t of node i. This will become the new pos pointer. And if "no" then pos will be set to i for next node.In this way u can insert all nodes.

→ Ответить