Traversal method of processing tree structure information and apparatus using the same

• US 4,868,743 A
• Filed: 11/23/1987
• Issued: 09/19/1989
• Est. Priority Date: 11/25/1986
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Nishio, Takanori
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/123,777
• Time in Patent Office: 666 Days
• Field of Search: 364/200 MS File, 364/ 900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A traversal method having a memory for storing tree structure data having nodes, each node including an attribute indicating a traversal stage in the tree structure in which an evaluation result of an attribute corresponding to the traversal state of each node of the tree structure data is stepwise arranged according to a depth-first order in the memory in a sequential fashion, the memory including two memories. In this method, the system recognizes as a sub-tree a group of nodes which have a same kind and which are linked with each other, sequentially arranges, during a traversal of a root of the sub-tree, symbols indicating an initiate position of the sub-tree and an end position thereof, and a symbol indicating an intermediate position of the sub-tree in a first memory. The system copies, while searching a series of data thus sequentially arranged for each kind, the initiate symbol, the intermediate symbol, and the end symbol of the sub-tree not belonging to the kind onto second memory. When the initiate symbol of a sub-tree belonging to the kind is detected, an activation of a traversal of the sub-tree is indicated, and when the intermediate and end symbols are detected, a reactivation of a traversal of the sub-tree is indicated. In response to the indication, a traversal of the sub-tree belonging to the kind is executed so as to develop an attribute of the sub-tree in the second memory.

Claims

1. A traversal method in a system including first and second memory means storing data of a tree structure having nodes and processing means for effecting a traversal of the tree structure data comprising:

a first step for achieving the traversal of the tree structure data so as to recognize as a sub-tree a group of nodes which have a same kind and which are linked with each other;

a second step for arranging and for storing in said first memory means, based on the recognition of said first step, a series of data including a location of a node of the tree structure undergone the traversal, a kind of the node, and a symbol indicating a positional relationship between the node and a boundary of an area to which the node belongs;

a third step for searching the sequential data series sequentially arranged in said first memory means by said second step so as to copy onto said second memory means data of sub-trees not belonging to the kind associated with the traversal; and

a fourth step operative when a sub-tree belonging to the pertinent kind is again detected for effecting a traversal on the sub-tree so as to store an attribute of the sub-tree in said second memory means.

2. A traversal method having:

first and second store means for storing tree structure data constituted from nodes, each said node including;

an attribute indicating a traversal stage in the tree structure, and

a kind restricting an evaluation order of the attribute for each node in which an evaluation result of an attribute corresponding to the traversal stage of each node of the tree structure data is stepwise arranged according to a depth-first order in said store means in a sequential fashion comprising;

a first step for recognizing as a sub-tree a group of nodes which have a same kind and which are linked with each other,

said first step, during a traversal of a root of the sub-tree, sequentially arranging symbols indicating an initiate position of the sub-tree and an end position thereof in the preorder and in the postorder,

said first step sequentially arranging a symbol indicating an intermediate position of the sub-tree in said first store means when control returns from a traversal of children with kinds different from the kind in each leaf of the sub-tree;

a second step, while searching a series of data sequentially arranged for each said kind by said first step, for copying the initiate symbol, the intermediate symbol, and the end symbol of the sub-tree not belonging to the kind onto said second store means,

said second step, when the initiate symbol of a sub-tree belonging to the kind is detected, indicating an activation of a traversal of said sub-tree,

said second step, when the intermediate and end symbols are detected, indicating a reactivation of a traversal of said sub-tree; and

a third step responsive to an indication of said second step for effecting a traversal of the sub-tree belonging to the kind so as to develop an attribute of the sub-tree in said second store means.

3. A tree traversal apparatus having:

accumulating means for accumulating tree structure data constituted from nodes, each said node including;

an attribute indicating a traversal stage in the tree structure, and

a kind restricting an evaluation order of the attribute for each node in which an evaluation result of an attribute corresponding to the traversal stage of each node of the tree structure data is stepwise arranged according to a depth-first order in said store means in a sequential fashion comprising;

means for accumulating as an original sequential data a series of initial sequential data constituted with said node information of the node accumulated in said tree structure accumulate means;

means for receiving an initial initiate signal initiating the tree traversal apparatus so as to effect a tree traversal and for writing the initial sequential data series in said original sequential data accumulate means while reading information possessed by the node from the tree structure data accumulated in said accumulate means;

means for accumulating as an object sequential data series an attribute of each said node of a kind as a current evaluation object and sequential data with a kind other than the kind of the evaluation object;

means for recognizing as a sub-tree a group of nodes which have a same kind and which are linked with each other

means for accumulating and for controlling location information of data indicating a state of the traversal processing of the sub-tree;

means for reading sequential data from said original sequential data accumulate means so as to write the sequential data in said object sequential data accumulate means and for controlling the sub-tree traversal processing while referencing and updating data indicating a state of the traversal processing of the sub-tree stored in said sub-tree traversal control information accumulate means so as to search the sequential data; and

means for reading from said tree structure accumulate means, based on a root of a sub-tree specified by said sequential data search means, information of nodes which are linked with each other to configure said sub-tree so as to write an attribute of each said node in said object sequential data accumulate means.

4. A traversal method in a system having:

first and second store means for storing tree structure data constituted from nodes, each said node including;

an attribute indicating a traversal stage in the tree structure, and

a kind restricting an evaluation order of the attribute for each node in which an evaluation result of an attribute corresponding to the traversal stage of each node of the tree structure data is stepwise arranged according to a depth-first order in said store means in a sequential fashion comprising;

a first step for recognizing as a sub-tree a group of nodes which have a same kind and which are linked with each other,

said first step recognizing as a root a node generating information to be an object of a propagation, and

recognizing as a propagation enable area in which said propagation information can be propagated an area excepting the node which is at the highest level among the nodes in which the propagation information is not referenced,

said first step retaining an attribute value vector keeping said entire propagation information in a node of a propagation source of said propagation information so as to store a value indicated by said attribute value vector in the node of the propagation source, and

sequentially arranging in the preorder and in the postorder, during a traversal of a root of the sub-tree, symbols indicating an initiate position and an end position of the sub-tree keeping a location of the attribute value vector of he propagation source of an ancestor nearest to the root,

said first step sequentially arranging a symbol indicating an intermediate position of the sub-tree in one of said first and second store means, at a point when control returns from a traversal of a child with a kind different from the kind in each leaf of the sub-tree;

a second step for searching a series of data sequentially arranged for each said kind by said first step so as to copy the initiate symbol, the intermediate symbol, and the end symbol of the sub-tree not belonging to the kind onto said second store means,

said second step, when the initiate symbol of a sub-tree belonging to the kind is detected, indicating an initiation of a traversal of said sub-tree,

said second step, when the intermediate symbol and the end symbol are detected, indicating a reactivation of the traversal of said sub-tree; and

a third step responsive to an indication of said second step for effecting a traversal of the sub-tree belonging to the kind so as to develop an attribute of the sub-tree in the other one of said two store means.

5. A traversal apparatus in a system including first and second memory means storing data of a tree structure having nodes and memory means for effecting a traversal of the tree structure data comprising:

first means for achieving a traversal of the tree structure data so as to recognize as a sub-tree a group of nodes which have a same kind and which are linked with each other;

second means for arranging and for storing in said first memory means, based on the recognition of said first means, a series of data including a location of a node of the tree structure undergone the traversal, a kind of the node, and a symbol indicating a positional relationship between the node and a boundary of an area to which the node belongs;

third means for searching the sequential data series sequentially arranged in said first memory means by said second means for copying onto said second memory means data of sub-trees not belonging to the kind associated with the traversal; and

fourth means operative when a sub-tree belonging to the pertinent kind is again detected, for effecting a traversal on the sub-tree so as to store an attribute of the sub-tree in said second memory means.