01445337

a

01445337 Evans, William Kirkpatrick, David Restructuring ordered binary trees. Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 477-486 (2000). 2000 Philadelphia, PA: SIAM EN restructuring an ordered binary tree displacement efficient algorithms Summary: We consider the problem of restructuring an ordered binary tree $T$, preserving the in-order sequence of its nodes, so as to reduce its height to some target value $h$. Such a restructuring necessarily involves the downward displacement of some of the nodes of $T$. Our results, focusing both on the maximum displacement over all nodes and on the maximum displacement over leaves only, provide (i) an explicit tradeoff between the worst-case displacement and the height restriction (including a family of trees that exhibit the worst case displacements) and (ii) efficient algorithms to achieve height-restricted restructuring while minimizing the maximum node displacement.