Patent ID: 7539694
Filing Date: 2009-05-26
Classification: G06F,Y10S

Abstract:
1. An apparatus comprising: a memory comprising a plurality of locations, each location to store a node for a binary tree comprising a plurality of the nodes; a classifier to search the binary tree, wherein the classifier requires one node processing interval to process one of the nodes; and a processor to modify the binary tree while the classifier searches the binary tree, wherein the processor (a) identifies a first one of the nodes about which the binary tree is to be rotated, wherein a second one of the nodes is a descendant of the first one of the nodes and has a first pointer that indicates a third one of the nodes and a second pointer that indicates a fourth one of the nodes, and wherein a side of the second one of the nodes from which the third one of the nodes descends is the same as a side of the first one of the nodes from which the second one of the nodes descends; (b) creates a copy of the second one of the nodes; (c) causes pointers of the copy to indicate the first and third nodes; (d) modifies a pointer that indicates the first one of the nodes to indicate the copy instead; (e) after (d), waiting at least two node processing intervals; (f) after (e), modifies a pointer that indicates the second one of the nodes to indicate the fourth one of the nodes instead; (g) after (f), waits at least one node processing interval; (h) modifies the second pointer to indicate the first one of the nodes instead; and (i) modifies a pointer that indicates the copy to indicate the second one of the nodes instead.