Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions
✍ Scribed by Ming Li; Louxin Zhang
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 101 KB
- Volume
- 32
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 n labeled leaves can be transformed into any other in at most 3n log n q 2 n twist and rotation operations, Ž . 2 deciding the twist᎐rotation distance between two binary trees is NP-complete, Ž . and 3 the twist᎐rotation transformation can be approximated with ratio 6 log n q 4 in polynomial time for full binary trees with n uniquely labeled leaves. ᮊ 1999 Academic Press