tailieunhanh - Lecture Data Structures: Lesson 41

Lecture Data Structures: Lesson 41 provide students with knowledge about implementation: TowerNode; implementation: QuadNode; skip lists with quad nodes; performance of skip lists; implementation 5: AVL tree; implementation 6: hashing; example hash functions; . | Skip List Implementation S3 S2 34 S1 23 34 S0 12 23 34 45 Lecture Data Structure Dr. Sohail Aslam Implementation TowerNode head tail Tower Node 20 26 30 40 50 57 60 TowerNode will have array of next pointers. Actual number of next pointers will be decided by the random procedure. Define MAXLEVEL as an upper limit on number of levels in a node. Implementation QuadNode A quad-node stores item quad node link to the node before link to the node after link to the node below link to the node above x This will require copying the key item at different levels Skip Lists with Quad Nodes S3 S2 31 S1 23 31 34 64 S0 12 23 26 31 34 44 56 64 78 Performance of Skip Lists In a skip list with n items The expected space used is proportional to n. The expected search insertion and deletion time is proportional to log n. Skip lists are fast and simple to implement in practice Implementation 5 AVL tree An AVL tree ordered by key key entry insert a standard insert log n find a standard find without removing of course log n key entry key entry remove a standard remove log n key entry and so on Anything better So far we have find remove and insert where time varies between constant logn. It would be nice to have all three as constant time operations Implementation 6 Hashing An array in which TableNodes are not stored key entry consecutively Their place of storage is 4 calculated using the key and a hash function 10 hash array Key index function 123 Keys and entries are scattered throughout the array. Hashing insert calculate place of storage insert key entry TableNode 1 find calculate place of 4 storage retrieve entry 1 10 remove calculate place of storage set it to null 1 123 All are constant time 1 Hashing We use an array of some fixed size T to hold the data. T is typically prime. Each key is mapped into some number in the range 0 to T-1 using a hash function which ideally should be efficient to compute. Example fruits Suppose our hash function 0 kiwi gave us the following 1 .