On the upper bound on the rotation distance of binary trees
type: Item
instance of: scholarly article
title: On the upper bound on the rotation distance of binary trees
zbMATH Open document ID: 0681.05024
DOI: 10.1016/0020-0190(89)90069-0
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: The rotation distance between two binary search trees \(T_ 1\) and \(T_ 2\) on n nodes is the minimum number of rotations needed to transform \(T_ 1\) into \(T_ 2\). It is known that an upper bound to the rotation distance is 2n-6. The authors present a proof of the bound by a tree transformation algorithm.
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4114656
zbMATH Keywords: binary trees
zbMATH Keywords: rotation distance
zbMATH Keywords: binary search trees
author: Fabrizio Luccio
author: L. Pagli
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90069-0
OpenAlex ID: W1974505029
cites work: A note on some tree similarity measures
cites work: Q3219751
description: scientific article; zbMATH DE number 4114656