wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

level_ancestor (852B)

      1 # Level ancestor
      2 
      3 https://en.wikipedia.org/wiki/Level_ancestor_problem
      4 
      5 Do [preprocessing] on a [tree] and compute a [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth])
      6 
      7 Can be done with linear preprocessing of the tree and constant query time
      8 - cf for instance [bender2004level]
      9 - [alstrup2000improved] for [trees] under [updates], and to find the node with minimum weight on the path between two nodes when the tree is weighted
     10 - [bender2003level]: simplified version of the problem
     11   - decompose into [microtrees]
     12 
     13 Less efficient solutions:
     14 - [jump_pointers]: store logarithmically many pointers to go up by powers of two
     15 - [long_path_decomposition]
     16 
     17 Up: [data_structure], [ancestor]
     18 
     19 Aliases: level ancestor problem
     20 
     21 See also: [skip_list]