vili Contents 4.5 Balanced Trees:AVL Trees 112 4.6 Balanced Trees:B-trees 122 Exercises 131 Bibliographic Notes and Further Reading 134 5 Abstract Data Type Sets-I 136 5.1 ADT Set:Definitions 137 5.2 Implementing Sets using Bit-vectors 139 5.3 Implementing Sets using Lists 141 5.4 Implementing Sets using Trees 145 Exercises 149 Bibliographic Notes and Further Reading 150 6 Abstract Data Type Sets-II 152 6.1 ADT Mapping 152 6.2 Hashing (Key Transformation) 155 6.3 Priority Queues 170 6.4 The ADT Relation 178 Exercises 189 Bibliographic Notes and Further Reading 197 7 Non-Linear ADTs-Graphs 200 7.1 Definitions and Terminology 200 7.2 ADT Graph and its Implementation 203 7.3 Spanning Trees 206 7.4 Path-finding Algorithms 217 Exercises 224 Bibliographic Notes and Further Reading 228 PART II:Algorithm Design with Abstract Data Types 231 8 Techniques for Developing Efficient Algorithms 232 8.1 Divide and Conquer 232 8.2 Dynamic Programming 237 8.3 Other Techniques 245 Exercises 245 Bibliographic Notes and Further Reading 249 9 Sorting:an Algorithm on the ADT List 251 9.1 An Abstract Sorting Algorithm 251 9.2 Easy Split/Hard Join Sorting Algorithms 254 9.3 Hard Split/Easy Join Sorting Algorithms 259 9.4 Sorting by Utilising the Representation of Elements 270 9.5 Taxonomy,Comparisons and Related Issues 273