Binary tree structure with end of path flags stored with path arc's
OwnerLuther J. Woodruminventor
Life of this patent
Estimating the term…
Abstract
Arrangement of fields in binary tree nodes provides a minimal storage encoding storing fixed and variable length keys in factored form in a multilevel tree. A locating method, and apparatus embodying that method, directed by an argument key, which may or may not be stored in the tree, traces a path following arcs upward or downward between nodes in said binary tree, starting from the top node or any other node, until it finds either the argument key or the delta arc where said argument key would be inserted into said tree. The novel binary tree encoding also provides for path tracing starting at a data backpointer field, which allows accessing of neighboring data entries in collating sequence order.
Claims5
A novel arrangement of flag bits signalling whether successors of an inner node, which itself is not at the end of a path, are at the end of a path, wherein said inner node has two successors, each of which may be an end of path node, independently of each other,
- two flag bits recording the end of path status of said two successors of said inner node,
- said flag bits arranged in a novel arrangement by being stored in the low order two bits of one of the inner arc fields of the predecessor of said inner node,
- said arc field of said predecessor node being a left inner arc field if said inner node is a left successor of said predecessor node, or said arc field of said predecessor node being a right inner arc field if said inner node is a right successor of said said predecessor node,
- said novel arrangement of flag bits thereby storing said end of path status of said successors of said inner node stored totally in said inner arc field of said predecessor of said inner node without any end of path information being stored in an arc of said inner node that is an end of path arc,
- thereby providing a complete word for storing end of path arcs containing no end of path flag bits.
Dependencies are inferred from the claim text.