US5530957A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Storing trees in navigable form
Assignee: AT&T Inc
•
Filing: 1992-08-07
•
Granted: 1996-06-25
•
Expires: 2012-08-07
Abstract
Abstract A compact representation of a tree data structure and techniques for navigating the compact representation. The compact representation is a list. Each element of the list represents a node of the tree and the list is organized according to a preorder traversal of the tree. Each list element contains only the index of a data dictionary entry for the kind of item represented by the node corresponding to the list element. The navigation techniques permit the location of the list element for the sibling of the node corresponding to the given list element, the location of the list element for that node's parent, and in the case of a parent node, the location of the list element for any child of the parent. The navigation techniques work by finding the list elements for subtrees. The subtrees are found by techniques based on the fact that the number of children of all of the nodes in a subtree minus the number of nodes in the subtree always equals -1. The number of children of a given node is determined by a valence function which takes the index of the data dictionary entry as its argument.
Inventors
- 👤 Andrew R. Koenig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 09:52
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; G06F16/904
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
149 words
Apparatus for storing a tree data structure in a memory system, the tree structure being made up of one or more nodes, each of which represents one of a plurality of items, the apparatus comprising: a data dictionary in the memory system which includes one data dictionary entry for each of the items; valence function means for determining the number of children which a node representing an item has; and a list in the memory system which has one or more list entries, the list entries being ordered according to a traversal of the tree structure and each list entry representing a single one of the nodes and including a value which is used both to locate the entry in the data dictionary for the item represented by the node and with the valence function means to determine the number of children of the node represented by the entry.
Claim 2
Dependent Claim
149 words
Apparatus for storing a tree data structure in a memory system, the tree structure being made up of one or more nodes, each of which represents one of a plurality of items, the apparatus comprising: a data dictionary in the memory system which includes one data dictionary entry for each of the items; valence function means for determining the number of children which a node representing an item has; and a list in the memory system which has one or more list entries, the list entries being ordered according to a traversal of the tree structure and each list entry representing a single one of the nodes and including a value which is used both to locate the entry in the data dictionary for the item represented by the node and with the valence function means to determine the number of children of the node represented by the entry.
Claim 3
Dependent Claim
28 words
The apparatus set forth in claim 1 wherein: the list entries are stored in a sequence of memory locations which corresponds to the sequence of the list entries.
Claim 4
Dependent Claim
15 words
The apparatus set forth in claim 2 wherein: each list entry includes only the value.
Claim 5
Dependent Claim
23 words
The apparatus set forth in claim 1 wherein: the sequence of the list entries is that of a preorder traversal of the tree.
Claim 6
Independent Claim
36 words
The apparatus set forth in any of claims 1, 2, 3, or 4, wherein: the value has substantially fewer bits than the number of bits in a pointer which specifies an address in the memory system.
Claim 7
Independent Claim
63 words
The apparatus set forth in any of claims 1, 2, 3, or 4 further comprising: navigation means for performing tree navigation operations on the list, the navigation means including means for detecting any subtrees of the tree data structure in a sequence of the list entries and the navigation means employing the detected subtrees to perform the tree navigation operations on the list.
Claim 8
Dependent Claim
41 words
The apparatus set forth in claim 6 wherein: the navigation means employs the detected subtrees to locate the parent of a given node; locate a given child of a given parent node; and locate a given sibling of a given node.
Claim 9
Dependent Claim
61 words
The apparatus set forth in claim 6 wherein: the means for detecting any subtrees further includes means for determining the number of children of a node represented by a list entry from the value included in the list entry; and the means for detecting any subtrees employs the number of children returned by the means for determining to detect the subtrees.
Claim 10
Independent Claim
134 words
A method for detecting a subtree of a tree in a sequential representation of the nodes of the tree, the sequential representation including an element for each node which includes a value from which a valence value can be determined, the valence value being the number of children belonging to the node corresponding to the element, and the sequence of the elements being that of a traversal of the nodes of the tree, the method comprising the steps of: for a given subsequence of the elements, determining the number of elements in the subsequence; determining the sum of the valence values for the elements in the subsequence; and subtracting the sum of the valence values from the number of elements, the subsequence corresponding to a subtree when the result of the subtraction is -1.
Claim 11
Independent Claim
134 words
A method for detecting a subtree of a tree in a sequential representation of the nodes of the tree, the sequential representation including an element for each node which includes a value from which a valence value can be determined, the valence value being the number of children belonging to the node corresponding to the element, and the sequence of the elements being that of a traversal of the nodes of the tree, the method comprising the steps of: for a given subsequence of the elements, determining the number of elements in the subsequence; determining the sum of the valence values for the elements in the subsequence; and subtracting the sum of the valence values from the number of elements, the subsequence corresponding to a subtree when the result of the subtraction is -1.
Claim 12
Independent Claim
95 words
A method of performing tree navigation operations on a list representing a tree data structure, the list including a list entry for each node of the tree data structure and being ordered according to a traversal of the tree data structure, the method comprising the steps of: employing a value in the list entry to determine the number of children of the node represented by the list entry employing the number of children to detect subtrees of the tree data structure; and employing the detected subtrees to perform the tree navigation operations on the list.
Claim 13
Independent Claim
95 words
A method of performing tree navigation operations on a list representing a tree data structure, the list including a list entry for each node of the tree data structure and being ordered according to a traversal of the tree data structure, the method comprising the steps of: employing a value in the list entry to determine the number of children of the node represented by the list entry employing the number of children to detect subtrees of the tree data structure; and employing the detected subtrees to perform the tree navigation operations on the list.
Claim 14
Dependent Claim
153 words
The method set forth in claim 10 wherein: the step of employing the number of children to detect the subtrees comprises the steps of: beginning with a starting list entry which is either the first list entry in the sequence or the first list entry following the list entries for a detected subtree, performing steps for each list entry following the starting list entry including for a current list entry, determining the number of list entries since the starting list entry; determining the sum of the number of children of the nodes represented by the starting list entry and the following list entries through the current list entry; and subtracting the sum of the number of children from the number of list entries since the starting list entry, the list entries from the starting list entry to the current list entry corresponding to a subtree when the result of the subtraction is -1.
References Cited (Backward Citations)
US4945475A
Cited
US4868743A
Cited
US5153591A
Cited
US5307486A
Cited
US5253325A
Cited
US5276874A
Cited
US5202986A
Cited
US5257365A
Cited
US5295261A
Cited
US5303367A
Cited
US5263160A
Cited
US5297284A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-25 | 1999-12-25 | 2000-06-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-25 | 2003-12-25 | 2004-06-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-25 | 2007-12-25 | 2008-06-25 | $7700.00 | Window Closed / Lapsed |