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 2*k*-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*).

Sun Sep 13 18:34:46 EDT 1998