Lecture Data Structures: Lesson 41

Chia sẻ: Hàn Thiên Ngạo | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

22
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Data Structures: Lesson 41

Skip List: Implementation S3 S2 34 S1 23 34 S0 12 23 34 45
Lecture No.41 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 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 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 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 strawberry
Example  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 strawberry
Example  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 strawberry
Example 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)%TableSize
Finding the hash function int hashCode( char* s ) { int i, sum; sum = 0; for(i=0; i < strlen(s); i++ ) sum = sum + s[i]; // ascii value return sum % TABLESIZE; }
Example Hash Functions  Another possibility is to convert the string into some number in some arbitrary base b (b also might be a prime number): length 1 h( str ) str[i ] b i %T i 0 0 1 2 Example : h( ABC ) (65b 66b 67b )%T
Example Hash Functions  If the keys are integers then key%T is generally a good hash function, unless the data has some undesirable features.  For example, if T = 10 and all keys end in zeros, then key%T = 0 for all keys.  In general, to avoid situations like this, T should be a prime number.