Browse Prior Art Database

# Replacement Selection Tree for Variable Length Records

IP.com Disclosure Number: IPCOM000076984D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 14K

IBM

## Related People

Parkinson, JCG: AUTHOR

## Abstract

In sorting variable-length records in an internal sort it will often happen that a long record is written out, and several short records are available to fill the space it occupied. The size of the tree should then be allowed to grow to include as many as possible of the short records.

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

Page 1 of 2

Replacement Selection Tree for Variable Length Records

In sorting variable-length records in an internal sort it will often happen that a long record is written out, and several short records are available to fill the space it occupied. The size of the tree should then be allowed to grow to include as many as possible of the short records.

Suppose the record selection area contains records with the keys 7, 5, 3, 9, 1, 2, 6, 8, 0 and 4. The tree for sorting to ascending order is then: 0 1 Tree: 3 6 5 2 8 4 7 9 Records: 7 5 3 9 1 2 6 8 0 4.

Suppose a new record is to be added to the tree under the 2. The new record should be compared with the 2, and unless it compares low it remains where it is. If it compares low it should be exchanged with the 2 and then compared and possibly exchanged with the 1. Note that it should not be compared with the 3. This is because the 3 reached its node from the left-hand branch. It is, therefore, known to be less than any key on its node's left branch, but has no known relationship to the records on the right-hand branch.

It is assumed that the current winner, the 0, is not available for exchanging. Anything comparing low to it is relegated to the next sequence.

Only if a record is exchanged as a result of one compare is another compare made. Moreover, in moving up through the tree, a compare is made only if the record found reached its node via the same branch that is now being followed.

One possible method of recording paths is to use a switch at each node. Another is to associate with each node a pointer to the immediate descendant from whose subtree the record currently at the node came.

With this technique a route must be traced down from the top of the tree and then up again on selection of a record. In the normal loser tree, a pointer is associated with each record indicating at which leaf the record entered the tree, and the tree need only be traced from bottom to top.

The main difficulty in providing such pointers with a growable tree, lies in providing paths from the bottom of the tree when the tree is not full. Thus, suppose the tree had been initialized in an environment with space for 22 pointers, the result would have been: 0 1 3 6 7 9 a b c d e f h i j k m n where a, b,
.... n are...