US 7,069,272 B2Granted

System and method for implementing dynamic set operations on data stored in a sorted array

AssigneeBlackRock Financial Management, Inc.

InventorKirk Snyder

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method are disclosed for implementing dynamic set operations on data stored in a sorted array using a hybrid red-black binary search tree as a data structure. More particularly, the subject invention facilitates the implementation of a binary search to access data items stored in a sorted array by position, rather than by key value. This is accomplished by generating a balanced red-black binary search tree for a sorted array of data items wherein the information stored at each node of the tree includes: a key value; a color; a left pointer to indicate the presence of a child to the left of the node; a right pointer to indicate the presence of a child to the right of the node; a count of descendents along a branch to the left of the node; and a count of descendants along a branch to the right of the node.

Claims19

Dependent claims

A method of accessing data items stored in a sorted array by position comprising the steps of:

a) providing a sorted array of data items;
b) generating a balanced binary search tree for the sorted array of data items using a first computer code segment based upon a set of properties that control a structure of the tree, wherein each data item in the sorted array defines a node in the tree, and information is stored at each node including:
i) a key value corresponding to a data item in the sorted array;
ii) a color selected from a group consisting of red and black;
iii) a left pointer to indicate a child to the left of the node;
iv) a right pointer to indicate a child to the right of the node;
v) a count of descendents in all sub-trees in a branch to the left of the node;
and
vi) a count of descendants in all sub-trees in a branch to the right of the node;
and
c) conducting a binary search of the tree using a second computer code segment to access a requested data item at a given position in the sorted array by referring to the right and left descendant counts at each node on a path from a root node of the tree to the node of the requested data item, wherein the following steps are executed recursively starting from the root node until the requested data item is found:
i) deciding a position of a current node by referring to the left and right descendant counts in the left and right branches;
ii) determining which branch of the tree to search by comparing the given position of the requested data item and the position of the current node;
iii) designating a top node in the determined branch as the current node and repeating steps from the deciding step if the requested data item is not found at the top node in the determined branch.

11 more elements

A machine readable program, tangibly embodied on a computer readable medium, containing instructions for controlling a system for accessing data items stored in a sorted array by position comprising:

a) means for generating a balanced binary search tree for a sorted array of data items based upon a set of properties controlling a structure of the tree, wherein each data item in the sorted array defines a node in the tree, and each node contains a plurality of data fields for storing information including:
i) a key value field for storing a key value corresponding to a data item in the sorted array;
ii) a color field for storing a color selected from a group consisting of red and black;
iii) a left pointer field for storing a value indicating existence of a child to the left of the node;
iv) a right pointer field for storing a value indicating existence of a child to the right of the node;
v) a left count field for storing a value equal to a total number of descendents in all sub-trees in a left branch of the node;
and
vi) a right count field for storing a value equal to a total number of descendants in all sub-trees in a right branch of the node;
and
b) means for conducting a binary search of the tree to access a requested data item at a given position in the sorted array by referring to the values stored in the right and left count fields at each node on a path from a root node of the tree to the node of the requested data item, wherein the following steps are executed recursively starting from the root node until the requested data item is found:
i) deciding a position of a current node by referring to the left and right descendant counts in the left and right branches;
ii) determining which branch of the tree to search by comparing the given position of the requested data item and the position of the current node;
iii) designating a top node in the determined branch as the current node and repeating steps from the deciding step if the requested data item is not found at the top node in the determined branch.

10 more elements

Dependencies are inferred from the claim text.