 |
|
|
|
|
|
 Title: |
US5530957:
Storing trees in navigable form
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Koenig, Andrew R.; Gillette, NJ
|
| Assignee: |
AT&T Corp., Murray Hill, NJ
other patents from AT&T CORP. (706518) (approx. 16,328)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1996-06-25
/ 1992-08-07
|
| Application Number: |
US1992000927087
|
| IPC Code: |
Advanced:
G06F 9/45;
G06F 12/00;
G06F 17/30;
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30Z1T;
|
| U.S. Class: |
Current:
001/001;
707/999.1;
707/E17.012;
Original:
395/600;
364/251.6;
364/960.5;
364/DIG.1;
395/700;
|
| Field of Search: |
395/600,200,700,400,425,159,160,2
364/DIG. 1,251.6,960.5
341/051,65,67,79,87
|
| Priority Number: |
| 1992-08-07 |
US1992000927087 |
|
| 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.
|
| Attorney, Agent or Firm: |
Nelson, Gordon E. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Alam, Hosain T.
|
| Maintenance Status: |
E3 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
DE ES FR GB IT
|
| Family: |
Show 8 known family members
|
First Claim:
Show all 11 claims |
What is claimed is:
1. 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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 35 U.S. patent(s) that reference this one
|
