On Euler tour trees

Правка en1, от ifsmirnov, 2015-06-07 00:33:21

TL;DR: is it possible to construct an Euler tour tree which supports LCA, subtree sum and rerooting?

Euler tour is a method for representing a rooted undirected tree as a number sequence. There are several common ways to build this representation. Usually only the first is called the Euler tour; however, I don't know any specific names for others and will call them Euler tours too. All of them have some pros and cons. I want to discuss if we can build an algorithm which contains benefits from each one.

The first way is to write down all edges of the tree, directed, in order of DFS. This is how Euler tour is defined on, for example, Wikipedia.

     1
    / \
   2   5
  / \
 3   4

[1-2] [2-3] [3-2] [2-4] [4-2] [2-1] [1-5] [5-1]

The second way is to store vertices. Each vertex is added to the array twice: when we descent into it and when we leave it.

     1
    / \
   2   5
  / \
 3   4

1 2 3 3 4 4 2 5 5 1

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский ifsmirnov 2015-06-07 02:13:58 32
ru2 Русский ifsmirnov 2015-06-07 02:12:49 93
en4 Английский ifsmirnov 2015-06-07 02:12:10 103
ru1 Русский ifsmirnov 2015-06-07 02:10:41 4065 Первая редакция перевода на Русский
en3 Английский ifsmirnov 2015-06-07 01:47:42 2 Tiny change: ' first(v)) in h]$. Why?' -> ' first(v))\ in\ h]$. Why?'
en2 Английский ifsmirnov 2015-06-07 01:46:30 5048 Tiny change: 'ooting|\n|-|-|-|-|-|-|\n|1|edge' - (published)
en1 Английский ifsmirnov 2015-06-07 00:33:21 1045 Initial revision (saved to drafts)