Browse Prior Art Database

TREE REBALANCING IN OPTIMAL TIME AND SPACE

IP.com Disclosure Number: IPCOM000128486D
Original Publication Date: 1984-Oct-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

Stout, Quentin F.: AUTHOR [+4]

Abstract

We give a simple algorithm which takes an arbitrary binary search tree and rebalances it to form another of minimal height, using time linear in the number of nodes and only a constant amount of additional space (beyond that used to store the initial tree). This algorithm is therefore optimal in its use of both time and space. Previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees. When the nodes of the tree are stored in an array, a simple addition to our algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using linear time and constant space.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1

TREE REBALANCING IN OPTIMAL TIME AND SPACE [ title ]

Quentin F. Stout and Bette L. Warren CRL-TR-42-84

October 1984 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000

Tree Rebalancing in Optimal Time and Space [ title ]

by Quentin F. Stout2

Dept. of Electrical Engineering and Computer Science University of Michigan Ann Arbor, MI 48109

Bette L. Warren Department of Mathematics and Computer Science Eastern Michigan University Ypsilanti, MI 48197

ABSTRACT

We give a simple algorithm which takes an arbitrary binary search tree and rebalances it to form another of minimal height, using time linear in the number of nodes and only a constant amount of additional space (beyond that used to store the initial tree). This algorithm is therefore optimal in its use of both time and space. Previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees. When the nodes of the tree are stored in an array, a simple addition to our algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using linear time and constant space.

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

2 Research partially supported by National Science Foundation grant MCS-83-01019.

University of Michigan Computing Research Laboratory Page 1 Oct 01, 1984

Page 2 of 9

TREE REBALANCING IN OPTIMAL TIME AND SPACE

[ Chapter ] 1. INTRODUCTION

A binary search tree is a conceptually simple, reasonably efficient, and widely used structure in which to maintain ordered data. Because the fundamental operations of insertion, deletion, and searching require accessing nodes along a single path from the root, for randomly generated trees of n nodes (using the standard insertion algorithm), the expected times to perform these operations are Θ(log(n)). Unfortunately, it is possible for a binary tree to have very long branches, and the worst case times are Θ(n).

In order to avoid the worst-case linear times is necessary to keep the tree balanced, that is, it should not be allowed to have unnecessarily long branches. This problem has been studied intensely, and there are many notions of balance and balancing strategies, such as AVL trees, weight-balanced trees, self- organizing trees, etc.3. Here we are concerned with perhaps the simplest strategy: periodically rebalance the entire tree to make an equivalent one of minimal height. This strategy has been discussed by many authors, and several algorithms have been offered4; recently Chang and Iyengar5 surveyed this work and presented additional algorithms. Despite all of this work, no previous algorithm could be applied to an arbitrary binary search tree and perfor...