Patent ID: 7499945

Claim:
A method of accessing data items stored in a sorted array by position comprising a processor to perform the steps of: a) providing a sorted array of data items; b) generating a balanced search tree for the sorted array of data items using a first computer code segment based upon a set of properties that control the 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 first pointer to indicate a first child of the node; iii) a second pointer to indicate a second child of the node; iv) a first count of descendents in all sub-trees in a branch including the first child; and v) a second count of descendants in all sub-trees in a branch including the second child; and c) conducting a 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 first and second 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 first and second descendant counts in the first and second 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; and 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.