Browse Prior Art Database

A Comparison of Tree Balancing Algorithms

IP.com Disclosure Number: IPCOM000128703D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 16 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

J.L. Baer: AUTHOR [+4]

Abstract

Several algorithms height-balance (i.e. AVL and extensions), weight-balance (i.e. BB and WB), total restructuring - for building balanced binary search trees are compared. The criterions for compari-sons encompass theoretical aspects (e.g. path lengths) implementation independent, and machine/algorithm dependent measures (e.g. run-time). A detailed analysis of code is also presented at a level believed to be language and compiler independent. Judging upon the quality of the re-sulting trees and the overhead spent on building them, some guidelines are given for an efficient use of the methods. If insertion and sub- seelp-lev.1t -a-ran the only, operations of intere9t t'hen "pure" AVL trees present the overall best qualities. Key words: binary search trees, AVL trees, weight-balance trees, path length, analysis of algorithms, information storage and retrieval CR category: 3.7, 3.72, 3.74, 5.31

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

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Comparison of Tree Balancing Algorithms

J.L. Baer and B. Schwab

Technical Report No. 75-08-08

Department of Computer Science University of Washington Seattle, Washington 98195

August 8, 1975

This work was supported in part by NSF Grant: GJ-41164 and by a Burroughs Fellowship Grant to Ms. Schwab.

Abstract

Several algorithms height-balance (i.e. AVL and extensions), weight-balance (i.e. BB and WB), total restructuring - for building balanced binary search trees are compared. The criterions for compari-sons encompass theoretical aspects (e.g. path lengths) implementation independent, and machine/algorithm dependent measures (e.g. run-time). A detailed analysis of code is also presented at a level believed to be language and compiler independent. Judging upon the quality of the re-sulting trees and the overhead spent on building them, some guidelines are given for an efficient use of the methods. If insertion and sub- seelp-lev.1t -a-ran the only, operations of intere9t t'hen "pure" AVL trees present the overall best qualities.

Key words: binary search trees, AVL trees, weight-balance trees, path length, analysis of algorithms, information storage and retrieval CR category: 3.7, 3.72, 3.74, 5.31

Introduction.

Binary Search trees (abbreviated b.s.t.'s) represent an important technique to handle structures such as files and directories, dictionaries and symbol tables. Nievergelt [81 gives a comprehensive survey of the methods used to create and modify b.s.t.'s as well as some pertinent an-alytical results on the efficiency of these methods. Figure 1 provides a classification of the b.s.t. types and references to previous works

-the study of non- in this area. In this paper we restrIct ourselves i6 weighted b.s.t's.

The random growth of a b.s.t. can lead, in the worst case., to a (linked) linear list. Hence, several algorithms have been devised to balance or restructure the tree while it is built, i.e. to maintain it close to its optimal form. The three main methods to do this - height-balance, weight- balance and total restructuring - will be introduced in ~the next section. We shall stress some aspects of the algorithms not covered previously in the literature.

The main thrust of this paper is to compare these various methods. Path length measures have already been used to assess the "goodness" of the resulting tree. In supplement, we introduce

University of Washington Page 1 Dec 31, 1975

Page 2 of 16

A Comparison of Tree Balancing Algorithms

some implementation in-dependent factors which affect the work generated to produce the trees. It will be seen in section III that theoretical consideration as well

This work was supported in part by NSF Grant GJ-41164 and by a Burroughs Fellowship Grant to Ms. Schwab. as results of simulation experiments are sufficient to justify balancing techniques but not discriminating enough. to make a judgment between them.

In the next secti...