Method and apparatus for deleting nodes in Patricia trees
First Claim
1. A method of deleting a node C in a tree having the properties that there is a unique path to every tree node, each node has a left child node and a right child node and corresponding left and right child pointers, each node is associated with a bit index identifying the bit position in a search key to be examined to determine whether to advance to the left child node or to the right child node as the tree is traversed, the bit indices of successive nodes monotonically decrease for trees of a first type and monotonically increase for trees of a second type as the tree is traversed, except for the last node in any path in which the bit index increases for trees of the first type and decreases for trees of the second type with respect to the bit index of the immediately preceeding node,for trees of the first type, each bit in positions M-1 through i+1 of the search key leading to a node N is equal to the corresponding bit in the search keys that lead to any of its child nodes, where i is a bit index of node N and M is the number of bits in a search key used to traverse the tree,and for trees of the second type, each bit in positions 0 through i-1 of the search key leading to a node is equal to the corresponding bit in the search keys that lead to any of its child nodes, the method comprising the steps oflocating the deletion node C by traversing the tree according to a search key corresponding to the deletion node,identifying a node B immediately preceding node C in the path to node C, andreplacing the node C in the tree with node B.
1 Assignment
0 Petitions
Accused Products
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.
43 Citations
6 Claims
-
1. A method of deleting a node C in a tree having the properties that there is a unique path to every tree node, each node has a left child node and a right child node and corresponding left and right child pointers, each node is associated with a bit index identifying the bit position in a search key to be examined to determine whether to advance to the left child node or to the right child node as the tree is traversed, the bit indices of successive nodes monotonically decrease for trees of a first type and monotonically increase for trees of a second type as the tree is traversed, except for the last node in any path in which the bit index increases for trees of the first type and decreases for trees of the second type with respect to the bit index of the immediately preceeding node,
for trees of the first type, each bit in positions M-1 through i+1 of the search key leading to a node N is equal to the corresponding bit in the search keys that lead to any of its child nodes, where i is a bit index of node N and M is the number of bits in a search key used to traverse the tree, and for trees of the second type, each bit in positions 0 through i-1 of the search key leading to a node is equal to the corresponding bit in the search keys that lead to any of its child nodes, the method comprising the steps of locating the deletion node C by traversing the tree according to a search key corresponding to the deletion node, identifying a node B immediately preceding node C in the path to node C, and replacing the node C in the tree with node B.
-
3. Apparatus deleting a node C in a tree having the properties that there is a unique path to every tree node, each node has a left child node and a right child node and corresponding left and right child pointers, each node is associated with a bit index identifying the bit position in a search key to be examined to determine whether to advance to the left child node or to the right child node as the tree is traversed, the bit indices of successive nodes monotonically decrease for trees of a first type and monotonically increase for trees of a second type as the tree is traversed, except for the last node in any path in which the bit index increases for trees of the first type and decreases for trees of the second type with respect to the bit index of the immediately preceeding node,
for trees of the first type, each bit in positions M-1 through i-1 of the search key leading to a node N is equal to the corresponding bit in the search keys that lead to any of its child nodes, where i is a bit index of node N and M is the number of bits in a search key used to traverse the tree, and for trees of the second type, each bit in positions 0 through i+1 of the search key leading to a node is equal to the corresponding bit in the search keys that lead to any of its child nodes, the apparatus comprising means for locating the deletion node C by traversing the tree according to a search key corresponding to the deletion node, means for identifying a node B immediately preceding node C in the path to node C, and means for replacing the node C in the tree with node B.
-
5. A computer program product for deleting a node C in a tree having the properties that there is a unique path to every tree node, each node has a left child node and a right child node and corresponding left and right child pointers, each node is associated with a bit index identifying the bit position in a search key to be examined to determine whether to advance to the left child node or to the right child node as the tree is traversed, the bit indices of successive nodes monotonically decrease for trees of a first type and monotonically increase for trees of a second type as the tree is traversed, except for the last node in any path in which the bit index increases for trees of the first type and decreases for trees of the second type with respect to the bit index of the immediately preceeding node,
for trees of the first type, each bit in positions M-1 through i+1 of the search key leading to a node N is equal to the corresponding bit in the search keys that lead to any of its child nodes, where i is a bit index of node N and M is the number of bits in a search key used to traverse the tree, and for trees of the second type, each bit in positions 0 through i-1 of the search key leading to a node is equal to the corresponding bit in the search keys that lead to any of its child nodes, the computer program product comprising a computer-readable medium having computer-readable program code means embodied in the medium, the computer-readable program code means comprising computer-readable program code means for locating the deletion node C by traversing the tree according to a search key corresponding to the deletion node, computer-readable program code means for identifying a node B immediately preceding node C in the path to node C, and computer-readable program code means for replacing the node C in the tree with node B.
Specification
-
- Resources
-
Current AssigneeInternational Business Machines Corporation
-
Original AssigneeInternational Business Machines Corporation
-
InventorsSharma, Supriya S.
-
Primary Examiner(s)Lintz, Paul R.
-
Application NumberUS08/978,697Time in Patent Office770 DaysField of Search707/100, 707/101, 341/51, 341/67US Class Current1/1CPC Class CodesG06F 16/322 TreesY10S 707/99942 Manipulating data structure...
