next up previous
Next: Insertion and Deletion Up: Data Structures and Algorithms Previous: Bubble


Although in the domain of windowing systems, the amount of rectangle data (i.e. the number of windows) is not high, it is still important to examine the storage requirements and the performance of the operations analytically as it may benefit applications in other domains such as VLSI, CAD, etc., where much more rectangle data is present.

The space requirement of the Elastic Windows tree structure is the total number of H-, G-, and L-Nodes. Since, the existence of H- and L-Nodes are user initiated (i.e. inserted by the user), we need to consider only the effect of G-Nodes as the additional space used by the data structure. In the worst case, binary space partitioning is done, as opposed to a k-ary, and the number of G-Nodes is maximum. A worst-case analysis yields that for n windows, the total number of nodes is 2n-1, still O(n). In the average, the structure is expected to contain partitionings of more than 2.

Note that the primary purpose of the G-Nodes is to skip partitioning (i.e. horizontal or vertical) at a certain level. In this case, the maximum number of additional G-nodes is limited by the depth of the tree structure when at every level a skip is needed which is unlikely to occur at every branch of the tree. Still, the worst-case in this situation is O(n).

Primary operations are insertion, deletion, structure operations (e.g. resize, move and copy hierarchy of rectangles) and proximity queries (e.g. neighbor finding and point query).

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

Web Accessibility