✦ LIBER ✦

Right-arm rotation distance between binary trees

✍ Scribed by Jean Marcel Pallo

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 88 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00283-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 distance between two binary trees, i.e., the minimum number of rightarm rotations necessary to transform one tree into the other.

📜 SIMILAR VOLUMES

Restricted rotation distance between bin

Restricted rotation distance between binary trees

✍ Sean Cleary 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 93 KB

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 rotati

Counterexamples in measuring the distanc

Counterexamples in measuring the distance between binary trees

✍ J.P. Jarvis; J.K. Luedeman; D.R. Shier 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 325 KB