Browse Prior Art Database

Ordinal Access to the Element of Data Structures Based on Binary Trees

IP.com Disclosure Number: IPCOM000086106D
Original Publication Date: 1976-Jul-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 38K

Publishing Venue

IBM

Related People

Giaccone, LF: AUTHOR [+2]

Abstract

Data structures based on binary trees often preserve the collating sequence of keys, in order that elements represented by the keys may be retrieved sequentially as well as individually by key. It may also be desirable to retrieve individual elements from such a data structure, based upon their positions in the ordered set. Fig. 1 illustrates the method.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 96% of the total text.

Page 1 of 2

Ordinal Access to the Element of Data Structures Based on Binary Trees

Data structures based on binary trees often preserve the collating sequence of keys, in order that elements represented by the keys may be retrieved sequentially as well as individually by key. It may also be desirable to retrieve individual elements from such a data structure, based upon their positions in the ordered set. Fig. 1 illustrates the method.

Ordinal access is accomplished by including in each inner vertex of the tree a field L, which contains the count of the elements in the left subtree of the vertex.

To search for the Xth element, L is examined at the tree source, and if it is larger than X, i.e., (L>X), then traverse the left edge; if not, i.e. (L< or = X), traverse the right edge and subtract L from X. (Note that the lowest ordered element is the zero th.)

Insertions are made in the normal fashion and the backpath is traced to the source, adding 1 to the count at each vertex for which the insertion is a left successor. Deletions require that 1 be subtracted on the backpath.

Example: X=24 (find the 24th element of Fig. 1) 1. Begin at (a), the source vertex. 2. L>X, i.e., (28>24). 3. Yes, traverse left to (b). 4. L>X, i.e., (23>24). 5. No, traverse right to (c). 6. Subtract L from X (X = 24-23). 7. L>X, i.e., (3>1). 8. Yes, traverse left to (d). 9. L>X, i.e., (2>1). 10. Yes, traverse left to (f). 11. L>X,
i.e., (1>1). 12. No, traverse right. 13. 24th element found.

1

Page 2 of 2...