if I have two binary search trees with the same keys(n keys) but not identical, I can get from the first tree to the other by maximum n tree rotations. how can I prove it? for example I can get from tree 1 to tree 2 by one rotation:
Asked
Active
Viewed 108 times
1 Answers
1
This is probably the same thing as the famous problem posed by Daniel Sleator, Robert Tarjan, and William Thurston asking for the diameter of the associahedra or the diameter of the rotation graph on plane binary trees.
The correct diameter is rather $2n - 2$.
This has been solved by Pournin in 2012 in the language of flips of triangulations, see his article.
F. C.
- 512