a) Write a function max_in_tree(t) that returns the maximum value in any binary tree.
b) Modify the function to be more efficient if the input tree is known to be a binary search tree.
Write a function that takes an integer N and inserts N random values in the range from 0 .. N – 1 into a binary search tree. Let r be the ratio of the tree's height to the minimum possible height of any tree that holds N values. The function should compute and return r.
Write a class TreeSet that implements a set of values using a binary search tree, with methods add() and contains(). Implement these methods using recursion, with no loops. Hint: write recursive helper functions outside your TreeSet class that work with Node objects.
Write a program that reads a text file and prints the most common word in the file, along with its count of occurrences. Assume that words are sequences of Latin letters (A .. Z, a .. z), and ignore case. Do not use a Python dictionary. Instead, use a binary search tree to store the word counts.
Write a method that determines how many values v in a binary search tree of unique integers fall in the range a ≤ v ≤ b, where a and b are function parameters. The function should run in time O(h + n), where h is the tree height and n is the number of integers in the range.
Write a function that returns the greatest difference between any two consecutive values in a binary search tree.
Write a function that takes a binary tree and returns True if the tree satisfies the ordering requirements of a binary search tree.
Write a method which, given a binary search tree of non-negative integers and an integer i, returns the next highest value in the tree, i.e. the smallest value in the tree that is greater than i. Return -1 if there are no values greater than i. Assume that all integers in the tree are unique. The value i may or may not be present in the tree. Your function should run in time O(h), where h is the height of the tree.
Modify our binary search tree implementation from last week's lecture so that it implements a dictionary with these operations:
d.add(key, val)
d.contains_key(key)
d.lookup(key)
The lookup() method should return None if the key is not found.
In the dynamic array class that we saw in the lecture, we started with 10 elements, and doubled the number of array elements on every resize operation. We then showed that we can grow the array to size N in time O(N), because
10 + 20 + 40 + 80 + ... + N = O(N)
Prove that, more generally, for any starting size S and growth factor R, we have
S + RS + R2S + R3S + ... + N = O(N)
where N = RkS, the array size after k resize operations.
Suppose that in our dynamic array implementation instead of doubling the array size at each step we only multiply it by 1.5, which will save memory. By the previous exercise, the time per add() operation will still be O(1) on average. However, it will be more expensive by a constant factor, which is the price we'll pay for the decreased memory usage.
Specifically, if we double the array size at each step, then the total cost of all the resize operations to grow the array to size N will be proportional to
f(N) = 1 + 2 + 4 + 8 + ... + N
If we multiply it by 1.5 at each step, the total cost will be proportional to
g(N) = 1 + (1.5) + (1.5)2 + (1.5)3 + ... = N
So the increase in cost will be lim N → ∞ [g(N) / f(N)], which is a constant. Compute the value of this constant.
Consider the hash function we saw in the lecture:
# Generate a hash code in the range 0 .. 2^32 - 1.
def my_hash(s):
h = 0
for c in s:
d = ord(c)
h = (B * h + d) % (2 ** 32)
return ha) If B = 0, what hash function will result? Will this be a good hash function?
b) If B = 1, what hash function will result? Will this be a good hash function?
c) Suppose that we want to place all unique words of War and Peace into 10,000 hash buckets. If we use the hash function above, some values of B will be better than others, because they will result in a more even distribution of hash values. Design an experiment to compare the performance of these choices: B = 2; B = 256; B = 257; B = 65,537; B = 1,000,003.