PatriciaSlide 2Node StructureCompressed Binary Trie To PatriciaSlide 5InsertSlide 7Slide 8Slide 9Slide 10Slide 11Deletep Has One Self Pointerp Has No Self PointerSlide 15Slide 16Slide 17Slide 18Patricia•Practical Algorithm To Retrieve Information Coded In Alphanumeric.•Compressed binary trie.•All nodes are of the same data type (binary tries use branch and element nodes).Pointers to only one kind of node.Simpler storage management.Patricia•Uses a header node.•Remaining nodes define a trie structure that is the left subtree of the header node. •Trie structure is the same as that for the compressed binary trie of previous lecture.Node Structure•bit# = bit used for branching•LC = left child pointer•Pair = dictionary pair•RC = right child pointerPairbit# LC RCCompressed Binary Trie To Patricia010001001110001001000111110011010 112344Move each element into an ancestor or header node.Compressed Binary Trie To Patricia0100011111234 400011101000111100010011000InsertInsert 000010100001010Insert 00000000000000000010105InsertInsert 00000000000101000000005Insert 0000010000010100000000500000106InsertInsert 000100000001010000000050000010600010004000000050000010600001010InsertInsert 000010000010004000000050000010600001010InsertInsert 00010100001000400000005000001060000101000001007InsertInsert 0001010000100040000000500000106000010100000100700010106Delete•Let p be the node that contains the dictionary pair that is to be deleted.•Case 1: p has one self pointer.•Case 2: p has no self pointer.p Has One Self Pointer•p = header => trie is now empty.Set trie pointer to null.•p != header => remove node p and update pointer to p.0001000p0000000pp Has No Self Pointer•Let q be the node that has a back pointer to p.•Node q was determined during the search for the pair with the delete key k.0001000pyqBlue pointer could be red or black.p Has No Self Pointer•Use the key y in node q to find the unique node r that has a back pointer to node q.0001000pyqzrp Has No Self Pointer•Copy the pair whose key is y to node p.0001000pyqzryp Has No Self Pointer•Change back pointer to q in node r to point to node p.0001000pyqzryp Has No Self Pointer•Change forward pointer to q from parent(q) to child of q.0001000pyqzryNode q now has been removed from
View Full Document
Unlocking...