Patent ID: 8762362

Claim:
A method for updating a data structure, comprising: providing a data structure, wherein the data structure comprises a hierarchically arranged set of nodes and branches, and each node has two or less branches; retrieving a first data entry in the data structure via a first node in response to a first data access request; modifying the data structure to generate a first intermediate data structure that keeps the first node and creates a duplicate of the first node, wherein the first intermediate data structure comprises the first node and the duplicate of the first node; retrieving a second data entry in the data structure via the duplicate of the first node in response to a second data access request; retrieving a third data entry in the data structure via a second node in response to a third data access request; and modifying the first intermediate data structure to generate a second intermediate data structure that creates a duplicate of the second node and removes the first node by replacing the first node with the duplicate of the second node.