Browse Prior Art Database

Representation of Tree Data Structures for Data Manipulation and Search Operations

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

Publishing Venue

IBM

Related People

Koch, K: AUTHOR

Abstract

The disclosed method refers to the economical mapping of trees, such as the parsing tree in Fig. 1, as matrices into computer memories, in order to permit easy and fast data manipulation and search operations. The matrix structure is statically organized, that means a fixed amount of storage space is required for describing a node, assuming the nonterminal and terminal names have a uniform length.

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

Page 1 of 2

Representation of Tree Data Structures for Data Manipulation and Search Operations

The disclosed method refers to the economical mapping of trees, such as the parsing tree in Fig. 1, as matrices into computer memories, in order to permit easy and fast data manipulation and search operations. The matrix structure is statically organized, that means a fixed amount of storage space is required for describing a node, assuming the nonterminal and terminal names have a uniform length.

The proposed matrix comprises five lines and a number of columns, one column each being required for describing a nonterminal and a terminal node, respectively. The nodes of a tree can be represented in any order and be positioned at any matrix column.

Fig. 2 shows the matrix structure for the parsing tree of Fig. 1, the nodes being represented in the order in which they are visited by preorder traversal (visit root, traverse leftmost subtree, traverse remaining subtrees in preorder). The matrix shown in Fig. 2 is described below. NONTERMINAL NAME/TERMINAL NAME.

For nonterminal nodes the NONTERMINAL NAME denotes the respective nonterminal.

For terminal nodes the TERMINAL NAME denotes the respective terminal. FATHER POINTER.

This line comprises pointers which refer to the matrix column describing the father of a given node. The root of a tree is indicated by a "null pointer" designated as "-". LEFTMOST SON POINTER.

For nonterminal nodes, the LEFTMOST SON POINTER comprises pointers which re...