|
TR-003-85
Rotation Distance |
|
| Authors: | Sleator, Daniel D., Tarjan, Robert E., Thurston, William P. |
| Date: | July 1985 |
| Pages: | 11 |
| Download Formats: | [PDF] |
In this note we summarize our recent results on rotation distance, a distance measure on binary trees with computer science applications. Our main result is that the maximum rotation distance between any two n-node binary trees is at most 2n - 6 for n >/= 11, and this bound is tight for infinitely many n. |
|