Rotation Distance
Report ID: TR-003-85Author: Tarjan, Robert E. / Sleator, Daniel D. / Thurston, William P.
Date: 1985-07-00
Pages: 11
Download Formats: |PDF|
Abstract:
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.