next up previous
Next: Proximity Queries Up: Performance Previous: Insertion and Deletion

Structure Operations

The move operation first gets a pointer to the window given the id, which costs O(1). Then, a call to the CloseWindow function is made to remove the node and all its children from the tree, which costs O(k+a+d) as calculated earlier. In the last phase of the move operation, the node is relocated to its new location which may require insertion of either 0, 1, or 3 G-Nodes and propagation of the changes to its children O(a). Thus, the total cost of the move operation is O(k+2a+d). The cost of the copy operation is equal to the cost of the move operation with the cost of the propagate operation in the CloseWindow reduced, O(k+a+d).

The resize operation similarly first gets a pointer to the window given the id. Then, it climbs up the tree hierarchy skipping G-Nodes with only a single child, which also has a constant cost since at most only two such G-Nodes can exist. Next, the boundary node is found, which costs on the worst case O(d/2), as found in the next section. Lastly, coordinates are updated and propagated to children nodes, similar to move operation. Thus, the total cost is O(d/2+k).

Eser Kandogan
Sun Sep 13 18:34:46 EDT 1998

Web Accessibility