Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Construction of Optimal 2,3 Trees

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

Publishing Venue

IBM

Related People

Miller, RE: AUTHOR [+3]

Abstract

Disclosed herein is a method for constructing 2,3-trees that are optimal in the sense of having minimal expected time for retrieving stored items.

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 53% of the total text.

Page 1 of 3

Construction of Optimal 2,3 Trees

Disclosed herein is a method for constructing 2,3-trees that are optimal in the sense of having minimal expected time for retrieving stored items.

Balanced search trees are popular data structures for storing data sets with distinct ordered keys, because such trees afford one efficient (roughly logarithmic) access to stored data. The class of balanced search trees, called 2,3-trees (also often called 3,2-trees), is particularly attractive among balanced tree organizations because of the extremely simple bookkeeping that suffices to maintain 2,3-trees through the various transactions (such as access, insert, delete) that typically occur with large data sets.

However, 2,3-trees are sensitive to the way the original data base is organized in far greater measure than most other balanced tree organizations. Specifically, although a 2,3-tree containing n keys affords one both expected and worst-case access of roughly log(2) (n+1), the behavior of a "poorly constructed" n-item tree can differ from that of a "well-constructed" n-item tree by as much as a factor of log(2)3 (= 1.584962501...). The procedure described herein constructs, given the size n of the initial set of data, a 2,3-tree for the data whose expected time of access is minimal among n-item 2,3-trees.

For the sake of self-containment, it is stated that a 2,3-tree is a rooted, oriented tree each of whose nonleaf nodes has either two or three sons, and all of whose root-to-leaf paths have the same length. Data is organized in a 2,3-tree in such a manner that each nonleaf node, with s successors (s = 2,3), contains s- 1 data items. All the data in the left (resp., right) subtree emanating from a node have keys strictly less than (resp., greater than) the keys of the data in the node. In case a node has three successors -- and, necessarily, two data items -- the keys of the data in the central subtree emanating from the node are strictly sandwiched between the keys of the data items in the nodes. Items are located by searching down from the root of the tree until the key is located. The time to access an item in a tree is thus proportional to the number of nodes visited to find its...