NDLI: Deletion in two-dimensional quad trees

Please wait, while we are loading the content...

Deletion in two-dimensional quad trees

Content Provider	ACM Digital Library
Author	Samet, Hanan
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.
Starting Page	703
Ending Page	710
Page Count	8
File Format	PDF
ISSN	00010782 15577317
DOI	10.1145/359038.359043
Journal	Communications of the ACM (CACM)
Volume Number	23
Issue Number	12
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Binary tree deletion Searching Binary search trees Associative searching Information retrieval Geographic databases Quad trees Sorting
Content Type	Text
Resource Type	Article
Subject	Computer Science Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multidimensional binary search trees used for associative searching

Median split trees

Parallel Balancing of Binary Search Trees

On Foster's information storage and retrieval using AVL trees

A selective traversal algorithm for binary search trees

A note on optimal doubly-chained trees

Comment on average binary search length

An empirical study of insertion and deletion in binary search trees

A comparison of tree-balancing algorithms

Deletion in two-dimensional quad trees

Similar Documents

Multidimensional binary search trees used for associative searching

Median split trees

Parallel Balancing of Binary Search Trees

On Foster's information storage and retrieval using AVL trees

A selective traversal algorithm for binary search trees

A note on optimal doubly-chained trees

Comment on average binary search length

An empirical study of insertion and deletion in binary search trees

A comparison of tree-balancing algorithms

Deletion in two-dimensional quad trees