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

Bubble Structure and Operation to Facilitate Tree Traversal

IP.com Disclosure Number: IPCOM000041636D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 6 page(s) / 42K

Publishing Venue

IBM

Related People

Chang, H: AUTHOR

Abstract

This article describes a bubble hardware and an algorithm including swap/edit gates and a level indicator for performing tree traversal. I. Introduction A binary tree may be defined recursively as consisting of a root node, a left binary subtree, and a right binary subtree. Binary trees are often encountered in computer data and program structures; their applications and mathematical properties have been discussed extensively (e.g., see Knuth 1). In different hardwares the binary tree is represented, implemented and manipulated differently. For example, a complete binary tree (each node with two identical subtrees except for the terminal nodes) can be represented by labelling a node i, its left successor node 2i, and its right successor node 2i+1, starting with the root node labelled as 1.

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

Page 1 of 6

Bubble Structure and Operation to Facilitate Tree Traversal

This article describes a bubble hardware and an algorithm including swap/edit gates and a level indicator for performing tree traversal. I. Introduction A binary tree may be defined recursively as consisting of a root node, a left binary subtree, and a right binary subtree. Binary trees are often encountered in computer data and program structures; their applications and mathematical properties have been discussed extensively (e.g., see Knuth 1). In different hardwares the binary tree is represented, implemented and manipulated differently. For example, a complete binary tree (each node with two identical subtrees except for the terminal nodes) can be represented by labelling a node i, its left successor node 2i, and its right successor node 2i+1, starting with the root node labelled as 1. Such a representation can be implemented conveniently in a random-access memory. Berkling 2 Ùhas described tree traversal schemes and controller design for such a representation. Updating of any node in such a representation will entail relabelling all its successor nodes. In the magnetic disk storage, pointers are used to link a node to its left and right successors. Traversal schemes for such a representation are given in Knuth 1 . Again, updating entails extensive alteration of pointers. In addition, the pointers consume storage space. With the promise of low cost and high speed for shift- register memories such as bubbles and CCDs, novel device structures have been proposed to store and manipulate binary trees. For example, Kluge [3] has suggested shift registers with permutation paths to facilitate tree traversals. He did not specify hardware structures, but perhaps assumed a device like a bubble ladder [4]. Elaborate logic schemes (as compared to what this paper shall present) have been described, together with storage structures and control mechanisms. Although in principle feasible, the hardware assumed has not been produced as yet. Here, the binary tree storage and traversals are based on major/ minor loop bubble chips in production today. Moreover, both node projection and level indexing are used to capture completely the tree structure information. Such complete information greatly simplifies tree traversals and other manipulations. In general, we believe that the flexibility of bubble hardware structure allows natural mapping of data structures into the hardware, resulting both in speed improvement and programming simplification. Moreover, we attempt to utilize major/minor loop configurations since that is presently available in commercial bubble chips. Chang and Nigam [5] have mapped a data base into bubble chips according to the relational data model. The use of columnized storage and off-chip marker loops are found to shorten search time and improve output efficiency. A balanced binary tree can be mapped into a major/minor loop chip and on-chip editing facilities can be i...