Patent ID: 7069272

Claim:
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.