CS 225 Lecture Notes - Lecture 30: Nearest Neighbor Search, Priority Queue, Self-Balancing Binary Search Tree
18 Nov 2016
School
Department
Course
Professor
Document Summary
Big records--- if your records are really big, should you keep them in the hash table, we would want to do a separate chaining approach (open hashing) Structure speed --- arrays by themselves are really fast, so (probase hashing) is better probase hashing vs open hashing. Hash tables replace avl trees in an implementation of a dictionary. There is a constraint on keyspaces for bst that does not affect hasing Let"s pretend to be zappos, our keys are shoes, if this shoe < that shoe, this doesn"t make sense because we have no heierarchy of shoes. We could overload the < operator, but it doesn"t make sense to others. Comperable keys means that op < is defined. There"s a lot more you can do with a bst than a dictionary. For example nearest neighbor search //cs374 range finding nearest neighbor search is much easier with a balanced tree. Area of active research in mathematics to develop general purpose hash functions.
