On Euler tour trees

Revision en1, by 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

History

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