Browse Prior Art Database

Construction of Minimal Comparison 2,3 Trees

IP.com Disclosure Number: IPCOM000088763D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Rosenberg, AL: AUTHOR [+2]

Abstract

Disclosed herein is a technique for constructing, given a set of K keys, a K-key 2,3-tree that is optimal in the sense of requiring the minimum number of comparisons per access on the average. These trees are very different from those constructed in [1], which minimize expected path length per access. These two measures of performance are somewhat complementary in the sense that minimizing comparisons is a prime concern in main memory but is often overshadowed in a paging environment by minimizing path length.

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

Page 1 of 2

Construction of Minimal Comparison 2,3 Trees

Disclosed herein is a technique for constructing, given a set of K keys, a K- key 2,3-tree that is optimal in the sense of requiring the minimum number of comparisons per access on the average. These trees are very different from those constructed in [1], which minimize expected path length per access. These two measures of performance are somewhat complementary in the sense that minimizing comparisons is a prime concern in main memory but is often overshadowed in a paging environment by minimizing path length.

The disclosed technique, which has been validated mathematically, operates in time that is linear in the cardinality of the input set of keys.

A 2,3-tree is a rooted, oriented tree each of whose interior nodes has either 2 or 3 successors and accommodates one less key than successors, and all of whose root-to-leaf paths have the same length.

Keys are stored in the interior nodes of the tree in such a way that the keys in the left (resp., right) subtree of a node are all less (resp., greater) than the key(s) in the node and, in the case of a ternary node, the keys in the central subtree are sandwiched between those in the node. For any node n of a 2,3-tree, father(n) denotes that node whose successor n is, 1st(n) denotes the lesser of n's keys and 2nd(n) denotes the greater of n's keys should such exist. In any transaction in the 2,3-tree, when node n is encountered, first 1st(n) is compared with the sought key. If 1st(n) is not the key sought, either 1st(left successor(n)) or 2nd(n) is compared with the sought key, depending on whether 1st(n) is too big or too small, respectively. [If n is a binary node, the role of 2nd(n) is played by 1st(right successor(n)).] If 2nd(n) is to be compared, then an unsuccessful comparison sends one to 1st(central successor(n)) or 1st(right successor(n)), depending on whether 2nd(n) is too big or too small, respectively. This order of element-access is consonant with Knuth's view of 2,3-trees as an "en-coded version" of binary trees [2, Section 6.2.3]. The regimen further suggests the following definition of the rank of a key in a 2,3-tree.

For each interior node n of the tree, a) rank(1st(n)) = 1 + rank(1st(father(n))) + if n not leftmost son of father (n) and if

father(n) is ternary then 1 b) rank(2nd(n)) = 1 rank(1st(n)) c) rank(1st(root)) = 1. One verifies easily that the rank of a key in a 2,3-tree is the number of comparisons required to access that key. Accordingly, the cost function to be minimized is:

(Image Omitted)

where K is the set of keys stored in the tree, and #K is its cardinality.

1

Page 2 of 2

The Program. This disclosed program takes the form of an executive procedure "build" that governs two subordinate procedures "left" and "right." Informally, th...