next up previous
Next: Structure Operations Up: Performance Previous: Performance

Insertion and Deletion

In order to insert a new rectangle (OpenWindow), the node where it is to be inserted has to be found in the tree, given the id. Since an additional hash data structure (WindowCollection) is kept for this purpose, this operation has constant cost, assuming a good hash function. Once the parent is found, the insertion may require additional G-Nodes to be inserted to preserve alternating order of partitions. In all the cases, as described earlier, the number of G-Nodes inserted are either 0 (Case 1), 1 (Case 2 and 4) or 2 (Case 3). Thus, the cost is also constant. The last operation to be performed in insertion is to propagate the changes to lower level rectangles. This operation is performed on all children. Assume the total number is k, at best the cost is O(k). However, taking into account the existence of G-Nodes, it can be as high as 2k-1, still O(k). Thus, the overall cost of insertion is O(k).

Similarly, in deletion first a pointer to the tree structure is needed given the id of the node to be deleted. Using the has data structure (WindowCollection) its costs is constant. The climb phase of the delete operation (CloseWindow) has also constant cost, as at most two levels are climbed, due to the clean phase performed at the end of the delete operation. Once the node is deleted, all its children are also to be deleted, which costs O(k), assuming their total number is k. The propagation of the changes is similarly linearly dependent on the number of nodes (a) affected. The cleanup phase climbs up the tree structure to clean any two consecutive G-nodes. The cost of this phase can be as high as the depth of the node (d). Thus, the overall cost of deletion is O(k+a+d).


next up previous
Next: Structure Operations Up: Performance Previous: Performance

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

Web Accessibility