Access Restriction

Author Samet, Hanan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Binary tree deletion ♦ Searching ♦ Binary search trees ♦ Associative searching ♦ Information retrieval ♦ Geographic databases ♦ Quad trees ♦ Sorting
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.
Description Affiliation: Univ. of Maryland, College Point (Samet, Hanan)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 23
Issue Number 12
Page Count 8
Starting Page 703
Ending Page 710

Open content in new tab

   Open content in new tab
Source: ACM Digital Library