𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Restricted rotation distance between binary trees

✍ Scribed by Sean Cleary

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
93 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Restricted rotation distance between pairs of rooted binary trees measures differences in tree shape and is related to rotation distance. In restricted rotation distance, the rotations used to transform the trees are allowed to be only of two types. Restricted rotation distance is larger than rotation distance, since there are only two permissible locations to rotate, but is much easier to compute and estimate. We obtain linear upper and lower bounds for restricted rotation distance in terms of the number of interior nodes in the trees. Further, we describe a linear-time algorithm for estimating the restricted rotation distance between two trees and for finding a sequence of rotations which realizes that estimate. The methods use the metric properties of the abstract group known as Thompson's group F .

πŸ“œ SIMILAR VOLUMES

Right-arm rotation distance between bina
Right-arm rotation distance between binary trees
✍ Jean Marcel Pallo πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 88 KB

We consider a transformation on binary trees, named right-arm rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes of the right arm of the trees are allowed. Using ordinal tools, we give an efficient algorithm for computing the right-arm rotation d

Distances between trees
Distances between trees
✍ T. Margush πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 520 KB
Twist–Rotation Transformations of Binary
Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions
✍ Ming Li; Louxin Zhang πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 101 KB

The paper studies the computational complexity and efficient algorithms for the twist᎐rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary Ž . operation. The main results are 1 a full binary tree with

On rotations in fringe-balanced binary t
On rotations in fringe-balanced binary trees
✍ Hosam M. Mahmoud πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 451 KB

We employ a P6lya urn to model rotations in a random fringe-balanced binary search tree. We show that asymptotically the number of rotations to construct a tree of size n has a normal distribution with mean +n and variance sn. Exact results for mean and variance are developed in the process. @ 1998