6533b853fe1ef96bd12ad46a
RESEARCH PRODUCT
Right-arm rotation distance between binary trees
Jean Marcel Pallosubject
Tree rotationBinary treeData_MISCELLANEOUSWeight-balanced treeRandom binary treeComputer Science ApplicationsTheoretical Computer ScienceCombinatoricsBinary search treeGeometry of binary search treesSignal ProcessingTernary search treeRotation (mathematics)Information SystemsMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2003-08-01 | Information Processing Letters |