Deletion in two-dimensional quad trees

ABSTRACT

An algorithm for deletion in two-dimensional quad trees that handles the problem in a manner analogous to deletion in binary search trees is presented. The algorithm is compared with a proposed method for deletion which reinserts all of the nodes in the subtrees of the deleted node. The objective of the new algorithm is to reduce the number of nodes that need to be reinserted. Analysis for complete quad trees shows that the number of nodes requiring reinsertion is reduced to as low as 2/9 of that required by the old algorithm. Simulation tests verify this result. Reduction of the number of insertions has a similar effect on the number of comparison operations. In addition, the total path length (and balance) of the resulting tree is observed to remain constant or increase slightly when the new algorithm for deletion is used, whereas use of the old algorithm results in a significant increase in the total path length for large trees.

REFERENCES

• 1: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 2: Bentley, J.L., and Stanat, D.F. Analysis of range searches in quad trees. Inform. Proc. Lett. (July 1975) 170-173.
• 3: Finkel, R.A., and Bentley, J.L. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4 (1974), 1-9.
• 4: Gary Don Knott, Deletion in binary storage trees., 1975
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Lee, D.T., and Wong, C.K. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica, 9 (1977), 23-29.
• 7: John Charles Linn, General methods for parallel-searching., 1973
• 8: Lueker, G.S. A data structure for orthogonal range queries. Proc. 19th Ann. Symp. Foundations Comptr. Sci., Ann Arbor, Mich., 1978, pp. 28-34.

INDEX TERMS

Keywords:
associative searching, binary search trees, binary tree deletion, geographic databases, information retrieval, quad trees, searching, sorting