Write a function equal(t,
u) that takes two Node objects
representing the roots of two binary trees. The
function should return True if the
binary trees are identical, i.e. they have the same structure
and the same values in corresponding nodes.
Write a function that prints out all values in a binary search tree in order, separated by spaces.
Modify your function to print out the tree values in reverse order.
Write a function that takes a binary tree and constructs a second tree that contains all the value from the first tree and is as balanced as possible.
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 function that takes a binary tree and returns True if the tree is complete.
Write a program that reads words from a file whose name is given on the command line. For each unique word in the file, the program should compute a hash value in the range 0..63 using the string hashing function we saw in the lecture. Then it should print a histogram: for each hash value, display a number of asterisks showing how many different words hashed to that value.
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) # 0 .. 255
h = (K * h + d) % (2 ** 32)
return h
a) If K = 0, what hash function will result? Will this be a good hash function?
b) If K = 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 a hash table with 10,000 buckets. If we use the hash function above, some values of K 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: K = 2; K = 256; K = 257; K = 65,537; K = 1,000,003.
Write a program that reads an integer N and simulates inserting (100 · N) values into a hash table with N buckets using separate chaining, assuming that hash values will be distributed randomly. The program should print the lengths of the longest and shortest chains.
Suppose that we insert N values into a hash table with N buckets. What fraction of the buckets do we expect will be empty? Assume that N is a large number.
We'd like to implement a data structure RandomQueue with the following interface:
q.add(x) – add an element to the queue
q.remove() - removes a random element from the queue
q.is_empty() - test if a RandomQueue is empty
All operations should be fast, i.e. not run in linear time. How can we implement this structure?