Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-003-85
Rotation Distance
Authors: Sleator, Daniel D., Tarjan, Robert E., Thurston, William P.
Date:July 1985
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.