Storing trees in navigable form

Details Storing trees in navigable form Storing trees in navigable form

1992-08-07

1996-06-25

Black, Thomas G.

Boots, shoes, and leggings

3642516, 3649605, 364DIG1, 395700, G06F 1730

Patent

active

055309577

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.

REFERENCES:
patent: 4868743 (1989-09-01), Nishio
patent: 4945475 (1990-07-01), Bruffey et al.
patent: 5153591 (1992-10-01), Clark
patent: 5202986 (1993-04-01), Nickel
patent: 5253325 (1993-10-01), Clark
patent: 5257365 (1993-10-01), Powers et al.
patent: 5263160 (1993-11-01), Porter et al.
patent: 5276874 (1994-01-01), Thomson
patent: 5295261 (1990-07-01), Simonetti
patent: 5297284 (1991-04-01), Jones et al.
patent: 5303367 (1990-12-01), Leenstra, Sr. et al.
patent: 5307486 (1994-04-01), Nakamigawa
Practical Dictionary Management for Hardware Data Compression, Bunton et al., Communications of the ACM, V35, n1, p. 95(11), Jan., 1992.

Affiliated with

Also associated with

Rating

Storing trees in navigable form does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Storing trees in navigable form, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storing trees in navigable form will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2198727