Array Generation Method And Array Generation Program

• US 20090106289A1
• Filed: 09/28/2005
• Published: 04/23/2009
• Est. Priority Date: 10/01/2004
• Status: Abandoned Application

• Current Assignee: Turbo Data Laboratories, Inc.
• Original Assignee: Turbo Data Laboratories, Inc.
• Inventors: Furusho, Shinji
• Application Number:
  US11/576,481
• Publication Number:
  US 20090106289A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A tree-type data structure representation method that can effectively trace relationships among data in a tree-type data structure, such as parent-child, ancestors, descendents, siblings, and generations, is provided. In a memory, data having a tree-type data structure in which unique node identifiers are assigned to nodes and a parent-child relationship between the nodes is represented by a C-P array including pairs, each pair being formed of a node identifier assigned to each of non-root nodes, which are nodes other than a root node, and a node identifier of a parent node with which each of the non-root nodes is associated is stored. In the memory, a vertex node list storing, in order to represent at least one node group, each including a specific node and a descendent node of the specific node, node identifiers of the specific nodes, which serve as vertex nodes, is also stored. A system 10 moves each of the vertex nodes to a child node, a parent node, or a node in the same generation as the vertex node (an older sibling node or a younger sibling node) by referring to the C-P array, and generates a new vertex node list.

Claims

1-18. -18. (canceled)

19. An array generation method, in a computer including data having a tree-type data structure in which unique node identifiers are assigned to nodes and a parent-child relationship between the nodes is represented by a first array including a node identifier of a parent node with which each of non-root nodes, which are nodes other than a root node, is associated, the array generation method comprising:

a step of providing a second array, in order to represent at least one node group, each including a specific node and a descendent node of the specific node, the second array storing a node identifier of at least one specific node, which serves as a vertex node; and

a step of generating, by referring to the first array, a third array storing a node identifier of a new vertex node, which is a moved version of each of the vertex nodes whose node identifiers are stored in the second array after moving the vertex node to a node having a certain relationship with the vertex node.

20. The array generation method according to claim 19, wherein in the step of generating the third array, the node having a predetermined relationship with each of the vertex nodes is one of

a) a child node directly connected to the vertex node by an arc which is extended from the vertex node to the child node,

b) a parent node directly connected to the vertex node by an arc which is extended from the parent node to the vertex node,

c) an older sibling node which is in the same generation as the vertex node, an arc from the parent node of the vertex node being connected to the older sibling node before another arc from the parent node of the vertex node is connected to the vertex node, and

d) a younger sibling node which is in the same generation as the vertex node, an arc from the parent node of the vertex node being connected to the younger sibling node after another arc from the parent node of the vertex node is connected to the vertex node.

21. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a storage location at which the node identifier of the vertex node is stored, and

a step of storing a node identifier corresponding to the storage location in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to a child node.

22. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a node identifier stored at a location corresponding to the node identifier of the vertex node, and

a step of storing the node identifier stored at the corresponding location in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to a parent node.

23. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a first node identifier stored at a location corresponding to the node identifier of the vertex node,

a step of specifying, in the first array, a second node identifier stored at a storage location having a value smaller than a value of the location corresponding to the node identifier of the vertex node by one, and

a step of storing, when the first node identifier and the second node identifier coincide with each other, a node identifier corresponding to the storage location at which the second node identifier is stored in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to an older sibling node.

24. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a first node identifier stored at a location corresponding to the node identifier of the vertex node,

a step of specifying, in the first array, a third node identifier stored at a storage location having a value greater than a value of the location corresponding to the node identifier of the vertex node by one, and

a step of storing, when the first node identifier and the third node identifier coincide with each other, a node identifier corresponding to the storage location at which the third node identifier is stored in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to a younger sibling node.

25. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a storage location at which the node identifier of the vertex node is stored, and

a step of storing a node identifier corresponding to the storage location in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to a child node.

26. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a node identifier stored at a location corresponding to the node identifier of the vertex node, and

a step of storing the node identifier stored at the corresponding location in the third array as a node identifier of a moved version of the vertex node;

each of the vertex nodes is moved to a parent node.

27. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a first node identifier stored at a storage location at which the node identifier of the vertex node is stored,

a step of searching, in the first array, a fourth node identifier stored at storage locations having values smaller than a value of the storage location at which the node identifier of the vertex node is stored, the fourth identifier being equal to the first identifier,

a step of specifying a storage location having a largest value among the storage locations of the fourth node identifier, and

a step of storing a node identifier corresponding to the storage location having the largest value in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to an older sibling node.

28. The method according to claim 20, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes;

the step of generating the third array includes

a step of specifying, in the first array, a first node identifier stored at a storage location at which the node identifier of the vertex node is stored,

a step of searching, in the first array, a fifth node identifier stored at storage locations having values greater than a value of the storage location at which the node identifier of the vertex node is stored, the fifth node identifier being equal to the first node identifier,

a step of specifying a storage location having a smallest value among the storage locations of the fifth node identifier, and

a step of storing a node identifier corresponding to the storage location having the largest value in the third array as a node identifier of a moved version of the vertex node; and

each of the vertex nodes is moved to be a younger sibling node.

29. An array generation program readable by a computer which includes data having a tree-type data structure, in which unique node identifiers are assigned to nodes and a parent-child relationship between the nodes is represented by a first array including a node identifier of a parent node with which each of non-root nodes, which are nodes other than a root node, is associated, the array generation program allowing the computer to execute:

a step of providing a second array, in order to represent at least one node group, each including a specific node and a descendent node of the specific node, the second array storing a node identifier of at least one specific node, which serves as a vertex node; and

a step of generating, by referring to the first array, a third array storing a node identifier of a new vertex node, which is a moved version of each of the vertex nodes whose node identifiers are stored in the second array after moving the vertex node to a node having a certain relationship with the vertex node.

30. The program according to claim 29, wherein in the step of generating the third array, the node having a predetermined relationship with each of the vertex nodes is one of

a) a child node directly connected to the vertex node by an arc which is extended from the vertex node to the child node,

b) a parent node directly connected to the vertex node by an arc which is extended from the parent node to the vertex node,

c) an older sibling node which is in the same generation as the vertex node, an arc from the parent node of the vertex node being connected to the older sibling node before another arc from the parent node of the vertex node is connected to the vertex node, and

d) a younger sibling node which is in the same generation as the vertex node, an arc from the parent node of the vertex node being connected to the younger sibling node after another arc from the parent node of the vertex node is connected to the vertex node.

31. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a child node, the program allows the computer to execute

a step of specifying, in the first array, a storage location at which the node identifier of the vertex node is stored, and

a step of storing a node identifier corresponding to the storage location in the third array as a node identifier of a moved version of the vertex node.

32. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a parent node, the program allows the computer to execute

a step of specifying, in the first array, a node identifier stored at a location corresponding to the node identifier of the vertex node, and

a step of storing the node identifier stored at the corresponding location in the third array as a node identifier of a moved version of the vertex node.

33. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to an older sibling node, the program allows the computer to execute

a step of specifying, in the first array, a first node identifier stored at a location corresponding to the node identifier of the vertex node,

a step of specifying, in the first array, a second node identifier stored at a storage location having a value smaller than a value of the location corresponding to the node identifier of the vertex node by one, and

a step of storing, when the first node identifier and the second node identifier coincide with each other, a node identifier corresponding to the storage location at which the second node identifier is stored in the third array as a node identifier of a moved version of the vertex node.

34. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to nodes in the same generation as a certain node rather than child nodes of that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a younger sibling node, the program allows the computer to execute

a step of specifying, in the first array, a first node identifier stored at a location corresponding to the node identifier of the vertex node,

a step of specifying, in the first array, a third node identifier stored at a storage location having a value greater than a value of the location corresponding to the node identifier of the vertex node by one, and

a step of storing, when the first node identifier and the third node identifier coincide with each other, a node identifier corresponding to the storage location at which the third node identifier is stored in the third array as a node identifier of a moved version of the vertex node.

35. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a child node, the program allows the computer to execute

a step of specifying, in the first array, a storage location at which the node identifier of the vertex node is stored, and

a step of storing a node identifier corresponding to the storage location in the third array as a node identifier of a moved version of the vertex node.

36. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a parent node, the program allows the computer to execute

a step of specifying, in the first array, a node identifier stored at a location corresponding to the node identifier of the vertex node, and

a step of storing the node identifier stored at the corresponding location in the third array as a node identifier of a moved version of the vertex node.

37. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to an older sibling node, the program allows the computer to execute

a step of specifying, in the first array, a first node identifier stored at a storage location at which the node identifier of the vertex node is stored,

a step of searching, in the first array, a fourth node identifier stored at storage locations having values smaller than a value of the storage location at which the node identifier of the vertex node is stored, the fourth identifier being equal to the first identifier,

a step of specifying a storage location having a largest value among the storage locations of the fourth node identifier, and

a step of storing a node identifier corresponding to the storage location having the largest value in the third array as a node identifier of a moved version of the vertex node.

38. The program according to claim 30, wherein:

unique serial integers are assigned to the nodes including the root node by giving priority to child nodes of a certain node rather than nodes in the same generation as that certain node;

the first array is formed by arranging the integers assigned to the parent nodes of the corresponding non-root nodes, which are nodes other than the root node, according to an order in which the integers are assigned to the non-root nodes; and

in the step of generating the third array for moving each of the vertex nodes to a younger sibling node, the program allows the computer to execute

a step of specifying, in the first array, a first node identifier stored at a storage location at which the node identifier of the vertex node is stored,

a step of searching, in the first array, a fifth node identifier stored at storage locations having values greater than a value of the storage location at which the node identifier of the vertex node is stored, the fifth node identifier being equal to the first node identifier,

a step of specifying a storage location having a smallest value among the storage locations of the fifth node identifier, and

a step of storing a node identifier corresponding to the storage location having the largest value in the third array as a node identifier of a moved version of the vertex node.