Searching Flashcards
How many compares are used for search hits in sequential search in the worst case?
N compares
How many compares to insert into an inittally empty Linked List Symbol Table?
N^2 / 2
How many compares does a search hit use in a BST?
2 ln N
How many compares do insertions and search misses in a BST require?
2 ln N
What is the height of a red-black BST?
2 lg N
What is the average lenth of a path from root to node in a RB tree?
1.00 lg N
Which operations take logarithmic time in the worst case in a RB BST?
- Search
- inesrt
- min
- max
- floor
- ceiling
- rank
- select
- delete min
- delete max
- range count
What are the compares used for search and insert in the worst case for 2-3 trees?
lg N
What is the average length of the lists in separate chaining?
N / M
Why is the probability that the number of keys in a list is within a small constant factor of N/M, close to 1?
What is the growth rate of the average length of the longest list in a separate chaining?
log N / log log N
What are the number of compares for miss and insert in a Separate Chaining has table?
N/M
How does get() work in sequential search in an unordered symbol table?
Scan through list, using equals() to compare search key with key in each node.
How does put() work in a linked list implementation of an unordered symbol table?
Same as get(), however update value once match is found, else inserted at beginning.
How does binary search work?
Compare search against key in middle half.
* If search < middle, search left, else right.
How many compares does Binary Search in an ordered array use?
lg N + 1
How many accesses does it take to insert a key into an ordered array, in the worst case?
2N
What is the order of growth for get, contains, floor, ceiling, rank in an ordered array?
log N
What is the order of growth for deleteMin, delete and put in an ordered array ST?
N
How many accesses does it take to insert a key into an initially empty table?
N^2
What is the worst case for search and insert, in sequential search? (Unordered linked lists)
N
What is the worst case for search and insert in binary search (ordered arrays)?
lgN, 2N
What are the pros and cons of SequentialSearchST?
- Best fow tiny ST’s
- Slow for large STs
What are the pros and cons of BinarySearchST?
- Optimal search and space, order based
- Slow insert
What are the pros and cons of BST?
- Easy implement, order based
What are the pros and cons of RedBlack BSTs?
- Optimal search and insert, order based
- Space for links
What are the pros and cons of Hash Tables?
- Fast search/insert for common data
- Need hash for each type, no order, space for links/empty
What is the recursive relation of Binary Search?
