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;...
Nội dung trích xuất từ tài liệu:
Lecture Data Structures: Lesson 41Skip List: Implementation S3 S2 34 S1 23 34 S0 12 23 34 45 Lecture No.41 Data StructureDr. Sohail AslamImplementation: TowerNode head tail TowerNode 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 quadnode • 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 levelsSkip Lists with Quad Nodes S3 S2 31 S1 23 31 34 64 S0 12 23 26 31 34 44 56 64 78Performance 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 logn.  Skip lists are fast and simple to implement in practiceImplementation 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 andsoonAnything 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 values: 2 banana hashCode(apple)=5 3 watermelon hashCode(watermelon)=3 4 hashCode(grapes)=8 hashCode(cantaloupe)=7 5 apple hashCode(kiwi)=0 6 mango hashCode(strawberry)=9 7 cantaloupe hashCode(mango)=6 hashCode(banana)=2 8 grapes 9 strawberryExample  Store data in a table 0 kiwi 1 array: table[5]=apple 2 banana table[3]=watermelon 3 watermelon table[8]=grapes 4 table[7]=cantaloupe 5 apple table[0]=kiwi table[9]=strawberry 6 mango table[6]=mango 7 cantaloupe table[2]=banana 8 grapes 9 strawberryExample  Associative array: 0 kiwi 1 table[apple] 2 banana table[watermelon] table[grapes] 3 watermelon 4 table[cantaloupe] table[kiwi] 5 apple table[strawberry] 6 mango table[mango] 7 cantaloupe table[banana] 8 grapes 9 strawberryExample Hash Functions If the keys are strings the hash function is some function of the characters in the strings. One possibility is to simply add the ASCII values of the characters: length 1 h( str ) str[i ] %TableSize i 0 Example : h( ABC ) (65 66 67)%TableSizeFinding the hash function int hashCode( char* s ) { int i, sum; sum = 0; for(i=0; i < strlen(s); i++ ) sum = sum + s[i]; ...