Browse Prior Art Database

A Structure for Matching Records using a Sorted Binary Tree

IP.com Disclosure Number: IPCOM000104243D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Related People

Bezviner, DE: AUTHOR

Abstract

Disclosed is a data structure and technique for matching records using a sorted binary tree.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 79% of the total text.

A Structure for Matching Records using a Sorted Binary Tree

      Disclosed is a data structure and technique for matching
records using a sorted binary tree.

      Records are often sorted using a binary tree.  Duplicate
records or keys may exist.  It may then be desirable to locate all
the records within the tree that have a particular key.  Disclosed is
a method for minimizing key comparisons when using a sorted binary
tree as a base.

      Typically, the first matching record can be found by comparing
the key to the record in the root, and then branching left or right
accordingly.  This is continued until the left-most, ie smallest or
first, matching record is found.  Once the first matching record is
found, the tree is parsed to the next node and another compare done
to determine if the record in that node matches the given key.

      If the tree is searched a second time for the same key,
compares will still be required to find the first matching record.
However, the technique described herein avoids any further key
comparisons.

      The structure required is a separate flag, one per node.  This
flag would have three values:  Equal, Not Equal, Unknown.

      The value "Equal" means that the key in this node is equal to
the key in the next node.  "Unequal" means that the key in this node
is not equal to the key in the next node.  "Unknown" means that it is
not known if the key in this node is equal to the key in the next
node.

  ...