Method and apparatus for deleting nodes in Patricia trees

Details Method and apparatus for deleting nodes in Patricia trees Method and apparatus for deleting nodes in Patricia trees

1997-11-25

2000-01-04

Lintz, Paul R.

Data processing: database and file management or data structures

Database design

Data structure types

707101, 341 51, 341 67, G06F 1730

Patent

active

060120614

ABSTRACT:
Any node of a Patricia tree is deleted by selecting as the replacing node the node immediately prior to the deletion node in the unique path to the deletion node. Once the replacing node is determined in this manner, the deletion node is easily removed by simple pointer adjustments of the affected surrounding nodes. Nodes are deleted in time consistent with node insertion time. It is now practicable to use Patricia trees in dynamic situations in which nodes are created and deleted frequently.

REFERENCES:
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5058144 (1991-10-01), Fiala et al.
"Algorithms in C", By: Robert Sedgewick, Addison-Wesley Publishing Company, Reading, Mass., 1990. pp. 245-258.
"The Art of Computer Programming", By: Donald E. Knuth, Stanford University, Addison-Wesley Publishing Company, Reading, Mass., 1973. pp. 489-500.
Fiala et al., "Data Compression With Finite Windows (Several Methods For Adaptive, Invertible Data Compression)", Communications of the ACM, vol. 32, No. 4, Apr., 1989, pp. 490-505.
Jiang, J, Implementing the Patricia Data Structure for Compression Algorithms with Finite Size Dictionaries, International Conference on Data Transmission-Advances in Modern and ISDN Technology and Applications9Conf. Publ. No. 356) Sep. 23-25, 1992.
Bays, J. C., The Complete Patricia, (Dissertation) The University of Okholoma, Norman Ok, Jan. 1974, UMI Order No. 75-6498.

Affiliated with

Also associated with

Rating

Method and apparatus for deleting nodes in Patricia trees does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for deleting nodes in Patricia trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for deleting nodes in Patricia trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1080484