Browse Prior Art Database

Bulk Deletion in Binary Trees

IP.com Disclosure Number: IPCOM000122925D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Related People

Bournas, R: AUTHOR

Abstract

Disclosed is an efficient method to delete elements from a Practical Algorithm to Retrieve Information Coded in Alphanumeric (PATRICIA) tree. This method is based on deleting bulk of elements all at once. The deletion of a tree element is not done right away but rather is deferred for a later time when a specified number of elements have been accumulated. At that time, the entire tree without the elements to be deleted is reconstructed. By choosing the right number of elements to defer for deletion, optimal deletion performance is achieved.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 70% of the total text.

Bulk Deletion in Binary Trees

      Disclosed is an efficient method to delete elements from a
Practical Algorithm to Retrieve Information Coded in Alphanumeric
(PATRICIA) tree.  This method is based on deleting bulk of elements
all at once.  The deletion of a tree element is not done right away
but rather is deferred for a later time when a specified number of
elements have been accumulated.  At that time, the entire tree
without the elements to be deleted is reconstructed.  By choosing the
right number of elements to defer for deletion, optimal deletion
performance is achieved.

The bulk deletion algorithm is described as follows.  It depends on
the following variables:
  1.  a deferred deletion bit for each element in the tree
       (a value of 1 indicating the element is to be deleted),
  2.  a counter of the total number of elements in the tree,
  3.  a threshold that is a maximum number of elements for
       which to defer deletion, and
  4.  a counter of the number of elements deferred for deletion

The threshold is predefined at tree initialization time as a
percentage of the total number of elements in the tree.  Upon a
deletion request, the deferred deletion counter is incremented by
one, the deferred deletion bit is set and the counter is compared
against the threshold.  If it is smaller, the element is not deleted,
otherwise the entire tree less all elements deferred for deletion is
reconstructed.  The search algorithm is modified...